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

DOI10.1016/0304-3975(93)90023-MzbMath0798.68088MaRDI QIDQ1210296

Jean Néraud

Publication date: 24 May 1993

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

zbMATH Keywords

complexityrankfree semigroup

Mathematics Subject Classification ID

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

Related Items

Primitive sets of words ⋮ The intersection of \(3\)-maximal submonoids

Cites Work

• On the defect theorem and simplifiability
• Sur le théorème du defaut
• On the rank of the subsets of a free monoid
• On the deficit of a finite set of words
• Elementariness of a finite set of words is co-NP-complete
• Fast Pattern Matching in Strings
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item