Infinite string rewrite systems and complexity

DOI10.1006/JSCO.1997.0198MaRDI QIDQ1264463zbMATH OpenOpenAlexFDO

Authors J.-C. Birget

Publication date 29 April 2002

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jsco.1997.0198

zbMATH Keywords

time complexitydecidable word problem

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• About the descriptive power of certain classes of finite string-rewriting systems
• Dehn's Algorithm and the Complexity of Word Problems
• Finite complete rewriting systems and the complexity of word problem
• Space functions and space complexity of the word problem in semigroups.
• Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids

Cited in

(13)

• Non-Looping String Rewriting
• Space functions and space complexity of the word problem in semigroups.
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• The derivational complexity of string rewriting systems
• McNaughton families of languages.
• Upper bound on the derivational complexity in some word rewriting system
• Algorithmically complex residually finite groups
• Turing machines and bimachines
• scientific article; zbMATH DE number 1324448 (Why is no real title available?)
• Reductions and functors from problems to word problems
• Infinite Families of Finite String Rewriting Systems and Their Confluence
• scientific article; zbMATH DE number 3993567 (Why is no real title available?)
• Infinitely generated semigroups and polynomial complexity

This page was built for publication: Infinite string rewrite systems and complexity

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