Two-way pebble transducers for partial functions and their composition

DOI10.1007/s00236-015-0224-3zbMath1330.68155WikidataQ59427678 ScholiaQ59427678MaRDI QIDQ748432

Joost Engelfriet

Publication date: 29 October 2015

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-015-0224-3

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Unnamed Item, Pebble minimization: the last theorems

Cites Work

• Complementing deterministic tree-walking automata
• On tree transducers for partial functions
• Complexity results for two-way and multi-pebble automata and their logics
• Typechecking for XML transformers
• A comparison of pebble tree transducers with macro tree transducers
• XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
• Adding pebbles to weighted automata: easy specification \& efficient evaluation
• Determinacy and Rewriting of Top-Down and MSO Tree Transformations
• Graph Reachability and Pebble Automata over Infinite Alphabets
• Translation from classical two-way automata to pebble two-way automata
• Expressive Power of Pebble Automata
• MSO definable string transductions and two-way finite-state transducers
• Three hierarchies of transducers
• Weighted Specifications over Nested Words
• Pebble Weighted Automata and Weighted Logics
• Finite state machines for strings over infinite alphabets
• Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure
• Complexity of Pebble Tree-Walking Automata
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item