On rationally controlled one-rule insertion systems

DOI10.1051/ITA/2022008MaRDI QIDQ5044416zbMATH OpenOpenAlexFDO

Authors Michel Latteux, Yves Roos

Publication date 31 October 2022

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/ita/2022008

zbMATH Keywords

context-free languagesstring rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Recommendations

• On prefixal one-rule string rewrite systems
• Graph-controlled insertion-deletion systems generating language classes beyond linearity
• Context-free insertion-deletion systems
• Small size insertion and deletion systems
• Insertion-deletion systems with substitutions. I

Cites work

• Decidability of termination of grid string rewriting rules
• Deleting string rewriting systems preserve regularity
• Elements of automata theory. Translated from the French by Reuben Thomas
• scientific article; zbMATH DE number 4205992 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3684913 (Why is no real title available?)
• scientific article; zbMATH DE number 3786151 (Why is no real title available?)
• Match-bounded string rewriting systems
• On one-rule grid semi-Thue systems
• On prefixal one-rule string rewrite systems
• On Regularity-Preservation by String-Rewriting Systems
• On the regular structure of prefix rewriting
• Semi-Thue systems with an inhibitor
• Some decision problems about controlled rewriting systems
• Termination proofs for string rewriting systems via inverse match-bounds
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Transductions des langages de Chomsky

Cited in

(3)

• On prefixal one-rule string rewrite systems
• One-rule length-preserving rewrite systems and rational transductions
• Subregularly controlled insertion systems

This page was built for publication: On rationally controlled one-rule insertion systems

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