On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
DOI10.1137/0214044zbMATH Open0577.68074OpenAlexW2059200976MaRDI QIDQ3698326FDOQ3698326
Authors: R. E. Stearns, H. 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
Recommendations
finite automataregular expressionsequivalence problemnondeterministic finite automatoncontainment problemregular grammarsfinite state transducersdegree of ambiguityhomogeneous linear difference equationsaccepting state transition sequenceambiguous automata
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Cited In (59)
- Singly exponential translation of alternating weak Büchi automata to unambiguous Büchi automata
- A pattern logic for automata with outputs
- A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
- From LTL to unambiguous Büchi automata via disambiguation of alternating automata
- On equality of multiplicity sets of regular languages
- Deterministic realization of nondeterministic computations with a low measure of nondeterminism
- Ambiguity and communication
- Deciding equivalence of finite tree automata
- Unambiguous constrained automata
- Operations on Unambiguous Finite Automata
- Unambiguous finite automata over a unary alphabet
- Weak minimization of DFA -- an algorithm and applications
- Regular Programming for Quantitative Properties of Data Streams
- Transforming a single-valued transducer into a Mealy machine
- On the degree of ambiguity of finite automata
- Queries on XML streams with bounded delay and concurrency
- Foundations of Boolean stream runtime verification
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Ambiguity and structural ambiguity of symmetric difference NFAs
- \((k,l)\)-unambiguity and quasi-deterministic structures: an alternative for the determinization
- From LTL to unambiguous Büchi automata via disambiguation of alternating automata
- Lower bounds for the size of deterministic unranked tree automata
- On the minimization of XML schemas and tree automata for unranked trees
- Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata
- Automata on infinite trees
- The parallel complexity of finite-state automata problems
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- The tractability frontier for NFA minimization
- On the existence of lookahead delegators for nfa
- Choice functions and well-orderings over the infinite binary tree
- Operations on Unambiguous Finite Automata
- \((k,l)\)-unambiguity and quasi-deterministic structures
- Descriptional and Computational Complexity of Finite Automata
- Communication complexity method for measuring nondeterminism in finite automata
- Universality Problem for Unambiguous VASS
- Ambiguity of the multiple interpretations on regular languages
- Unambiguous constrained automata
- A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
- Unambiguous languages exhaust the index hierarchy
- The containment problem for unambiguous register automata
- Effective entropies and data compression
- In memoriam Chandra Kintala
- The containment problem for unambiguous register automata and unambiguous timed automata
- A special case of a unary regular language containment
- Title not available (Why is that?)
- Concise representations of regular languages by degree and probabilistic finite automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Descriptional and computational complexity of finite automata -- a survey
- Unambiguity in automata theory
- On path equivalence of nondeterministic finite automata
- On degrees of ambiguity for Büchi tree automata
- A probabilistic approach to navigation in Hypertext
- General Algorithms for Testing the Ambiguity of Finite Automata
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Bounded Delay and Concurrency for Earliest Query Answering
- A note on finite-valued and finitely ambiguous transducers
- The inclusion problem for some subclasses of context-free languages
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3698326)
