Succinct representation of regular languages by Boolean automata
From MaRDI portal
Publication:1151754
DOI10.1016/S0304-3975(81)80005-9zbMath0458.68017OpenAlexW2063230375WikidataQ56750270 ScholiaQ56750270MaRDI QIDQ1151754
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(81)80005-9
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, On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs, Inferring regular languages and \(\omega\)-languages, An approximation algorithm for state minimization in 2-MDFAs, State complexity of operations on input-driven pushdown automata, Performing regular operations with 1-limited automata, On the state complexity of reversals of regular languages, Complexity of suffix-free regular languages, Counting with Probabilistic and Ultrametric Finite Automata, Complexity of Suffix-Free Regular Languages, ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION, State complexity of inversion operations, Prefix-free languages: left and right quotient and reversal, The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic, Existential and universal width of alternating finite automata, Complexity of exclusive nondeterministic finite automata, On the translation of automata to linear temporal logic, Operational complexity in subregular classes, Operations on Boolean and Alternating Finite Automata, Concatenation of regular languages and descriptional complexity, Reversal of binary regular languages, Descriptional complexity of two-way pushdown automata with restricted head reversals, Two-way automata and length-preserving homomorphisms, On the State Complexity of Operations on Two-Way Finite Automata, Generalized acceptance, succinctness and supernondeterministic finite automata., Operations on Unambiguous Finite Automata, NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES, DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY, Intersection and union of regular languages and state complexity, Partial orders on words, minimal elements of regular languages, and state complexity, State complexity of some operations on binary regular languages, Complementing unary nondeterministic automata, On binary circle plus operator \(\oplus\)-NFAs and succinct descriptions of regular languages, Descriptional and computational complexity of finite automata -- a survey, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Alternation in two-way finite automata, Note on Reversal of Binary Regular Languages, Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals, Square on Deterministic, Alternating, and Boolean Finite Automata, Descriptional and Computational Complexity of Finite Automata, State Complexity of Combined Operations for Prefix-Free Regular Languages, STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION, On degrees of ambiguity for Büchi tree automata, Operations on Unambiguous Finite Automata, The complexity of concatenation on deterministic and alternating finite automata, Concatenation of Regular Languages and Descriptional Complexity, Domain mu-calculus, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Self-Verifying Finite Automata and Descriptional Complexity, Descriptional Complexity of Bounded Regular Languages, State complexity of basic operations on suffix-free regular languages, Descriptional complexity of regular languages, Alternating finite automata and star-free languages, Efficient implementation of regular languages using reversed alternating finite automata, Complexity and succinctness issues for linear-time hybrid logics, Unambiguity in Automata Theory, Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997, Unnamed Item, The Ranges of Accepting State Complexities of Languages Resulting from Some Operations, On classes of tractable unrestricted regular expressions, Concise representations of regular languages by degree and probabilistic finite automata, Succinct representation of regular languages by Boolean automata. II, The state complexities of some basic operations on regular languages
Cites Work
