scientific article; zbMATH DE number 7003194

DOI10.23638/LMCS-14(4:22)2018zbMath1404.68065arXiv1706.01668MaRDI QIDQ4611380

Anca Muscholl, Olivier Gauwin, Gabriele Puppis, Félix Baschenis

Publication date: 18 January 2019

Full work available at URL: https://arxiv.org/abs/1706.01668

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

two-way transducerssweeping transducersone-way definabilityregular word transductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (10)

Definability results for top-down tree transducers ⋮ On the decidability of the valuedness problem for two-way finite transducers ⋮ Definability Results for Top-Down Tree Transducers ⋮ Deciding whether an attributed translation can be realized by a top-down transducer ⋮ One-way resynchronizability of word transducers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Two-Way Transducers to Regular Function Expressions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound technique for the size of nondeterministic finite automata
• Factorization forests of finite height
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• Determinization of transducers over finite and infinite words.
• Economy of description for single-valued transducers
• Expressiveness of Streaming String Transducers
• An Algebraic Characterization of Unary Two-Way Transducers
• A Pumping Lemma for Two-Way Finite Transducers
• First-order definable string transformations
• Two-way automaton computations
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• MSO definable string transductions and two-way finite-state transducers
• Minimizing resources of sweeping and streaming string transducers
• First-order definability of rational transductions
• A Generalised Twinning Property for Minimisation of Cost Register Automata
• Uniformisation of Two-Way Transducers
• From Two-Way to One-Way Finite State Transducers
• One-way Definability of Sweeping Transducer.
• Factorisation Forests for Infinite Words
• A general theory of translation
• A remark on finite transducers

This page was built for publication: