Two-way pebble transducers for partial functions and their composition

DOI10.1007/S00236-015-0224-3zbMATH Open1330.68155DBLPjournals/acta/Engelfriet15OpenAlexW2087397784WikidataQ59427678 ScholiaQ59427678MaRDI QIDQ748432FDOQ748432

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

Recommendations

• scientific article; zbMATH DE number 1929941
• On reversible transducers
• Two-way transducers with a two-way output tape
• Uniformisation of two-way transducers
• From two-way to one-way finite state transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• Pebble-depth
• Title not available (Why is that?)
• Pebble minimization: the last theorems
• Transducers of polynomial growth
• Implementation and Application of Automata

This page was built for publication: Two-way pebble transducers for partial functions and their composition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q748432)