Two-way finite state transducers with nested pebbles

DOI10.1007/3-540-45687-2_19MaRDI QIDQ4708573zbMATH OpenFDO

Authors Sebastian Maneth, Joost Engelfriet

Publication date 18 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2420/24200234.htm

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• From two-way to one-way finite state transducers
• Two-way counter machines and finite-state transducers†
• scientific article; zbMATH DE number 5286862
• Finitary compositions of two-way finite-state transductions
• Translation from classical two-way automata to pebble two-way automata
• Translation from classical two-way automata to pebble two-way automata
• Stateless one-way multi-head finite automata with pebbles
• Two-way pebble transducers for partial functions and their composition
• Finite state transducers
• Two-way finite state transducers and monadic second-order logic

Cited in

(13)

• A comparison of pebble tree transducers with macro tree transducers
• A pumping lemma for two-way finite transducers
• Translation from classical two-way automata to pebble two-way automata
• From Nondeterministic to Multi-Head Deterministic Finite-State Transducers
• Translation from classical two-way automata to pebble two-way automata
• Finitary compositions of two-way finite-state transductions
• Using acceptors as transducers
• Pebble-depth
• Transducers of polynomial growth
• Polyregular functions: characterisations and refutations
• Comparison-free polyregular functions
• Reversible pebble transducers
• Two-way pebble transducers for partial functions and their composition

This page was built for publication: Two-way finite state transducers with nested pebbles

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