MSO definable string transductions and two-way finite-state transducers
From MaRDI portal
Publication:4406290
DOI10.1145/371316.371512zbMath1171.03326OpenAlexW2106181999MaRDI QIDQ4406290
Hendrik Jan Hoogeboom, Joost Engelfriet
Publication date: 25 June 2003
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/371316.371512
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Related Items
Regular model checking with regular relations, Definable transductions and weighted logics for texts, The equivalence problem for deterministic MSO tree transducers is decidable, Query Automata for Nested Words, Computability by monadic second-order logic, On the decidability of the valuedness problem for two-way finite transducers, Pebble minimization: the last theorems, Weighted two-way transducers, Complexity of regular functions, Weighted two-way transducers, Synthesizing Computable Functions from Rational Specifications Over Infinite Words, Unnamed Item, Input- or output-unary sweeping transducers are weaker than their 2-way counterparts, On the descriptional complexity of stateless deterministic ordered restarting automata, Unnamed Item, Aperiodic String Transducers, On the Complexity of Infinite Advice Strings, One-way resynchronizability of word transducers, Nondeterministic Streaming String Transducers, Multiple context-free tree grammars: lexicalization and characterization, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Sequences of words defined by two-way transducers, Streamable regular transductions, Regular Transformations of Data Words Through Origin Information, Two-way pebble transducers for partial functions and their composition, Unnamed Item, Both Ways Rational Functions, Aperiodic String Transducers, Register Transducers Are Marble Transducers, Origin-equivalence of two-way word transducers is in PSPACE, Regular transducer expressions for regular transformations, Copyful Streaming String Transducers, Unnamed Item, Finite transducers and rational transductions, From Two-Way Transducers to Regular Function Expressions, Normality and two-way automata, Non-deterministic transducer models of retransmission protocols over noisy channels, Query automata over finite trees
