A note on decidability questions on presentations of word semigroups
From MaRDI portal
Publication:1391138
DOI10.1016/S0304-3975(96)00311-8zbMath0901.68096MaRDI QIDQ1391138
Juhani Karhumäki, Christian Choffrut, Tero J.Harju
Publication date: 22 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q45: Formal languages and automata
Related Items
ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS, Inverse Subsemigroups of the Monogenic Free Inverse Semigroup, Unique decipherability in the monoid of languages: an application of rational relations, The minimum substring cover problem, On well quasi orders of free monoids, Periodicity and the golden ratio, Generalized factorizations of words and their algorithmic properties, Partial words and a theorem of Fine and Wilf, On repetition-free binary words of minimal density, A note on decidability questions on presentations of word semigroups, The homomorphism problem for trace monoids., On lengths of words in context-free languages, Context-free languages of sub-exponential growth, Computing by commuting., A multidimensional critical factorization theorem, Unique Decipherability in the Monoid of Languages: An Application of Rational Relations
Cites Work
- Systems of equations over a free monoid and Ehrenfeucht's conjecture
- A proof of Ehrenfeucht's conjecture
- On the defect theorem and simplifiability
- A note on decidability questions on presentations of word semigroups
- A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
- On finitely generated subsemigroups of a free semigroup
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item