Complexity of certain decision problems about congruential languages

DOI10.1016/0022-0000(85)90051-0zbMath0607.68055OpenAlexW2058954424MaRDI QIDQ1085618

Heinrich Rolletschek, Paliath Narendran, Colm P. O'Dunlaing

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90051-0

zbMATH Keywords

rewriting systemscongruence classesChurch-Rosser Thue systemscommutative Thue systemscongruential language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Thue and Post systems, etc. (03D03)

Related Items

On sufficient-completeness and related properties of term rewriting systems, Thue systems as rewriting systems, On deciding the confluence of a finite string-rewriting system on a given congruence class, On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata, A note on regular classes in special Thue systems, An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group, On public-key cryptosystem based on Church-Rosser string-rewriting systems, Church-Rosser codes, The size of Higman-Haines sets, ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA, WHEN CHURCH-ROSSER BECOMES CONTEXT FREE, Cancellativity in finitely presented semigroups, On equational theories, unification, and (un)decidability, One-rule semi-Thue systems with loops of length one, two or three

Cites Work

• The Church-Rosser property and special Thue systems
• Thue congruences and the Church-Rosser property
• The covering and boundedness problems for vector addition systems
• Infinite regular Thue systems
• Parallel program schemata
• Confluent and Other Types of Thue Systems
• Recursive Unsolvability of a problem of Thue
• The undecidability of the Turing machine immortality problem
• Strong Computability and Variants of the Uniform Halting Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item