Elementariness of a finite set of words is co-NP-complete
From MaRDI portal
Publication:3484360
DOI10.1051/ita/1990240504591zbMath0704.68065MaRDI 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
The Minimum Substring Cover Problem, The minimum substring cover problem, A string-matching interpretation of the equation \(x^ m y^ n = z^ p\), On the rank of the subsets of a free monoid, Deciding whether a finite set of words has rank at most two, Locally complete sets and finite decomposable codes, On the deficit of a finite set of words, Many aspects of defect theorems, Primitive sets of words
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