Time-bounded grammars and their languages

DOI10.1016/S0022-0000(71)80025-9zbMath0223.68012OpenAlexW2032623970MaRDI QIDQ2548174

Ronald V. Book

Publication date: 1971

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(71)80025-9

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Grammars and rewriting systems (68Q42)

Related Items

On the generating power of regularly controlled bidirectional grammars, Time-bounded controlled bidirectional grammars, Deterministic multitape automata computations, Sweeping input-driven pushdown automata, Grammars with valuations - a discrete model for self-organization of biopolymers, Time and space complexity for splicing systems, On the structure of context-sensitive grammars, Complexity theory for splicing systems, Nonuniform complexity and the randomness of certain complete languages, On the degrees of non-regularity and non-context-freeness, On the synchronized derivation depth of context-free grammars, The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages, Membership for growing context-sensitive grammars is polynomial, On the complexity of formal grammars, The ancestor width of grammars and languages, A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES, On the extension of Gladkij's theorem and the hierarchies of languages, SHRINKING RESTARTING AUTOMATA, Some restrictions onW-grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time- and tape-bounded Turing acceptors and AFLs
• System error analysis based on one-at-a-time perturbations
• On the Computational Complexity of Algorithms
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Mappings which preserve context sensitive languages
• Real-Time Definable Languages
• A note on undecidable properties of formal languages
• Some remarks on derivations in general rewriting systems
• Quasi-realtime languages
• Classes of languages and linear-bounded automata
• One-tape, off-line Turing machine computations
• Three theorems on phrase structure grammars of type 1