Deletion operations on deterministic families of automata

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

zbMATH Keywords

determinismfinite automatacounter machinesreversal-boundsautomata and logicdeletion operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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