Remarks on blind and partially blind one-way multicounter machines

DOI10.1016/0304-3975(78)90020-8zbMath0389.68030OpenAlexW2075742699MaRDI QIDQ1251070

Publication date: 1978

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(78)90020-8

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Algebraic characterization of petri net pomset semantics ⋮ Groups whose word problems are accepted by abelian $G$-automata ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Exact Affine Counter Automata ⋮ Spiking neural P systems: main ideas and results ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Jump complexity of finite automata with translucent letters ⋮ Extended finite automata over groups ⋮ On spiking neural P systems ⋮ On Boolean closed full trios and rational Kripke frames ⋮ Modularity in P Colonies with Checking Rules ⋮ Thompson's group $F$ is 1-counter graph automatic. ⋮ CTS systems and Petri nets ⋮ From regulated rewriting to computing with membranes: collapsing hierarchies ⋮ The conformon-P system: a molecular and cell biology-inspired computability model ⋮ Reversal-bounded nondeterministic multicounter machines and complementation ⋮ The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Unnamed Item ⋮ Context-free commutative grammars with integer counters and resets ⋮ General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond ⋮ Geodesic growth in virtually abelian groups ⋮ Unnamed Item ⋮ Classical and Quantum Counter Automata on Promise Problems ⋮ P systems with minimal insertion and deletion ⋮ Reset machines ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ One-way weak-stack-counter automata ⋮ On two-way weak counter machines ⋮ $\mathcal C$-graph automatic groups. ⋮ On counting functions and slenderness of languages ⋮ Computation power of asynchronous spiking neural P systems with polarizations ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Nonterminal complexity of programmed grammars. ⋮ Unnamed Item ⋮ Recent advances on reachability problems for valence systems (invited talk) ⋮ Homing vector automata ⋮ On Recursion, Replication and Scope Mechanisms in Process Calculi ⋮ The power of synchronizing operations on strings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Purely Catalytic P Systems over Integers and Their Generative Power ⋮ On the group memory complexity of extended finite automata over groups ⋮ Two-way deterministic multi-weak-counter machines ⋮ FINITE AUTOMATA OVER FREE GROUPS ⋮ On the topological complexity of $\omega$-languages of non-deterministic Petri nets ⋮ Refining the hierarchy of blind multicounter languages and twist-closed trios. ⋮ On spiking neural P systems and partially blind counter machines ⋮ Polycyclic and Bicyclic Valence Automata ⋮ The Equivalence Problem of Finite Substitutions on ab*c, with Applications ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Place/transition nets with debit arcs ⋮ On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids ⋮ The fixed point problem of a simple reversible language ⋮ Counter machines, Petri nets, and consensual computation ⋮ A multiset-based model of synchronizing agents: Computability and robustness ⋮ A Note on Multidimensional Dyck Languages ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ State grammars with stores ⋮ A well-structured framework for analysing Petri net extensions ⋮ $X$-automata on $\omega$-words ⋮ Affine Computation and Affine Automaton ⋮ Decidability of code properties ⋮ On partially blind multihead finite automata. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ ON GROUPS AND COUNTER AUTOMATA ⋮ GENERALIZED COUNTERS AND REVERSAL COMPLEXITY ⋮ Word problems recognisable by deterministic blind monoid automata ⋮ On the Number of Agents in P Colonies ⋮ Conformon-P Systems with Negative Values ⋮ New Results on Vector and Homing Vector Automata ⋮ Formal Languages and Groups as Memory ⋮ Input-driven multi-counter automata ⋮ Interference automata ⋮ General decidability results for asynchronous shared-memory programs: higher-order and beyond ⋮ P SYSTEMS AND TOPOLOGY: SOME SUGGESTIONS FOR RESEARCH ⋮ AN UNIVERSALITY RESULT FOR A (MEM)BRANE CALCULUS BASED ON MATE/DRIP OPERATIONS ⋮ Reachability problems in low-dimensional nondeterministic polynomial maps over integers ⋮ On the sentence valuation in a semiring ⋮ SIMULATIONS BY TIME-BOUNDED COUNTER MACHINES ⋮ TOWARD UNDERSTANDING THE GENERATIVE CAPACITY OF ERASING RULES IN MATRIX GRAMMARS ⋮ On Families of Full Trios Containing Counter Machine Languages ⋮ Asynchronous spiking neural P systems ⋮ Unnamed Item ⋮ Language classes associated with automata over matrix groups ⋮ Erasing in Petri Net Languages and Matrix Grammars ⋮ A class of restricted P colonies with string environment ⋮ A uniform approach to true-concurrency and interleaving semantics for Petri nets ⋮ Reachability in Petri Nets with Inhibitor Arcs ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ Unnamed Item ⋮ P SYSTEMS WITH SINGLE PASSENGER CARRIERS ⋮ Outils et résultats pour les transducteurs boustrophédons ⋮ Characterizations of some classes of spiking neural P systems ⋮ Finite transducers and rational transductions ⋮ Rational subsets of polycyclic monoids and valence automata ⋮ On some bounded semiAFLs and AFLs ⋮ Langages à un compteur ⋮ Groups Whose Word Problem is a Petri Net Language ⋮ On families of full trios containing counter machine languages ⋮ Remarks on two-way automata with weak-counters ⋮ On symport/antiport P systems with a small number of objects ⋮ A normal form theorem for label grammars ⋮ ON THE POWER OF DETERMINISTIC AND SEQUENTIAL COMMUNICATING P SYSTEMS ⋮ Extending regular expressions with iterated shuffle ⋮ On the power of alternation in automata theory ⋮ Sequential grammars and automata with valences ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ Characterization and complexity results on jumping finite automata

Cites Work