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

DOI10.1007/978-3-540-85780-8_10zbMATH Open1161.68510OpenAlexW1483856029MaRDI QIDQ3533005FDOQ3533005

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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The state complexities of some basic operations on regular languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Regular expressions: new results and open problems
• Complexity of the Frobenius problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Frobenius Problem in a Free Monoid
• Parsing with a finite dictionary

Cited In (1)

• On the average state and transition complexity of 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)