On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata

DOI10.1137/0214044zbMath0577.68074OpenAlexW2059200976MaRDI QIDQ3698326

Richard E. Stearns, Harry B. III Hunt

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214044

zbMATH Keywords

regular expressions finite automata equivalence problem nondeterministic finite automaton containment problem regular grammars finite state transducers degree of ambiguity homogeneous linear difference equations accepting state transition sequence ambiguous automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (45)

Foundations of Boolean stream runtime verification ⋮ A note on finite-valued and finitely ambiguous transducers ⋮ On path equivalence of nondeterministic finite automata ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ From LTL to unambiguous Büchi automata via disambiguation of alternating automata ⋮ Deterministic realization of nondeterministic computations with a low measure of nondeterminism ⋮ Choice functions and well-orderings over the infinite binary tree ⋮ On the minimization of XML schemas and tree automata for unranked trees ⋮ Deciding equivalence of finite tree automata ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ The tractability frontier for NFA minimization ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ Unambiguous finite automata over a unary alphabet ⋮ Unnamed Item ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Ambiguity and structural ambiguity of symmetric difference NFAs ⋮ Operations on Unambiguous Finite Automata ⋮ On the degree of ambiguity of finite automata ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY ⋮ The inclusion problem for some subclasses of context-free languages ⋮ The parallel complexity of finite-state automata problems ⋮ Ambiguity and communication ⋮ Weak minimization of DFA -- an algorithm and applications ⋮ Queries on XML streams with bounded delay and concurrency ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ ON THE EXISTENCE OF LOOKAHEAD DELEGATORS FOR NFA ⋮ Regular Programming for Quantitative Properties of Data Streams ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Bounded Delay and Concurrency for Earliest Query Answering ⋮ On degrees of ambiguity for Büchi tree automata ⋮ Operations on Unambiguous Finite Automata ⋮ Effective entropies and data compression ⋮ Transforming a single-valued transducer into a Mealy machine ⋮ Universality Problem for Unambiguous VASS ⋮ A probabilistic approach to navigation in Hypertext ⋮ Automata on infinite trees ⋮ Unambiguity in Automata Theory ⋮ Unnamed Item ⋮ A Pattern Logic for Automata with Outputs ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Concise representations of regular languages by degree and probabilistic finite automata ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

This page was built for publication: On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata