A note on decidability questions on presentations of word semigroups
From MaRDI portal
Publication:1391138
DOI10.1016/S0304-3975(96)00311-8zbMath0901.68096MaRDI QIDQ1391138
Tero J.Harju, Christian Choffrut, Juhani Karhumäki
Publication date: 22 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
A note on decidability questions on presentations of word semigroups, Unique decipherability in the monoid of languages: an application of rational relations, On recognising words that are squares for the shuffle product, The homomorphism problem for trace monoids., Algorithmic and algebraic aspects of unshuffling permutations, The minimum substring cover problem, Computing by commuting., Unique Decipherability in the Monoid of Languages: An Application of Rational Relations, Inverse Subsemigroups of the Monogenic Free Inverse Semigroup, On well quasi orders of free monoids, Periodicity and the golden ratio, Reachability via Cooperating Morphisms, On finitely generated submonoids of virtually free groups, Finite transducers and rational transductions, On lengths of words in context-free languages, 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 multidimensional critical factorization theorem, ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS, Context-free languages of sub-exponential growth
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
