scientific article; zbMATH DE number 7003194

DOI10.23638/LMCS-14(4:22)2018MaRDI QIDQ4611380zbMATH OpenFDO

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

Publication date 18 January 2019

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

zbMATH Keywords

one-way definabilityregular word transductionssweeping transducerstwo-way transducers

Mathematics Subject Classification ID

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

Recommendations

• One-way definability of sweeping transducer
• From two-way to one-way finite state transducers
• One-way resynchronizability of word transducers
• An algebraic characterization of unary two-way transducers
• On the containment and equivalence problems for two-way transducers
• scientific article; zbMATH DE number 6606353
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• A pumping lemma for two-way finite transducers
• scientific article; zbMATH DE number 3978428
• One-way multihead finite automata and 2-bounded languages

Cites work

• A general theory of translation
• A generalised twinning property for minimisation of cost register automata
• A lower bound technique for the size of nondeterministic finite automata
• A pumping lemma for two-way finite transducers
• A remark on finite transducers
• An algebraic characterization of unary two-way transducers
• Aperiodic two-way transducers and FO-transductions
• Determinization of transducers over finite and infinite words.
• Economy of description for single-valued transducers
• Expressiveness of streaming string transducers
• Factorisation Forests for Infinite Words
• Factorization forests of finite height
• First-order definability of rational transductions: an algebraic approach
• First-order definable string transformations
• From two-way to one-way finite state transducers
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• Minimizing resources of sweeping and streaming string transducers
• MSO definable string transductions and two-way finite-state transducers
• One-way definability of sweeping transducer
• The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications
• Two-way automaton computations
• Une caractérisation des fonctions séquentielles et des fonctions sous- séquentielles en tant que rélations rationnelles
• Uniformisation of two-way transducers

Cited in

(24)

• One-way permutations and self-witnessing languages
• One-way resynchronizability of word transducers
• On the decidability of the valuedness problem for two-way finite transducers
• An algebraic characterization of unary two-way transducers
• Input- or output-unary sweeping transducers are weaker than their 2-way counterparts
• Minimizing resources of sweeping and streaming string transducers
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• scientific article; zbMATH DE number 7559499 (Why is no real title available?)
• The many facets of string transducers (invited talk)
• Synthesis of computable regular functions of infinite words
• Untwisting two-way transducers in elementary time
• From two-way to one-way finite state transducers
• One-way definability of sweeping transducer
• Streamability of nested word transductions
• Finitary compositions of two-way finite-state transductions
• scientific article; zbMATH DE number 6606353 (Why is no real title available?)
• From two-way transducers to regular function expressions
• Definability Results for Top-Down Tree Transducers
• Deciding whether an attributed translation can be realized by a top-down transducer
• Deciding whether an attributed translation can be realized by a top-down transducer
• Shape preserving tree transducers
• Decomposing finite-valued two-way finite transducers
• A Ramsey theorem for finite monoids
• Definability results for top-down tree transducers

This page was built for publication:

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