Elementariness of a finite set of words is co-NP-complete
From MaRDI portal
Publication:3484360
DOI10.1051/ita/1990240504591zbMath0704.68065OpenAlexW46283434MaRDI QIDQ3484360
Publication date: 1990
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92369
Related Items
Many aspects of defect theorems ⋮ Primitive sets of words ⋮ Efficient Computation of 2-Covers of a String. ⋮ A string-matching interpretation of the equation \(x^ m y^ n = z^ p\) ⋮ On the rank of the subsets of a free monoid ⋮ The minimum substring cover problem ⋮ Deciding whether a finite set of words has rank at most two ⋮ The Minimum Substring Cover Problem ⋮ On the deficit of a finite set of words ⋮ Locally complete sets and finite decomposable codes
Cites Work
- Sur le théorème du defaut
- Sur la détermination du rang d'une équation dans le monoide libre
- Elementary homomorphisms and a solution of the DOL sequence equivalence problem
- The decidability of the equivalence problem for DOL-systems
- THE PROBLEM OF SOLVABILITY OF EQUATIONS IN 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: Elementariness of a finite set of words is co-NP-complete