The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
From MaRDI portal
Publication:3720578
DOI10.1016/S0019-9958(84)80041-8zbMath0592.03025MaRDI QIDQ3720578
Paliath Narendran, Friedrich Otto, Karl Winklmann
Publication date: 1984
Published in: Information and Control (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Thue and Post systems, etc. (03D03)
Related Items (10)
Thue systems as rewriting systems ⋮ Left-to-right regular languages and two-way restarting automata ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems ⋮ Parikh-reducing Church-Rosser representations for some classes of regular languages ⋮ A hierarchy of monotone deterministic non-forgetting restarting automata ⋮ Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems ⋮ Hierarchies of weakly monotone restarting automata ⋮ Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems ⋮ On equations and first-order theory of one-relator monoids ⋮ On two problems related to cancellativity
This page was built for publication: The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
