Speed of Recognition of Context-Free Languages by Array Automata

DOI10.1137/0204028zbMath0311.68052OpenAlexW1980204294MaRDI QIDQ4069798

S. Rao Kosaraju

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204028

Mathematics Subject Classification ID

Formal languages and automata (68Q45) General topics in the theory of software (68N01)

Related Items (19)

Algorithm partition and parallel recognition of general context-free languages using fixed-size VLSI architecture ⋮ An optimal sublinear time parallel algorithm for some dynamic programming problems ⋮ A parallel parsing algorithm for arbitrary context-free grammars ⋮ Two-dimensional iterative arrays: Characterizations and applications ⋮ Optimal simulation of tree arrays by linear arrays ⋮ Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs ⋮ Parallel \(LL\) parsing ⋮ A computation model with automatic functions and relations as primitive operations ⋮ Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition ⋮ Parallel recognition and ranking of context-free languages ⋮ Optimal tradeoffs for addition on systolic arrays ⋮ Iterative tree arrays with logarithmic depth^† ⋮ Parallel parsing of tree adjoining grammars on the connection machine ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ INSTANCE-SPECIFIC SOLUTIONS FOR ACCELERATING THE CKY PARSING OF LARGE CONTEXT-FREE GRAMMARS ⋮ Iterative arrays with direct central control ⋮ Systolic parsing of context-free languages ⋮ On the relationship between propagating context-dependent Lindenmayer systems and cellular automata systems ⋮ Topological transformations as a tool in the design of systolic networks

This page was built for publication: Speed of Recognition of Context-Free Languages by Array Automata