The Average State Complexity of the Star of a Finite Set of Words Is Linear

DOI10.1007/978-3-540-85780-8_10zbMath1161.68510OpenAlexW1483856029MaRDI QIDQ3533005

Frédérique Bassino, Laura Giambruno, Cyril Nicaud

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_10

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• The state complexities of some basic operations on regular languages
• Complexity of the Frobenius problem
• Parsing with a finite dictionary
• The Frobenius Problem in a Free Monoid
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Average State Complexity of the Star of a Finite Set of Words Is Linear