scientific article
From MaRDI portal
Publication:4040284
zbMath0651.68007MaRDI QIDQ4040284
Seppo Sippu, Eljas Soisalon-Soininen
Publication date: 5 June 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitycontext-free grammarsexercisesderivational complexitypushdown transducerparsing theorycontext-free language recognitionbibliographical commentsLL(k) parsers
Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items
Translating regular expressions into small ε-free nondeterministic finite automata ⋮ One-unambiguity of regular expressions with numeric occurrence indicators ⋮ Comparing the size of NFAs with and without \(\epsilon\)-transitions ⋮ The language intersection problem for non-recursive context-free grammars ⋮ Graph Parsing as Graph Transformation ⋮ Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars. ⋮ Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions ⋮ P-hardness of the emptiness problem for visibly pushdown languages ⋮ A characterization of Thompson digraphs. ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ Follow automata. ⋮ Bounded-connect noncanonical discriminating-reverse parsers. ⋮ Reducing NFAs by invariant equivalences. ⋮ Postfix automata ⋮ Computation of distances for regular and context-free probabilistic languages ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ Partial derivatives of regular expressions and finite automaton constructions ⋮ Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata ⋮ The IELR(1) algorithm for generating minimal LR(1) parser tables for non-LR(1) grammars with conflict resolution ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs ⋮ On parsing LL-languages ⋮ On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited ⋮ Reasoning about strings in databases ⋮ Measuring nondeterminism in pushdown automata ⋮ Descriptional complexity of regular languages ⋮ Producing the left parse during bottom-up parsing ⋮ Conversion of regular expressions into realtime automata ⋮ Measuring nondeterminism in pushdown automata ⋮ Checking determinism of regular expressions with counting ⋮ Regular expressions into finite automata ⋮ Size/lookahead tradeoff for \(LL(k)\)-grammars ⋮ Approximate matching between a context-free grammar and a finite-state automaton
