Speed of Recognition of Context-Free Languages by Array Automata

DOI10.1137/0204028MaRDI QIDQ4069798zbMATH OpenOpenAlexFDO

Authors S. R. 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

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

Cited in

(19)

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

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

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