Reversal-Bounded Multicounter Machines and Their Decision Problems

Cited in

(only showing first 100 items - show all)

Bad news on decision problems for patterns
A characterization of reversal-bounded multipushdown machine languages
A note on Parikh maps, abstract languages, and decision problems
Alternating multicounter machines with constant number of reversals
An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
Reversal-bounded nondeterministic multicounter machines and complementation
Representations of language families by homomorphic equality operations and generalized equality sets
On the decidability of some problems about rational subsets of free partially commutative monoids
On reversal bounded alternating Turing machines
Pushdown automata with reversal-bounded counters
Simple counter machines and number-theoretic problems
The complexity of the equivalence problem for two characterizations of Presburger sets
The complexity of decision problems for finite-turn multicounter machines
On the decidability of equivalence for deterministic pushdown transducers
Deciding freeness for program schemes with a single unary function
2DST mappings of languages and related problems
Two-way deterministic multi-weak-counter machines
Rational relations and rational series
Some decision problems concerning sequential transducers and checking automata
Transducers and the decidability of independence in free monoids
Verification in loosely synchronous queue-connected discrete timed automata.
Automatic verification of recursive procedures with one integer parameter.
Generalized discrete timed automata: Decidable approximations for safety verification.
Pushdown timed automata: A binary reachability characterization and safety verification.
Past pushdown timed automata and safety verification.
Closure and decidability properties of some language classes with respect to ciliate bio-operations.
Modelization of deterministic rational relations
Visibly pushdown transducers
On the teaching complexity of linear sets
Reachability analysis of reversal-bounded automata on series-parallel graphs
Computations on register machines with counters
Accepting runs in a two-way finite automaton
On two-way nondeterministic finite automata with one reversal-bounded counter
Grammatical characterizations of NPDAs and VPDAs with counters
On store languages of language acceptors
A technique for proving decidability of containment and equivalence of linear constraint queries
Nondeterministic multicounter machines and complementation
Counter machines and verification problems.
Augmenting the discrete timed automaton with other data structures.
Some decision problems concerning semilinearity and commutation.
Presburger liveness verification of discrete timed automata.
Eliminating the storage tape in reachability constructions.
On two-way FA with monotonic counters and quadratic Diophantine equations
Catalytic P systems, semilinear sets, and vector addition systems
Computational power of two stacks with restricted communication
Cellular automata with sparse communication
Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity
Pseudo-inversion: closure properties and decidability
Counter machines and crystallographic structures
Dense-choice counter machines revisited
On the complexity of decision problems for counter machines with applications to coding theory
Iterative arrays with finite inter-cell communication
On decidability and closure properties of language classes with respect to bio-operations
On the overlap assembly of strings and languages
On families of full trios containing counter machine languages
Sampling automata and programs
Deterministic input-driven queue automata: finite turns, decidability, and closure properties
Simulating one-reversal multicounter machines by partially blind multihead finite automata
On the conjecture \(\mathcal {L}_{\mathsf {DFCM}}\subsetneq \mathsf {RCM}\)
Information rate of some classes of non-regular languages: an automata-theoretic approach
On store languages and applications
On counting functions and slenderness of languages
Verification of gap-order constraint abstractions of counter systems
On partially blind multihead finite automata.
On composition and lookahead delegation of \(e\)-services modeled by automata
Equivalence between model-checking flat counter systems and Presburger arithmetic
The effect of end-markers on counter machines and commutativity
On the decidability of the valuedness problem for two-way finite transducers
Recent advances on reachability problems for valence systems (invited talk)
On computational complexity of graph inference from counting
Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities
On Families of Full Trios Containing Counter Machine Languages
Descriptional complexity of bounded regular languages
Decision Problems for Finite Automata over Infinite Algebraic Structures
On bounded semilinear languages, counter machines, and finite-index ET0L
On the Teaching Complexity of Linear Sets
Bounded Parikh automata
On computational power of partially blind automata
Multitape NFA: Weak Synchronization of the Input Heads
Verification of gap-order constraint abstractions of counter systems
Model-checking \(\mathrm{CTL}^*\) over flat Presburger counter systems
Schema for parallel insertion and deletion: revisited
Automata with modulo counters and nondeterministic counter bounds
Security of numerical sensors in automata
VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES
THE EXISTENCE OF ω-CHAINS FOR TRANSITIVE MIXED LINEAR RELATIONS AND ITS APPLICATIONS
Sublinearly space bounded iterative arrays
Two-party Watson-Crick computations
A polynomial time match test for large classes of extended regular expressions
One-reversal counter machines and multihead automata: revisited
On strong reversibility in P systems and related problems
The complexity of reversal-bounded model-checking
Quantifying communication in synchronized languages
PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS
Quantifying communication in synchronized languages
Ordered multi-stack visibly pushdown automata
On the density of context-free and counter languages
Multi-sequential word relations
ON COUNTER MACHINES, REACHABILITY PROBLEMS, AND DIOPHANTINE EQUATIONS
Bad News on Decision Problems for Patterns

This page was built for publication: Reversal-Bounded Multicounter Machines and Their Decision Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4140393)