35 citations · 87 across the 11 of their papers we have counts for
13 papers
Computability by Monadic Second-Order Logic
Joost Engelfriet
A binary relation on graphs is recursively enumerable if and only if it can be computed by a formula in monadic second-order logic. The latter means that the formula defines a set…
A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
Joost Engelfriet, Heiko Vogler
We introduce MSO graph storage types, and call a storage type MSO-expressible if it is isomorphic to some MSO graph storage type. An MSO graph storage type has MSO-definable sets o…
Linear Bounded Composition of Tree-Walking Tree Transducers: Linear Size Increase and Complexity
Joost Engelfriet, Kazuhiro Inaba, Sebastian Maneth
Compositions of tree-walking tree transducers form a hierarchy with respect to the number of transducers in the composition. As main technical result it is proved that any such com…
XML Navigation and Transformation by Tree-Walking Automata and Transducers with Visible and Invisible Pebbles
Joost Engelfriet, Hendrik Jan Hoogeboom, Bart Samwel
The pebble tree automaton and the pebble tree transducer are enhanced by additionally allowing an unbounded number of "invisible" pebbles (as opposed to the usual "visible" ones).…
The Trees of Hanoi
Joost Engelfriet
The game of the Towers of Hanoi is generalized to binary trees. First, a straightforward solution of the game is discussed. Second, a shorter solution is presented, which is then s…
Multiple Context-Free Tree Grammars: Lexicalization and Characterization
Joost Engelfriet, Andreas Maletti, Sebastian Maneth
Multiple (simple) context-free tree grammars are investigated, where "simple" means "linear and nondeleting". Every multiple context-free tree grammar that is finitely ambiguous ca…