Monadic Thue systems
From MaRDI portal
Publication:1165842
DOI10.1016/0304-3975(82)90036-6zbMath0488.03020OpenAlexW2034188445MaRDI QIDQ1165842
Matthias Jantzen, Celia Wrathall, Ronald V. Book
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90036-6
Related Items
Cancellation in context-free languages: enrichment by reduction ⋮ Decidability of reachability for disjoint union of term rewriting systems ⋮ Computing presentations for subgroups of polycyclic groups and of context-free groups ⋮ Reductions in tree replacement systems ⋮ On language equations with invertible operations ⋮ On the regular equivalence problem for regular Thue systems ⋮ On a subclass of context-free groups ⋮ Decidability of confluence and termination of monadic term rewriting systems ⋮ Bottom-up tree pushdown automata and rewrite systems ⋮ Thue systems as rewriting systems ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ A closure property of regular languages ⋮ On the word problem for special monoids ⋮ Decidable sentences of Church-Rosser congruences ⋮ A note on regular classes in special Thue systems ⋮ Deterministic tree pushdown automata and monadic tree rewriting systems ⋮ \(\mathcal{L}\)-reduction computation revisited ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ On the rational subset problem for groups. ⋮ An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS ⋮ On the word problem for weakly compressible monoids ⋮ McNaughton families of languages. ⋮ Power of controlled insertion and deletion ⋮ The undecidability of a word problem: On a conjecture of Strong, Maggiolo-Schettini and Rosen ⋮ On the word problem for free products of semigroups and monoids ⋮ Some decision problems about controlled rewriting systems ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ NTS grammars and Church-Rosser systems ⋮ A characterisation of deterministic context-free languages by means of right-congruences ⋮ Testing for the Church-Rosser property ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ When is a monoid a group? The Church-Rosser case is tractable ⋮ Church-Rosser systems with respect to formal languages ⋮ Polycyclic and Bicyclic Valence Automata ⋮ The word problem for one-relation monoids: a survey ⋮ Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Match-bounded string rewriting systems ⋮ Deleting string rewriting systems preserve regularity ⋮ Cancellation rules and extended word problems ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems ⋮ FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS ⋮ Bottom-up rewriting for words and terms ⋮ On characterizations of recursively enumerable languages ⋮ Automatic Termination ⋮ On regularity of context-free languages ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Rational subsets of polycyclic monoids and valence automata ⋮ Infinite regular Thue systems ⋮ Undecidable questions related to Church-Rosser Thue systems ⋮ Homomorphic images of sentential form languages defined by semi-Thue systems ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems ⋮ Non-finitely generated maximal subgroups of context-free monoids ⋮ Conjugacy in monoids with a special Church-Rosser presentation is decidable ⋮ Complexity results on the conjugacy problem for monoids ⋮ On one-relator groups and units of special one-relation inverse monoids
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Testing for the Church-Rosser property
- On a special monoid with a single defining relation
- Une généralisation des ensembles de Dyck
- On theories with a combinatorial definition of 'equivalence'
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- How to Make Arbitrary Grammars Look Like Context-Free Grammars
- The Hardest Context-Free Language
- Partial algorithm problems for context free languages
- Full AFLs and nested iterated substitution
- A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
- Tree-Manipulating Systems and Church-Rosser Theorems
