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 (22)
Free subsemigroups in topological semigroups ⋮ 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
This page was built for publication: A note on decidability questions on presentations of word semigroups
