State complexity of combined operations with union, intersection, star and reversal

MaRDI QIDQ2893301zbMATH OpenFDO

Authors Sheng Yu, Yuan Gao

Publication date 20 June 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL http://iospress.metapress.com/content/k27w5577q6811063/fulltext.html

zbMATH Keywords

finite automataregular languagescombined operationsstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of four combined operations composed of union, intersection, star and reversal
• State complexity of combined operations with two basic operations
• State complexity of union and intersection of star on \(k\) regular languages
• State complexity of basic language operations combined with reversal
• State complexity of combined operations

Cited in

(17)

• State complexity of star of union and square of union on \textit{k} regular languages
• State complexity of combined operations for suffix-free regular languages
• State complexity of combined operations with two basic operations
• Incomplete transition complexity of some basic operations
• State complexity of basic language operations combined with reversal
• The ranges of accepting state complexities of languages resulting from some operations
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• The state complexity of two combined operations: star of catenation and star of reversal
• State complexity of some operations on binary regular languages
• Undecidability of the state complexity of composed regular operations
• State complexity of combined operations
• State complexity of star and square of union of \(k\) regular languages
• State complexity of four combined operations composed of union, intersection, star and reversal
• On the state complexity of star of union and star of intersection
• Universal witnesses for state complexity of Boolean operations and concatenation combined with star
• Universal witnesses for state complexity of basic operations combined with reversal
• Unrestricted state complexity of binary operations on regular languages

This page was built for publication: State complexity of combined operations with union, intersection, star and reversal

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