Complexity of certain decision problems about congruential languages
From MaRDI portal
Publication:1085618
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
rewriting systemscongruence classesChurch-Rosser Thue systemscommutative Thue systemscongruential language
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
