Counter machines and counter languages
From MaRDI portal
Publication:5551469
DOI10.1007/BF01694011zbMath0165.32002WikidataQ57407483 ScholiaQ57407483MaRDI QIDQ5551469
Arnold L. Rosenberg, Patrick C. Fischer, Albert R. Meyer
Publication date: 1968
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items
Production en temps réel et complexité de structure de suites infinies, The complexity of decision procedures in relevance logic II, ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS, Real-time solutions of the origin-crossing problem, Quasi-realtime languages, Multi-stack-counter languages, On the computational complexity of membrane systems, Recognising \(k\)-connected hypergraphs in cubic time, Syntactic operators on full semiAFLs, Simple programming languages and restricted classes of Turing machines, Remarks on two-way automata with weak-counters, Complexity of the word problem for commutative semigroups of fixed dimension, A note on real-time one-way alternating multicounter machines, The complexity of finding SUBSEQ\((A)\), Word problems over traces which are solvable in linear time, Two-way automata with more than one storage medium, One-way weak-stack-counter automata, Indirect addressing and the time relationships of some models of sequential computation, On-line n-bounded multicounter automata, The complexity of decision problems for finite-turn multicounter machines, Complexity of algorithms and computations, An information-theoretic approach to time bounds for on-line computation, Two-way deterministic multi-weak-counter machines, Remarks on the complexity of nondeterministic counter languages, On the pre-AFL of \([lg\;n\) space and related families of languages], The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet, Computational complexity of multitape Turing machines and random access machines, Remarks on blind and partially blind one-way multicounter machines, One-way simple multihead finite automata, On the simulation of many storage heads by one, The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors, Refining the hierarchy of blind multicounter languages and twist-closed trios., Counter machines, Quantum versus deterministic counter automata, The complexity of the word problems for commutative semigroups and polynomial ideals, Theory of formal grammars, Minimum-cost delegation in service composition, Time-restricted sequence generation, AFL with the semilinear property, Translating recursion equations into flow charts, Pushdown automata with counters, On the Computational Complexity of Spiking Neural P Systems, Unnamed Item, Simulations by Time-Bounded Counter Machines, Unnamed Item, On two-way weak counter machines, Uniform simulations of nondeterministic real time multitape turing machines, Equivalence problem for finitely iterated counter machines, Unnamed Item, Unnamed Item, Non-prinicipalité du cylindre des langages à compteur
Cites Work
- Unnamed Item
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Real time computation
- On the Computational Complexity of Algorithms
- Bounded Algol-Like Languages
- Turing machines with restricted memory access
- Real-Time Definable Languages
- On Context-Free Languages
- Real-time solutions of the origin-crossing problem
