Partial orders on words, minimal elements of regular languages, and state complexity
From MaRDI portal
Publication:688156
DOI10.1016/0304-3975(93)90160-UzbMath0786.68071OpenAlexW1991409518WikidataQ57380781 ScholiaQ57380781MaRDI QIDQ688156
Publication date: 18 May 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90160-u
Related Items
Descriptional Complexity of Input-Driven Pushdown Automata, State-complexity of finite-state devices, state compressibility and incompressibility, COMPLEXITY IN UNION-FREE REGULAR LANGUAGES, State complexity of combined operations, State complexity of operations on input-driven pushdown automata, On complementing unambiguous automata and graphs with many cliques and cocliques, Improved complement for two-way alternating automata, ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION, Unnamed Item, On the state complexity of closures and interiors of regular languages with subwords and superwords, The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic, The size of power automata., Converting finite width AFAs to nondeterministic and universal finite automata, Unambiguous finite automata over a unary alphabet, A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity, State complexity of cyclic shift, An extension of a Y. C. Yang theorem, Concatenation of regular languages and descriptional complexity, Unnamed Item, Two-way automata and length-preserving homomorphisms, On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, On the State Complexity of Operations on Two-Way Finite Automata, DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET, Operations on Unambiguous Finite Automata, NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES, A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton, Succinct description of regular languages by weak restarting automata, On the state complexity of operations on two-way finite automata, Intersection and union of regular languages and state complexity, THE RANGES OF STATE COMPLEXITIES FOR COMPLEMENT, STAR, AND REVERSAL OF REGULAR LANGUAGES, On the descriptional complexity of finite automata with modified acceptance conditions, State complexity of some operations on binary regular languages, Complementing unary nondeterministic automata, On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, The robustness of LWPP and WPP, with an application to graph reconstruction, Complement for two-way alternating automata, STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION, MAGIC NUMBERS AND TERNARY ALPHABET, Operations on Unambiguous Finite Automata, Decimations of languages and state complexity, Magic Numbers and Ternary Alphabet, 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, BÜCHI COMPLEMENTATION MADE TIGHTER, On NFAs where all states are final, initial, or both, Nondeterministic complexity in subclasses of convex languages, Descriptional complexity of regular languages, Complement on Free and Ideal Languages, Deterministic blow-ups of minimal NFA's, State complexity of unambiguous operations on finite automata, State complexity of union and intersection on graph-walking automata
Cites Work
- Unnamed Item
- Unnamed Item
- Minimal strings in a regular language with respect to a partial order on the alphabet
- Succinct representation of regular languages by Boolean automata
- The theory of well-quasi-ordering: a frequently discovered concept
- Alternation
- State-complexity of finite-state devices, state compressibility and incompressibility
- Nondeterminism and the size of two way finite automata
- Ordering by Divisibility in Abstract Algebras
