-
Notifications
You must be signed in to change notification settings - Fork 0
/
diploma.bib
109 lines (102 loc) · 5.31 KB
/
diploma.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
@article{DBLP:journals/corr/AzimovG17,
author = {Rustam Azimov and
Semyon Grigorev},
title = {Graph Parsing by Matrix Multiplication},
journal = {CoRR},
volume = {abs/1707.01007},
year = {2017},
url = {http://arxiv.org/abs/1707.01007},
archivePrefix = {arXiv},
eprint = {1707.01007},
timestamp = {Sat, 05 Aug 2017 14:56:23 +0200},
biburl = {http://dblp.org/rec/bib/journals/corr/AzimovG17},
bibsource = {dblp computer science bibliography, http://dblp.org}
}
@article{DBLP:journals/corr/BringmannGSW17,
author = {Karl Bringmann and
Fabrizio Grandoni and
Barna Saha and
Virginia Vassilevska Williams},
title = {Truly Sub-cubic Algorithms for Language Edit Distance and {RNA} Folding
via Fast Bounded-Difference Min-Plus Product},
journal = {CoRR},
volume = {abs/1707.05095},
year = {2017},
url = {http://arxiv.org/abs/1707.05095},
archivePrefix = {arXiv},
eprint = {1707.05095},
timestamp = {Mon, 11 Dec 2017 17:04:01 +0100},
biburl = {http://dblp.org/rec/bib/journals/corr/BringmannGSW17},
bibsource = {dblp computer science bibliography, http://dblp.org}
}
@INPROCEEDINGS{p2pdyck,
author={P. G. Bradford and V. Choppella},
booktitle={2016 IEEE 7th Annual Ubiquitous Computing, Electronics Mobile Communication Conference (UEMCON)},
title={Fast point-to-point Dyck constrained shortest paths on a DAG (Extended abstract)},
year={2016},
volume={},
number={},
pages={1-7},
keywords={directed graphs;program diagnostics;DAG;Dyck CFL;context-free language;directed acyclic graph;edge-labeled digraphs;exact integer path length algorithm;fast point-to-point Dyck constrained shortest paths;Algorithm design and analysis;Electronic mail;Grammar;Heuristic algorithms;Jacobian matrices;Matrix converters;Shortest path problem},
doi={10.1109/UEMCON.2016.7777894},
ISSN={},
month={Oct},
}
@phdthesis{Nathan,
author={Wiegand,Nathan M.},
year={2010},
title={On labeled paths},
journal={ProQuest Dissertations and Theses},
pages={96},
note={Авторское право - Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works; Обновлено - 2016-03-09},
abstract={Labeled graph theory is the marriage of two common problem domains to computer science—graph theory and automata theory. Though each has been independently studied in depth, there has been little investigation of their intersection, the labeled paths. This dissertation examines three results in the area of labeled path problems. The first result presents an empirical analysis of two context-free labeled all-pairs shortest-path algorithms using MapReduce as the experimental platform. The second and third results examine labeled paths in the context of formal languages beyond the context free languages. The second result is a lower bound on the length of the longest shortest path when the formal language constraining the path is a member of the control language hierarchy. Finally, the third result presents a labeled all-pairs shortest-path algorithm for each level of the infinite KLinear-Hierarchy.},
keywords={Applied sciences; Algorithms; Control language hierarchy; Formal languages; Graph theory; Labeled graphs; Computer science; 0984:Computer science},
isbn={9781124061917},
language={English},
url={https://search.proquest.com/docview/594660185?accountid=28393},
}
@article{Barrett,
author = {Chris Barrett and Riko Jacob and Madhav Marathe},
title = {Formal-Language-Constrained Path Problems},
journal = {SIAM Journal on Computing},
volume = {30},
number = {3},
pages = {809-837},
year = {2000},
doi = {10.1137/S0097539798337716},
URL = {https://doi.org/10.1137/S0097539798337716},
eprint = {https://doi.org/10.1137/S0097539798337716}
}
@article{VALIANT1975308,
title = "General context-free recognition in less than cubic time",
journal = "Journal of Computer and System Sciences",
volume = "10",
number = "2",
pages = "308 - 315",
year = "1975",
issn = "0022-0000",
doi = "https://doi.org/10.1016/S0022-0000(75)80046-8",
url = "http://www.sciencedirect.com/science/article/pii/S0022000075800468",
author = "Leslie G. Valiant"
}
@INPROCEEDINGS{D-Fast-BJM,
author={C. B. Ward and N. M. Wiegand and P. G. Bradford},
booktitle={2008 37th International Conference on Parallel Processing},
title={A Distributed Context-Free Language Constrained Shortest Path Algorithm},
year={2008},
volume={},
number={},
pages={373-380},
keywords={context-free grammars;distributed algorithms;formal languages;graph grammars;path planning;constrained shortest path algorithm;distributed algorithm;distributed context-free language;formal language;labeled graphs;shortest path problems;Computer languages;Computer science;Distributed computing;Formal languages;Jacobian matrices;Parallel processing;Production;Relational databases;Shortest path problem;Transportation;labeled graphs;labeled paths},
doi={10.1109/ICPP.2008.67},
ISSN={0190-3918},
month={Sept},}
@article{Johnson-Fast-BJM,
author = {Bradford, Phillip and A. Thomas, David},
year = {2009},
month = {07},
pages = {},
title = {Labeled shortest paths in digraphs with negative and positive edge weights},
volume = {43},
booktitle = {http://dx.doi.org/10.1051/ita/2009011}
}