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
|
@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}
}
@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}
}
|