scientific article; zbMATH DE number 4049114

MaRDI QIDQ3786002zbMATH OpenFDO

Authors Oscar H. Ibarra, B. Ravikumar

Publication date 1987

zbMATH Keywords

hierarchyKolmogorov complexitynondeterministic finite automatonregular languagesize complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• On the degree of ambiguity of finite automata
• On the relation between ambiguity and nondeterminism in finite automata
• scientific article; zbMATH DE number 4001492
• Ambiguity, nondeterminism and state complexity of finite automata

Cited in

(6)

• Succinct representations of languages by DFA with different levels of reliability
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• scientific article; zbMATH DE number 2201365 (Why is no real title available?)
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3786002)