Iteration of rational transductions

DOI10.1051/ITA:2000109MaRDI QIDQ4508635zbMATH OpenOpenAlexFDO

Authors Alain Terlutte, David Simplot

Publication date 3 October 2000

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222099, https://semanticscholar.org/paper/90e6fee319d9f7a334da12b90559b47781a2d0ff

zbMATH Keywords

length-preserving rational transductionslinear space computations

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• Iteration of invertible transductions
• On fixed points of rational transductions
• Invertible transductions and iteration
• Logical and algebraic characterizations of rational transductions
• scientific article; zbMATH DE number 4211520
• Rational transductions and complexity of counting problems
• Rational transductions and complexity of counting problems
• Finite transducers and rational transductions
• Closure under union and composition of iterated rational transductions
• Iterative weighted finite transductions

Cites work

• Classes of languages and linear-bounded automata
• Closure under union and composition of iterated rational transductions
• Context-sensitive string languages and recognizable picture languages
• Full AFLs and nested iterated substitution
• scientific article; zbMATH DE number 3860412 (Why is no real title available?)
• scientific article; zbMATH DE number 3714977 (Why is no real title available?)
• scientific article; zbMATH DE number 3765174 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• Iterated a-NGSM maps and Γ systems
• Nondeterministic Space is Closed under Complementation
• On characterizations of recursively enumerable languages
• On Relations Defined by Generalized Finite Automata
• Partial commutations and faithful rational transductions
• Recognizable picture languages and domino tiling
• Some characterizations of functions computable in on-line arithmetic
• Sur les rélations rationnelles entre monoides libres
• The method of forced enumeration for nondeterministic automata
• Transductions des langages de Chomsky

Cited in

(12)

• Iterative weighted finite transductions
• On prefixal one-rule string rewrite systems
• An Exercise on Fibonacci Representations
• scientific article; zbMATH DE number 4211520 (Why is no real title available?)
• scientific article; zbMATH DE number 4051036 (Why is no real title available?)
• Closure under union and composition of iterated rational transductions
• Consensus game acceptors and iterated transductions
• A canonical automaton for one-rule length-preserving string rewrite systems
• Lexicographic rationalizability and iterated admissibility
• Symbolic reachability analysis and maximally permissive entrance control for globally synchronized templates
• A Kleene characterization of computability
• Cyclic rational transductions and polynomials of rational functions

This page was built for publication: Iteration of rational transductions

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