On the State Complexity of Star of Union and Star of Intersection

DOI10.3233/FI-2011-502zbMath1252.68175OpenAlexW1784335425MaRDI QIDQ2895795

Alexander Okhotin, Galina Jirásková

Publication date: 4 July 2012

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2011-502

zbMATH Keywords

finite automatastate complexitydescriptional complexitycombined operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items

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, The exact state complexity for the composition of root and reversal, State complexity of union and intersection of star on \(k\) regular languages, Operational state complexity revisited: the contribution of monsters and modifiers, State complexity of combined operations with two basic operations, Unnamed Item, State complexity of union and intersection of square and reversal on \(k\) regular languages, State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal, State Complexity of Catenation Combined with Union and Intersection, State complexity of power, Unnamed Item, State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures