Comon H. etc. Tree Automata Techniques and Applications
Подождите немного. Документ загружается.
INDEX 261
OI, 67
order, 103
order-sorted signatures, 96
overlapping constraints, 134
path-closed, 39
pop clause, 191
position, 16
Presburger’s arithmetic, 73
production rules, 52
productive, 52
program analysis, 138
projection, 80, 212
pumping lemma, 29
push clause, 191
pushdown automaton, 195
Rabin
automaton, 74, 96
theorem, 96
ranked alphabet, 15
RATEG, 113
reachable, 52
recognition
by an automaton, 115
recognizable
by a hedge automaton, 204
language of unranked trees, 211
recognized, 115
recognizes, 115
reduced, 52
NFHA, 204
reducibility theory, 98, 125, 133
reduction automaton, 126
regular equation systems, 61
regular expression
deterministic, 233
regular tree expressions, 57
regular tree grammars, 52
regular tree language, 52
relation
rational relation, 106
of bounded delay, 106
remote equalities, 128
root symbol, 16
rules
ǫ-rules, 23
run, 22, 115
of an alternating tree automaton,
185
of an alternating word automaton,
184
of an automaton, 115
of hedge automaton, 202
successful, 22
sequential calculus, 73
sequentiality, 101
set constraints, 137
definite, 190
shuffle, 215
size, 16, 116
of a constraint, 116
of an automaton with constraints,
116
SkS, 88
solution, 104
sort
constraint, 96
expression, 96
symbol, 96
state
accessible, 24
dead, 24
stepwise automaton, 226
substitution, 17
subterm, 16
subterm ordering, 16
subtree
of an unranked tree, 201
success node, 184
symbol to symbol, 34
synchronization states, 76
target state, 114
temporal logic
propositional linear time temporal
logic, 108
term
in the simply typed lambda calcu-
lus, 103
well-formed, 96
terminal, 51
terms, 15, 103
theory
of reducibility, 98
transducer
ε-free, 164
rational, 164
transition rules, 114
TATA — November 18, 2008 —
262 INDEX
tree, 15
unranked, 201
tree automaton, 20
flat tree automaton, 47
alternating, 183
complete, 24
deterministic, 23
dual, 188
generalized, see GTSA
reduced, 24
reduction automaton, 114
top down, 38
two-way, 191
weak alternating, 196
with ǫ-rules, 22
with constraints between brothers,
113
tree homomorphism
alphabetic, 35
complete, 35
delabeling, 35
linear, 32
symbol to symbol, 34
tree substitution, 55
tree transducer
ε-free, 173
bottom-up, 173
complete, 173
deterministic, 173
linear, 173
non-erasing, 173
top-down, 174
tree grammar, 51
tree homomorphism, 31
tree automaton
alternating, 185
product, 30
tree homomorphism
ǫ-free, 34
two-way tree automaton, 191
type
in the simply typed lambda calcu-
lus, 103
type inference, 138
unranked tree, 201
variable position, 16
variables, 15
weak monadic second-order logic, 212
Weak Second-order monadic logic with
K successors, 95
WMSO, 212
WS1S, 73
WSkS, 73, 87, 95
Yield, 63
TATA — November 18, 2008 —