Quasi-realtime languages
From MaRDI portal
Publication:5582342
DOI10.1007/BF01705890zbMath0188.33102MaRDI QIDQ5582342
Ronald V. Book, Sheila A. Greibach
Publication date: 1970
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items (53)
Some formal results about stratificational grammars and their relevance to linguistics ⋮ Weighted restarting automata and pushdown relations ⋮ State-complexity of finite-state devices, state compressibility and incompressibility ⋮ Consensus Game Acceptors ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers) ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ Separating classes in the exponential-time hierarchy from classes in PH ⋮ Alternating real-time computations ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Some considerations about NPRIORITY(1) without ROM ⋮ On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamical recognizers: real-time language recognition by analog computers ⋮ Multi-stack-counter languages ⋮ Reset machines ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Observations on complete sets between linear time and polynomial time ⋮ Multiple equality sets and Post machines ⋮ Complexity of algorithms and computations ⋮ Two-way automata and length-preserving homomorphisms ⋮ Quasi-rocking real-time pushdown automata ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ Unnamed Item ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Computational power of one-way Turing machines with sublogarithmic memory restrictions ⋮ On characterisation of language families in terms of inverse morphisms ⋮ Comparing complexity classes ⋮ The role of rudimentary relations in complexity theory ⋮ On the pre-AFL of \([lg\;n\) space and related families of languages] ⋮ Control sets on context-free grammar forms ⋮ One way finite visit automata ⋮ Stack languages and log n space ⋮ Remarks on blind and partially blind one-way multicounter machines ⋮ A useful lemma for context-free programmed grammars ⋮ Compelled operations and operations of degreeP ⋮ Syntactic operators on full semiAFLs ⋮ Time- and tape-bounded Turing acceptors and AFLs ⋮ Language complexity of rotations and Sturmian sequences ⋮ Real-time computations with restricted nondeterminism ⋮ Time-bounded grammars and their languages ⋮ Realtime subshifts ⋮ On the extension of Gladkij's theorem and the hierarchies of languages ⋮ Real-time language recognition by one-dimensional cellular automata ⋮ Complexity of One-Way Cellular Automata ⋮ Deterministic Turing machines in the range between real-time and linear-time. ⋮ Partial commutations and faithful rational transductions ⋮ SHRINKING RESTARTING AUTOMATA ⋮ Non-deterministic cellular automata and languages ⋮ Some restrictions onW-grammars
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Scattered context grammars
- On the Computational Complexity of Algorithms
- Turing machines with restricted memory access
- Real-Time Definable Languages
- An Approach to a Unified Theory of Automata
- Counter machines and counter languages
- One-way stack automata
- An Infinite Hierarchy of Context-Free Languages
- One-way nondeterministic real-time list-storage languages
This page was built for publication: Quasi-realtime languages
