Linear bounded automata and rewrite systems: influence of initial configurations on decision properties

DOI10.1007/3-540-53982-4_5MaRDI QIDQ2736359zbMATH OpenFDO

Authors Anne-Cecile Caron

Publication date 29 August 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-53982-4_5

Mathematics Subject Classification ID

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

Recommendations

• Undecidable properties on length-two string rewriting systems
• scientific article; zbMATH DE number 4060699
• Decision problems for term rewriting systems and recognizable tree languages
• Some undecidability results for weakly confluent monadic string-rewriting systems
• Termination of linear bounded term rewriting systems

Cited in

(14)

• On termination of one rule rewrite systems
• Simple termination is difficult
• Simple termination of rewrite systems
• Confluence up to garbage in graph transformation
• From Hertzsprung's problem to pattern-rewriting systems
• Undecidable properties on length-two string rewriting systems
• One-rule semi-Thue systems with loops of length one, two or three
• scientific article; zbMATH DE number 17534 (Why is no real title available?)
• Simple termination is difficult
• More problems in rewriting
• Confluence up to garbage
• Termination of linear bounded term rewriting systems
• Some undecidable termination problems for semi-Thue systems
• Termination of \(\{aa\rightarrow bc,bb\rightarrow ac,cc\rightarrow ab\}\)

This page was built for publication: Linear bounded automata and rewrite systems: influence of initial configurations on decision properties

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