Recognition and parsing of context-free languages in time n3

DOI10.1016/S0019-9958(67)80007-XzbMath0149.24803WikidataQ56092150 ScholiaQ56092150MaRDI QIDQ5528645

Daniel H. Younger

Publication date: 1967

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

mathematical logic

Related Items (86)

The theory of languages ⋮ Pattern selector grammars and several parsing algorithms in the context- free style ⋮ Richard Bellman's contributions to computer science ⋮ Applications of scheduling theory to formal language theory ⋮ The principle of optimality in the design of efficient algorithms ⋮ A method for automatic construction of ontological knowledge bases. I: Development of a semantic-syntactic model of natural language ⋮ Earley’s Parsing Algorithm and k-Petri Net Controlled Grammars ⋮ Boolean grammars ⋮ A method for automatic construction of ontological knowledge bases. II: Automatic identification of semantic relations in ontological networks ⋮ A CKY parser for picture grammars ⋮ On parsing coupled-context-free languages ⋮ Finding the smallest binarization of a CFG is NP-hard ⋮ The theory of languages ⋮ EXPLOITING SYNTACTIC, SEMANTIC, AND LEXICAL REGULARITIES IN LANGUAGE MODELING VIA DIRECTED MARKOV RANDOM FIELDS ⋮ Super-pattern matching ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Recognition is not parsing - SPPF-style parsing from cubic recognisers ⋮ Characterizations and extensions of pushdown translations ⋮ Online perceptual learning and natural language acquisition for autonomous robots ⋮ Parsing schemata and correctness of parsing algorithms ⋮ Computing abstract decorations of parse forests using dynamic programming and algebraic power series ⋮ Learning to Parse on Aligned Corpora (Rough Diamond) ⋮ The equivalence of four extensions of context-free grammars ⋮ Forest alignment with affine gaps and anchors, applied in RNA structure comparison ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Deterministic multitape automata computations ⋮ Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models ⋮ Automating formalization by statistical and semantic parsing of mathematics ⋮ One-variable context-free hedge automata ⋮ Formal languages for integer programming modeling of shift scheduling problems ⋮ Interdependent translation schemes ⋮ Analyzing Context-Free Grammars Using an Incremental SAT Solver ⋮ Efficient parallel and incremental parsing of practical context-free languages ⋮ Unnamed Item ⋮ Independent parallelism in finite copying parallel rewriting systems ⋮ Path querying with conjunctive grammars by matrix multiplication ⋮ Certified CYK parsing of context-free languages ⋮ Grammar semantics, analysis and parsing by abstract interpretation ⋮ An efficient automata approach to some problems on context-free grammars. ⋮ An error-correcting syntactic decoder for computer networks ⋮ Fast uniform analysis of Coupled-Context-Free languages ⋮ Definability and decidability issues in extensions of the integers with the divisibility predicate ⋮ BRNGLR: a cubic Tomita-style GLR parsing algorithm ⋮ Parallel parsing on a one-way linear array of finite-state machines ⋮ Approximately matching context-free languages ⋮ Linear processing with pregroups ⋮ Efficient reconfigurable embedded parsers ⋮ Recognising \(k\)-connected hypergraphs in cubic time ⋮ Relationships between pushdown automata with counters and complexity classes ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ A large neighbourhood search approach to the multi-activity shift scheduling problem ⋮ The tape-complexity of context-independent developmental languages ⋮ Error-repair parsing schemata ⋮ Sequentielle Analyse kontextfreier Sprachen ⋮ Storage requirements for deterministic polynomial time recognizable languages ⋮ Efficiency of pregroups and the French noun phrase ⋮ A unifying approach to picture grammars ⋮ Membership for growing context-sensitive grammars is polynomial ⋮ Complete problems for deterministic polynomial time ⋮ Bracket-languages are recognizable in logarithmic space ⋮ Computational aspects of mining maximal frequent patterns ⋮ Recognition of EOL languages in less than quartic time ⋮ Two complementary operations inspired by the DNA hairpin formation: Completion and reduction ⋮ LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata ⋮ Syntactic stochastic processes: definitions, models, and related inference problems ⋮ Complexity of some problems concerningL systems ⋮ Properties of syntax directed translations ⋮ Syntax directed translations and the pushdown assembler ⋮ Generalized sequential machine maps ⋮ An efficient all-parses systolic algorithm for general context-free parsing ⋮ On some algorithmic problems regarding the hairpin completion ⋮ Manipulating derivation forests by scheduling techniques ⋮ Selected Decision Problems for Square-Refinement Collage Grammars ⋮ Reflections on Optimal and Nearly Optimal Binary Search Trees ⋮ Tabulator-Turingmaschine und Komplexität. (Tabulator Turing machine and complexity) ⋮ DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS ⋮ Pushdown automata with counters ⋮ Tape-reversal bounded Turing machine computations ⋮ Theory of formal grammars ⋮ Computing a context-free grammar-generating series ⋮ Parallel on-line parsing in constant time per word ⋮ A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead ⋮ On the complexity of the recognition of parallel 2D-image languages ⋮ Representations of the language recognition problem for a theorem prover ⋮ Synchronous context-free grammars and optimal linear parsing strategies

This page was built for publication: Recognition and parsing of context-free languages in time n3