A note on decidability questions on presentations of word semigroups

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)

zbMATH Keywords

\(F\)-semigroups

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS, Reachability via Cooperating Morphisms, 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