ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
From MaRDI portal
Publication:3503086
DOI10.1142/S0129054107004917zbMath1149.68397OpenAlexW1974278282MaRDI QIDQ3503086
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
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