Counter machines and counter languages

DOI10.1007/BF01694011zbMath0165.32002OpenAlexW2056647002WikidataQ57407483 ScholiaQ57407483MaRDI QIDQ5551469

Albert R. Meyer, Patrick C. Fischer, Arnold L. Rosenberg

Publication date: 1968

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01694011

zbMATH Keywords

languages, automata, networks

Related Items

Two-way automata with more than one storage medium ⋮ The Complexity of Small Universal Turing Machines: A Survey ⋮ Real-time solutions of the origin-crossing problem ⋮ The complexity of finding SUBSEQ\((A)\) ⋮ Minimum-cost delegation in service composition ⋮ Unnamed Item ⋮ On the simulation of many storage heads by one ⋮ Quasi-realtime languages ⋮ Counter machines and distributed automata -- a story about exchanging space and time ⋮ On the computational complexity of membrane systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the computational complexity of spiking neural P systems ⋮ Universality in Infinite Petri Nets ⋮ Multi-stack-counter languages ⋮ The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors ⋮ One-way weak-stack-counter automata ⋮ On two-way weak counter machines ⋮ \(\mathcal C\)-graph automatic groups. ⋮ Indirect addressing and the time relationships of some models of sequential computation ⋮ On-line n-bounded multicounter automata ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Languages generated by numerical P systems with thresholds ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ Complexity of algorithms and computations ⋮ Homing vector automata ⋮ An information-theoretic approach to time bounds for on-line computation ⋮ Word problems over traces which are solvable in linear time ⋮ Two-way deterministic multi-weak-counter machines ⋮ Computational power of two stacks with restricted communication ⋮ Passively mobile communicating machines that use restricted space ⋮ Unnamed Item ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ On the Computational Complexity of Spiking Neural P Systems ⋮ On some derivation mechanisms and the complexity of their Szilard languages ⋮ Unnamed Item ⋮ Three small universal spiking neural P systems ⋮ Expressive Power of Broadcast Consensus Protocols ⋮ Computations on register machines with counters ⋮ Counter machines, Petri nets, and consensual computation ⋮ Recognising \(k\)-connected hypergraphs in cubic time ⋮ Non-prinicipalité du cylindre des langages à compteur ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ Quantum versus deterministic counter automata ⋮ On the pre-AFL of \([lg\;n\) space and related families of languages] ⋮ SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS ⋮ The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet ⋮ The complexity of decision procedures in relevance logic II ⋮ Computational complexity of multitape Turing machines and random access machines ⋮ On the termination and structural termination problems for counter machines with incrementing errors ⋮ Remarks on blind and partially blind one-way multicounter machines ⋮ Clocked population protocols ⋮ Input-driven multi-counter automata ⋮ ON VARIOUS NOTIONS OF PARALLELISM IN P SYSTEMS ⋮ One-way simple multihead finite automata ⋮ SIMULATIONS BY TIME-BOUNDED COUNTER MACHINES ⋮ Simulations by Time-Bounded Counter Machines ⋮ Time-restricted sequence generation ⋮ Syntactic operators on full semiAFLs ⋮ Complexity Hierarchies beyond Elementary ⋮ Equivalence problem for finitely iterated counter machines ⋮ AFL with the semilinear property ⋮ Translating recursion equations into flow charts ⋮ Pushdown automata with counters ⋮ On the Complexity of Szilard Languages of Regulated Grammars ⋮ Production en temps réel et complexité de structure de suites infinies ⋮ The complexity of the word problems for commutative semigroups and polynomial ideals ⋮ Theory of formal grammars ⋮ 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 ⋮ Counter machines

Cites Work