Ambiguity in Graphs and Expressions

DOI10.1109/T-C.1971.223204zbMath0222.94067MaRDI QIDQ5628042

Ronald V. Book, Sheila A. Greibach, Gene Ott, Shimon Even

Publication date: 1971

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Translating regular expressions into small ε-free nondeterministic finite automata, Comparing the size of NFAs with and without \(\epsilon\)-transitions, Deciding determinism of caterpillar expressions, Valuations, regular expressions, and fractal geometry, The validation of SGML content models, From Ambiguous Regular Expressions to Deterministic Parsing Automata, Deterministic regular languages, Deterministic Caterpillar Expressions, Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions, Automata-based symbolic string analysis for vulnerability detection, The inclusion problem for regular expressions, One-unambiguous regular languages, One-unambiguous regular languages, Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata, Attribute grammars for unranked trees as a query language for structured documents, From regular expressions to finite automata^∗, A deterministic parsing algorithm for ambiguous regular expressions, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity, Regular Programming for Quantitative Properties of Data Streams, State complexity of unique rational operations, Derivative-Based Diagnosis of Regular Expression Ambiguity, A homomorphism theorem for weighted context-free grammars, Free and almost-free subsemigroups of a free semigroup, Solving string problems on graphs using the labeled direct product, Regular expressions into finite automata, The base of the intersection of two free submonoids, Algebraic aspects of families of fuzzy languages