NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
From MaRDI portal
(Redirected from Publication:5696955)
Recommendations
Cites work
- Finite automata and unary languages
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- Lower bounds on the size of sweeping automata
- Minimal cover-automata for finite languages
- Minimal NFA Problems are Hard
- On the equivalence, containment, and covering problems for the regular and context-free languages
- Optimal simulations between unary automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- State-complexity of finite-state devices, state compressibility and incompressibility
- Succinct representation of regular languages by Boolean automata
- The state complexities of some basic operations on regular languages
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
Cited in
(97)- State complexity of power
- State complexity of unique rational operations
- State complexity of basic operations on suffix-free regular languages
- An optimal lower bound for nonregular languages
- State complexity of some operations on binary regular languages
- Complementing unary nondeterministic automata
- Power, positive closure, and quotients on convex languages
- Descriptional complexity of regular languages
- 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
- NFA-to-DFA trade-off for regular operations
- Nondeterministic state complexity of nested word automata
- Determination of finite automata accepting subregular languages
- Estimation of state complexity of combined operations
- Operational state complexity of nested word automata
- Nondeterministic complexity in subclasses of convex languages
- State complexity of unambiguous operations on finite automata
- State complexity of permutation on finite languages over a binary alphabet
- The chop of languages
- State complexity of operations on input-driven pushdown automata
- Nondeterministic complexity of operations on free and convex languages
- Transition complexity of language operations
- Operations on Unambiguous Finite Automata
- Self-verifying finite automata and descriptional complexity
- Descriptional complexity of bounded regular languages
- Nondeterministic complexity of operations on closed and ideal languages
- Nondeterministic biautomata and their descriptional complexity
- Undecidability of state complexity
- State complexity of insertion
- Descriptional complexity of input-driven pushdown automata
- On inverse operations and their descriptional complexity
- Concatenation of Regular Languages and Descriptional Complexity
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Deterministic blow-ups of minimal NFA's
- ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
- State complexity of cyclic shift
- 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
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- State Complexity of Nested Word Automata
- State Complexity of Combined Operations for Prefix-Free Regular Languages
- scientific article; zbMATH DE number 4049104 (Why is no real title available?)
- Descriptional complexity of bounded context-free languages
- State complexity of combined operations for suffix-free regular languages
- Unambiguous finite automata over a unary alphabet
- 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
- scientific article; zbMATH DE number 1773094 (Why is no real title available?)
- Descriptional complexity of bounded regular languages
- Operations on Unambiguous Finite Automata
- The pseudopalindromic completion of regular languages
- Descriptional complexity of unambiguous input-driven pushdown automata
- State complexity and approximation
- On the state complexity of operations on two-way finite automata
- Two double-exponential gaps for automata with a limited pushdown
- The ranges of state complexities for complement, star, and reversal of regular languages
- Nondeterministic state complexity of proportional removals
- Nondeterministic biautomata and their descriptional complexity
- Complexity of operation problems
- 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
- Descriptional complexity of the forever operator
- Descriptional complexity of h-alternating finite automata
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- Regularity and size of set automata
- Nondeterministic tree width of regular languages
- Complement on free and ideal languages
- Descriptional and computational complexity of finite automata -- a survey
- Limitations of lower bound methods for deterministic nested word automata
- scientific article; zbMATH DE number 2213327 (Why is no real title available?)
- NON-UNIQUENESS AND RADIUS OF CYCLIC UNARY NFAs
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- Investigations on automata and languages over a unary alphabet
- Regular expression length via arithmetic formula complexity
- scientific article; zbMATH DE number 7770057 (Why is no real title available?)
- Nondeterministic operational complexity in subregular languages
- State complexity of finite partial languages
- 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
- Concatenation of regular languages and descriptional complexity
- Descriptional complexity of finite automata -- selected highlights
- Square, power, positive closure, and complementation on ordered and star-free languages
- Operational complexity: NFA-to-DFA trade-off
- Conversions between six models of finite automata
- 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
- Lower bounds for the transition complexity of NFAs
This page was built for publication: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696955)
