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

DOI10.1137/0214044MaRDI QIDQ3698326zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

finite automataregular expressionsequivalence problemnondeterministic finite automatoncontainment problemregular grammarsfinite state transducersdegree of ambiguityhomogeneous linear difference equationsaccepting state transition sequenceambiguous automata

Mathematics Subject Classification ID

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

Recommendations

• The parallel complexity of finite-state automata problems
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Deciding equivalence of finite tree automata
• On the degree of ambiguity of finite automata
• scientific article; zbMATH DE number 4049114

Cited in

(58)

• A pattern logic for automata with outputs
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• Singly exponential translation of alternating weak Büchi automata to unambiguous Büchi automata
• On degrees of ambiguity for Büchi tree automata
• Descriptional and computational complexity of finite automata -- a survey
• Concise representations of regular languages by degree and probabilistic finite automata
• Transforming a single-valued transducer into a Mealy machine
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Unambiguous languages exhaust the index hierarchy
• On the degree of ambiguity of finite automata
• Deciding equivalence of finite tree automata
• A note on finite-valued and finitely ambiguous transducers
• Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata
• Foundations of Boolean stream runtime verification
• Queries on XML streams with bounded delay and concurrency
• Automata on infinite trees
• \((k,l)\)-unambiguity and quasi-deterministic structures: an alternative for the determinization
• The containment problem for unambiguous register automata
• Deterministic realization of nondeterministic computations with a low measure of nondeterminism
• Effective entropies and data compression
• Unambiguous finite automata over a unary alphabet
• Descriptional and Computational Complexity of Finite Automata
• Bounded Delay and Concurrency for Earliest Query Answering
• In memoriam Chandra Kintala
• A special case of a unary regular language containment
• On the existence of lookahead delegators for nfa
• The inclusion problem for some subclasses of context-free languages
• The parallel complexity of finite-state automata problems
• scientific article; zbMATH DE number 1416105 (Why is no real title available?)
• Universality Problem for Unambiguous VASS
• Operations on Unambiguous Finite Automata
• Unambiguous constrained automata
• On the minimization of XML schemas and tree automata for unranked trees
• Choice functions and well-orderings over the infinite binary tree
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• Ambiguity of the multiple interpretations on regular languages
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Lower bounds for the size of deterministic unranked tree automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Unambiguity in automata theory
• Unambiguous constrained automata
• A probabilistic approach to navigation in Hypertext
• On path equivalence of nondeterministic finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Ambiguity and structural ambiguity of symmetric difference NFAs
• Weak minimization of DFA -- an algorithm and applications
• Operations on Unambiguous Finite Automata
• The tractability frontier for NFA minimization
• On equality of multiplicity sets of regular languages
• General Algorithms for Testing the Ambiguity of Finite Automata
• Ambiguity and communication
• scientific article; zbMATH DE number 871236 (Why is no real title available?)
• scientific article; zbMATH DE number 7407790 (Why is no real title available?)
• Regular Programming for Quantitative Properties of Data Streams
• The containment problem for unambiguous register automata and unambiguous timed automata
• \((k,l)\)-unambiguity and quasi-deterministic structures
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes

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)