Deciding whether a finite set of words has rank at most two
type: Item
instance of: scholarly article
title: Deciding whether a finite set of words has rank at most two
zbMATH Open document ID: 0798.68088
DOI: 10.1016/0304-3975(93)90023-M
published in: Theoretical Computer Science
publication date: 1993-05-24T00:00:00Z
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\).
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 178040
zbMATH Keywords: free semigroup
zbMATH Keywords: complexity
zbMATH Keywords: rank
author: J. Néraud
reviewed by: Tero Harju
MaRDI profile type: Publication
cites work: Q4430300
cites work: Sur le théorème du defaut
cites work: Q3901701
cites work: On the defect theorem and simplifiability
cites work: Fast Pattern Matching in Strings
cites work: Q4529547
cites work: Elementariness of a finite set of words is co-NP-complete
cites work: On the deficit of a finite set of words
cites work: On the rank of the subsets of a free monoid
cites work: Q4385527
cites work: Q3921412
cites work: Q3737376
cites work: Q5625457
description: scientific article; zbMATH DE number 178040