Deletion operations on deterministic families of automata
From MaRDI portal
Publication:2407104
DOI10.1016/j.ic.2017.07.009zbMath1376.68089arXiv1607.00931OpenAlexW2949687231MaRDI QIDQ2407104
Ian McQuillan, Oscar H. Ibarra, Joey Eremondi
Publication date: 28 September 2017
Published in: Lecture Notes in Computer Science, Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.00931
Related Items (11)
The effect of end-markers on counter machines and commutativity ⋮ On the Density of Context-Free and Counter Languages ⋮ On the decidability of infix inclusion problem ⋮ On the conjecture \(\mathcal {L}_{\mathsf {DFCM}}\subsetneq \mathsf {RCM}\) ⋮ Deletion operations on deterministic families of automata ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On the Density of Context-Free and Counter Languages ⋮ On the complexity and decidability of some problems involving shuffle ⋮ On store languages of language acceptors ⋮ On families of full trios containing counter machine languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- One-reversal counter machines and multihead automata: revisited
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- The complexity of decision problems for finite-turn multicounter machines
- Reversal-bounded multipushdown machines
- Counter machines and verification problems.
- Some decision problems concerning semilinearity and commutation.
- Deletion operations on deterministic families of automata
- Insertion operations on deterministic reversal-bounded counter machines
- SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED
- Nondeterministic Streaming String Transducers
- ON STRONG REVERSIBILITY IN P SYSTEMS AND RELATED PROBLEMS
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- New Decidability Results Concerning Two-Way Counter Machines
- Visibly Pushdown Automata and Transducers with Counters
- Morphisms preserving densities
- CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
- Deterministic context free languages
- Indexed Grammars—An Extension of Context-Free Grammars
This page was built for publication: Deletion operations on deterministic families of automata