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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
@incollection{bagan2006,
doi = {10.1007/11874683_11},
% url = {https://doi.org/10.1007%2F11874683_11},
year = 2006,
publisher = {Springer Berlin Heidelberg},
pages = {167--181},
author = {Guillaume Bagan},
title = {{MSO} Queries on Tree Decomposable Structures Are Computable with Linear Delay}
}
@article{kazana2013,
doi = {10.1145/2528928},
% url = {https://doi.org/10.1145%2F2528928},
year = 2013,
month = {nov},
publisher = {Association for Computing Machinery ({ACM})},
volume = {14},
number = {4},
pages = {1--12},
author = {Wojciech Kazana and Luc Segoufin},
title = {Enumeration of monadic second-order queries on trees}
}
@incollection{colcombet,
doi = {10.1007/978-3-540-73420-8_77},
% url = {https://doi.org/10.1007%2F978-3-540-73420-8_77},
publisher = {Springer Berlin Heidelberg},
pages = {901--912},
author = {Thomas Colcombet},
title = {A Combinatorial Theorem for Trees}
}
@incollection{bender2000,
doi = {10.1007/10719839_9},
% url = {https://doi.org/10.1007%2F10719839_9},
year = 2000,
publisher = {Springer Berlin Heidelberg},
pages = {88--94},
author = {Michael A. Bender and Mart{\'{\i}}n Farach-Colton},
title = {The {LCA} Problem Revisited}
}
@article{tarjan1984,
doi = {10.1137/0213024},
% url = {https://doi.org/10.1137%2F0213024},
year = 1984,
month = {may},
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
volume = {13},
number = {2},
pages = {338--355},
author = {Dov Harel and Robert Endre Tarjan},
title = {Fast Algorithms for Finding Nearest Common Ancestors}
}
@article{schieber1988,
doi = {10.1137/0217079},
% url = {https://doi.org/10.1137%2F0217079},
year = 1988,
month = {dec},
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
volume = {17},
number = {6},
pages = {1253--1262},
author = {Baruch Schieber and Uzi Vishkin},
title = {On Finding Lowest Common Ancestors: Simplification and Parallelization}
}
@article{berkman1993,
doi = {10.1137/0222017},
% url = {https://doi.org/10.1137%2F0222017},
year = 1993,
month = {apr},
publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
volume = {22},
number = {2},
pages = {221--242},
author = {Omer Berkman and Uzi Vishkin},
title = {Recursive Star-Tree Parallel Data Structure}
}
@incollection{courcelle1990,
doi = {10.1016/b978-0-444-88074-1.50010-x},
url = {https://doi.org/10.1016%2Fb978-0-444-88074-1.50010-x},
year = 1990,
publisher = {Elsevier},
pages = {193--242},
author = {Bruno Courcelle},
title = {Graph Rewriting: An Algebraic and Logic Approach}
}
@incollection{courcelle1992,
doi = {10.1007/3-540-55121-2_2},
url = {https://doi.org/10.1007%2F3-540-55121-2_2},
year = 1992,
publisher = {Springer Berlin Heidelberg},
pages = {13--24},
author = {B. Courcelle and M. Mosbah},
title = {Monadic second-order evaluations on tree-decomposable graphs}
}
@incollection{flum2001,
doi = {10.1007/3-540-44503-x_2},
url = {https://doi.org/10.1007%2F3-540-44503-x_2},
year = 2001,
publisher = {Springer Berlin Heidelberg},
pages = {22--38},
author = {Jörg Flum and Markus Frick and Martin Grohe},
title = {Query Evaluation via Tree-Decompositions}
}
@misc{bojanczyk,
url = {https://www.mimuw.edu.pl/~bojan/upload/confdltBojanczyk09.pdf},
year = 2009,
% month = {dec},
% publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
% volume = {17},
% number = {6},
pages = {8--10},
author = {Mikołaj Bojańczyk},
title = {Factorization Forests}
}
@misc{bojanczyktoolbox,
url = {https://www.mimuw.edu.pl/~bojan/papers/toolbox-reduced-feb6.pdf},
year = 2018,
% month = {dec},
% publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
% volume = {17},
% number = {6},
pages = {65--70},
author = {Mikołaj Bojańczyk},
title = {An Automata Toolbox}
}
@inproceedings{amarilli2019,
doi = {10.1145/3294052.3319702},
url = {https://doi.org/10.1145%2F3294052.3319702},
year = 2019,
publisher = {{ACM} Press},
author = {Antoine Amarilli and Pierre Bourhis and Stefan Mengel and Matthias Niewerth},
title = {Enumeration on Trees with Tractable Combined Complexity and Efficient Updates},
booktitle = {Proceedings of the 38th {ACM} {SIGMOD}-{SIGACT}-{SIGAI} Symposium on Principles of Database Systems - {PODS} {\textquotesingle}19}
}
@phdthesis{kazanaphd,
author = {Wojciech Kazana},
title = {Query Evaluation with Constant Delay},
school = {ENS Cachan},
year = 2013
}
|