NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
From MaRDI portal
Publication:5696955
DOI10.1142/S0129054103002199zbMath1101.68657OpenAlexW2011252827WikidataQ57380771 ScholiaQ57380771MaRDI QIDQ5696955
Publication date: 19 October 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054103002199
Related Items (78)
State complexity of permutation on finite languages over a binary alphabet ⋮ The chop of languages ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ State complexity of operations on input-driven pushdown automata ⋮ Nondeterministic complexity of operations on free and convex languages ⋮ Descriptional complexity of bounded context-free languages ⋮ State complexity of combined operations for suffix-free regular languages ⋮ ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION ⋮ Nondeterministic operational complexity in subregular languages ⋮ State complexity of inversion operations ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Unambiguous finite automata over a unary alphabet ⋮ Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification ⋮ A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity ⋮ Operational complexity: NFA-to-DFA trade-off ⋮ State complexity of cyclic shift ⋮ State Complexity of Insertion ⋮ Concatenation of regular languages and descriptional complexity ⋮ Nondeterministic state complexity of star-free languages ⋮ The size-cost of Boolean operations on constant height deterministic pushdown automata ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Unnamed Item ⋮ On the State Complexity of Complements, Stars, and Reversals of Regular Languages ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES ⋮ The pseudopalindromic completion of regular languages ⋮ Operations on Unambiguous Finite Automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ NON-UNIQUENESS AND RADIUS OF CYCLIC UNARY NFAs ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ STATE COMPLEXITY AND APPROXIMATION ⋮ Transition complexity of language operations ⋮ On the state complexity of operations on two-way finite automata ⋮ Two double-exponential gaps for automata with a limited pushdown ⋮ Lower bounds for the transition complexity of NFAs ⋮ THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ State complexity of some operations on binary regular languages ⋮ Complementing unary nondeterministic automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ State complexity of finite partial languages ⋮ Nondeterministic state complexity of nested word automata ⋮ Estimation of state complexity of combined operations ⋮ Operational state complexity of nested word automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Power, positive closure, and quotients on convex languages ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ State Trade-Offs in Unranked Tree Automata ⋮ Operational Accepting State Complexity: The Unary and Finite Case ⋮ State Complexity of Nested Word Automata ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ Regular expression length via arithmetic formula complexity ⋮ STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION ⋮ Operations on Unambiguous Finite Automata ⋮ State complexity of power ⋮ State complexity of unique rational operations ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Nondeterministic Complexity of Operations on Closed and Ideal Languages ⋮ State complexity of basic operations on suffix-free regular languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ Nondeterministic Tree Width of Regular Languages ⋮ Complement on Free and Ideal Languages ⋮ Deterministic blow-ups of minimal NFA's ⋮ State complexity of unambiguous operations on finite automata ⋮ Undecidability of state complexity ⋮ State complexity of partial word finite automata ⋮ State complexity of union and intersection on graph-walking automata ⋮ Image-binary automata ⋮ Operations on subregular languages and nondeterministic state complexity ⋮ State complexity of finite partial languages
Cites Work
- Unnamed Item
- Partial orders on words, minimal elements of regular languages, and state complexity
- Finite automata and unary languages
- Lower bounds on the size of sweeping automata
- Succinct representation of regular languages by Boolean automata
- On the equivalence, containment, and covering problems for the regular and context-free languages
- The state complexities of some basic operations on regular languages
- Optimal Simulations between Unary Automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Minimal NFA Problems are Hard
- State-complexity of finite-state devices, state compressibility and incompressibility
- Minimal cover-automata for finite languages
This page was built for publication: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
