ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION

DOI10.1142/S0129054107004917zbMath1149.68397OpenAlexW1974278282MaRDI QIDQ3503086

Kai Salomaa, Sheng Zu

Publication date: 20 May 2008

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

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

zbMATH Keywords

regular languagesestimation methodsnondeterministic state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (15)

Undecidability of State Complexities Using Mirror Images ⋮ Operational State Complexity of Subtree-Free Regular Tree Languages ⋮ State Complexity of Boundary of Prefix-Free Regular Languages ⋮ State complexity of combined operations for suffix-free regular languages ⋮ State complexity of inversion operations ⋮ State Complexity of Regular Tree Languages for Tree Matching ⋮ STATE COMPLEXITY AND APPROXIMATION ⋮ State complexity of basic language operations combined with reversal ⋮ Estimation of state complexity of combined operations ⋮ State Complexity of Nested Word Automata ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ State complexity of power ⋮ Composition and orbits of language operations: finiteness and upper bounds ⋮ Undecidability of state complexity ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partial orders on words, minimal elements of regular languages, and state complexity
• The state complexity of \(L^{2}\) and \(L^k\)
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• State complexity of some operations on binary regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES

This page was built for publication: ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION