Classes of languages and linear-bounded automata
From MaRDI portal
Publication:5596812
DOI10.1016/S0019-9958(64)90120-2zbMath0199.04002DBLPjournals/iandc/Kuroda64WikidataQ55871788 ScholiaQ55871788MaRDI QIDQ5596812
Publication date: 1964
Published in: Information and Control (Search for Journal in Brave)
Related Items (72)
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
This page was built for publication: Classes of languages and linear-bounded automata
