The average state complexity of rational operations on finite languages

DOI10.1142/S0129054110007398MaRDI QIDQ3586401zbMATH OpenOpenAlexFDO

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

Publication date 6 September 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054110007398

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The Average State Complexity of the Star of a Finite Set of Words Is Linear
• On the average state and transition complexity of finite languages
• Publication:4941905
• Intersection and union of regular languages and state complexity
• State complexity of unique rational operations

Cites work

• scientific article; zbMATH DE number 3943051 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Complexity of the Frobenius problem
• On the average state and transition complexity of finite languages
• Parsing with a finite dictionary
• The state complexities of some basic operations on regular languages

Cited in

(6)

• A hitchhiker's guide to descriptional complexity through analytic combinatorics
• More on deterministic and nondeterministic finite cover automata (extended abstract)
• On the average state and transition complexity of finite languages
• More on deterministic and nondeterministic finite cover automata
• State complexity of unique rational operations
• The Average State Complexity of the Star of a Finite Set of Words Is Linear

This page was built for publication: The average state complexity of rational operations on finite languages

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