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

DOI10.1007/978-3-540-85780-8_10MaRDI QIDQ3533005zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• State complexity of star and square of union of \(k\) regular languages
• On the average state and transition complexity of finite languages
• The State Complexity of Lexicographically Smallest Words and Computing Successors
• The state complexity of star-complement-star
• State complexity of union and intersection of star on \(k\) regular languages
• State complexity of star of union and square of union on \textit{k} regular languages
• A characterization of words of linear complexity
• The average state complexity of rational operations on finite languages
• The ranges of state complexities for complement, star, and reversal of regular languages
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 2081044 (Why is no real title available?)
• scientific article; zbMATH DE number 1458676 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Analytic combinatorics
• Complexity of the Frobenius problem
• Parsing with a finite dictionary
• Regular expressions: new results and open problems
• The Frobenius problem in a free monoid
• The state complexities of some basic operations on regular languages

Cited in

(2)

• On the average state and transition complexity of finite languages
• The average state complexity of rational operations on finite languages

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

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