On equations for regular languages, finite automata, and sequential networks
From MaRDI portal
Publication:600253
DOI10.1016/0304-3975(80)90069-9zbMath0415.68023OpenAlexW1975653808MaRDI QIDQ600253
Ernst L. Leiss, Janusz A. Brzozowski
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(80)90069-9
language equationsBoolean automatonnondeterministic automaton representationrepresenting regular languagessequential networks
Related Items (58)
Concurrent Dynamic Algebra ⋮ On the closure properties of linear conjunctive languages. ⋮ Taming Multirelations ⋮ ON THE ROOT OF LANGUAGES ⋮ Language equations over a one-letter alphabet with union, concatenation and star: A complete solution ⋮ Unrestricted complementation in language equations over a one-letter alphabet ⋮ Generalized language equations with multiple solutions ⋮ A symbolic decision procedure for symbolic alternating finite automata ⋮ State-complexity of finite-state devices, state compressibility and incompressibility ⋮ Construction of a Deterministicω-Automaton Using Derivatives ⋮ Alternating automata on infinite trees ⋮ Succinct representation of regular sets using gotos and Boolean variables ⋮ Manipulation of regular expressions using derivatives: an overview ⋮ Equations and regular-like expressions for afa ⋮ On the role of complementation in implicit language equations and relations ⋮ Automatic winning shifts ⋮ Kleene closure and state complexity ⋮ Decision procedures for inductive Boolean functions based on alternating automata ⋮ The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic ⋮ From bidirectionality to alternation. ⋮ Model checking open systems with alternating projection temporal logic ⋮ A Nivat Theorem for Weighted Alternating Automata over Commutative Semirings ⋮ On generalized language equations ⋮ Succinct representation of regular languages by Boolean automata ⋮ Operations on Boolean and Alternating Finite Automata ⋮ Two-way automata and length-preserving homomorphisms ⋮ Generalized acceptance, succinctness and supernondeterministic finite automata. ⋮ Descriptional Complexity of the Forever Operator ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ Implicit language equations: existence and uniqueness of solutions ⋮ Rewriting extended regular expressions ⋮ Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations ⋮ Transformation from PLTL to automata via NFGs ⋮ Linear Parsing Expression Grammars ⋮ Alternating automata and temporal logic normal forms ⋮ Decision problems for language equations ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Alternation in two-way finite automata ⋮ Square on Deterministic, Alternating, and Boolean Finite Automata ⋮ Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ A Rice-style theorem for parallel automata ⋮ The complexity of concatenation on deterministic and alternating finite automata ⋮ Domain mu-calculus ⋮ BOOLEAN FUZZY SETS ⋮ Alternating automata: Unifying truth and validity checking for temporal logics ⋮ Descriptional complexity of regular languages ⋮ Language equations ⋮ Alternating finite automata and star-free languages ⋮ Efficient implementation of regular languages using reversed alternating finite automata ⋮ Implementing automata. Selected papers from the 2nd international workshop, WIA '97, Univ. of Western Ontario, London, Ontario, Canada, September 18--20, 1997 ⋮ On the simplest centralizer of a language ⋮ Trace semantics via determinization ⋮ On classes of tractable unrestricted regular expressions ⋮ Succinct representation of regular languages by Boolean automata. II ⋮ The commutation of finite sets: A challenging problem ⋮ Inferring program specifications in polynomial-time ⋮ Unresolved systems of language equations: expressive power and decision problems
Cites Work
This page was built for publication: On equations for regular languages, finite automata, and sequential networks
