Deciding whether a finite set of words has rank at most two

DOI10.1016/0304-3975(93)90023-MMaRDI QIDQ1210296zbMATH OpenFDO

Authors J. Néraud

Publication date 24 May 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90023-M

zbMATH Keywords

complexityfree semigrouprank

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Formal languages and automata (68Q45)

Review text

Let \(X\subseteq A^*\) be a finite set of words over the alphabet \(A\). The rank \(r(X)\) of \(X\) is the smallest size of a set \(Y\subseteq A^*\) of words such that \(X\subseteq Y^*\). The author presents an algorithm to check the condition \(r(X)\leq 2\). This algorithm works in \(O(n\log^ 2 m)\) time, where \(n\) is the sum of the lengths of words in \(X\) and \(m\) is the length of the longest word in \(X\).

Recommendations

• Elementariness of a finite set of words is co-NP-complete
• scientific article; zbMATH DE number 17550
• On sets of words of rank two
• The finite basis problem for words with at most two non-linear variables.
• On the deficit of a finite set of words

Cites work

• Elementariness of a finite set of words is co-NP-complete
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 3970684 (Why is no real title available?)
• scientific article; zbMATH DE number 3710436 (Why is no real title available?)
• scientific article; zbMATH DE number 3734202 (Why is no real title available?)
• scientific article; zbMATH DE number 1142311 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3350192 (Why is no real title available?)
• On the defect theorem and simplifiability
• On the deficit of a finite set of words
• On the rank of the subsets of a free monoid
• Sur le théorème du defaut

Cited in

(6)

• The intersection of 3-maximal submonoids
• On sets of words of rank two
• Primitive sets of words
• Elementariness of a finite set of words is co-NP-complete
• scientific article; zbMATH DE number 17550 (Why is no real title available?)
• Automatic sequences of rank two

This page was built for publication: Deciding whether a finite set of words has rank at most two

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210296)