Classes of languages and linear-bounded automata
From MaRDI portal
Publication:5596812
DOI10.1016/S0019-9958(64)90120-2zbMath0199.04002WikidataQ55871788 ScholiaQ55871788MaRDI QIDQ5596812
Publication date: 1964
Published in: Information and Control (Search for Journal in Brave)
Related Items
The theory of languages, Parsimonious computational completeness, A Note on Combined Derivation Modes for Cooperating Distributed Grammar Systems, Context-free languages and rudimentary attributes, Controlled Term Rewriting, Consensus Game Acceptors, The method of forced enumeration for nondeterministic automata, Programmed grammars and their relation to the LBA problem, Linearly bounded infinite graphs, The theory of languages, \(\Sigma_ 2SPACE(n)\) is closed under complement, A note on some systems of lindenmayer, Some modifications of auxiliary pushdown automata, On weak growing context-sensitive grammars, Complexity of multi-head finite automata: origins and directions, Weight-reducing Turing machines, Investigations on the power of matrix insertion-deletion systems with small sizes, CD Grammar Systems with Two Propagating Scattered Context Components Characterize the Family of Context Sensitive Languages, Existence and feasibility in arithmetic, Strictly Locally Testable and Resources Restricted Control Languages in Tree-Controlled Grammars, On the complexity of regular-grammars with integer attributes, An infinite hierarchy of intersections of context-free languages, Unnamed Item, Traces of term-automatic graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the structure of context-sensitive grammars, Parallel language recognition in constant time by cellular automata, Unnamed Item, Space bounded computations: Review and new separation results, Consensus Game Acceptors and Iterated Transductions, Fifty years of the spectrum problem: survey and new results, Two-Way Automata versus Logarithmic Space, A survey of space complexity, Unnamed Item, Accepting networks of evolutionary processors with subregular filters, Two-way automata versus logarithmic space, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Comment on the paper 'Error detection in formal languages', On coupled languages and translations, On the complexity of the ℰ2 Grzegorczyk class, Descriptional and computational complexity of finite automata -- a survey, Splitting a context-sensitive set, Families of automata characterizing context-sensitive languages, Size, index, and context-sensitivity of controlled partition grammars, A characterization of the power of vector machines, Some clarifications of the concept of a Garden-of-Eden configuration, Membership for growing context-sensitive grammars is polynomial, On the complexity of formal grammars, Finite state and finite stop quantum languages, Gaining Power by Input Operations: Finite Automata and Beyond, Inference of bounded L systems with polymorphic P systems, Zerlegungen von Semi-Thue-Systemen, A generator of context-sensitive languages, A hierarchy between context-free and context-sensitive languages, Real-time computations with restricted nondeterminism, Error detection in formal languages, Time-bounded grammars and their languages, Towards a theory of data structures, Unilateral context sensitive grammars and left-to-right parsing, Pushdown cellular automata, On the generative power of transformational grammars, Real-time language recognition by one-dimensional cellular automata, A class of universal linear bounded automata, Normal forms for context-sensitive grammars, Converting nondeterministic two-way automata into small deterministic linear-time machines, Iteration of rational transductions, Emergence of order in random languages, Multi-head finite automata: Data-independent versus data-dependent computations, Turing machines and the spectra of first-order formulas
