A canonical automaton for one-rule length-preserving string rewrite systems

DOI10.1016/j.ic.2015.07.002zbMath1329.68163MaRDI QIDQ498407

Michel Latteux, Yves Roos

Publication date: 28 September 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.07.002

zbMATH Keywords

rational transduction; string rewrite system

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

On prefixal one-rule string rewrite systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semi-commutations
• On lexicographic semi-commutations
• Semicommutations and algebraic languages
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• On cube-free \(\omega\)-words generated by binary morphisms
• Peg-solitaire, string rewriting systems and finite automata
• On the rational subsets of the free group
• Decidability of Termination of Grid String Rewriting Rules
• One-rule semi-Thue systems with loops of length one, two or three
• Iteration of rational transductions
• One-Rule Length-Preserving Rewrite Systems and Rational Transductions
• On Relations Defined by Generalized Finite Automata
• Term Rewriting and Applications
• Term Rewriting and Applications
• Semi-Thue systems with an inhibitor
• Termination and derivational complexity of confluent one-rule string-rewriting systems