Insertion operations on deterministic reversal-bounded counter machines

DOI10.1016/j.jcss.2018.02.003zbMath1423.68250arXiv1903.03518OpenAlexW2962898883WikidataQ130162601 ScholiaQ130162601MaRDI QIDQ2424688

Oscar H. Ibarra, Joey Eremondi, Ian McQuillan

Publication date: 25 June 2019

Published in: Journal of Computer and System Sciences, Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.03518

zbMATH Keywords

determinismfinite automatacounter machinesreversal-boundsinsertion operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The effect of end-markers on counter machines and commutativity ⋮ Deletion operations on deterministic families of automata ⋮ Special issue: Selected papers of the 9th international conference on language and automata theory and applications, LATA 2015 ⋮ Formal grammars for turn-bounded deterministic context-free 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
• The effect of end-markers on counter machines and commutativity
• Theoretical and computational properties of transpositions
• One-reversal counter machines and multihead automata: revisited
• On a class of languages with holonomic generating functions
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Finite automata and unary languages
• The complexity of decision problems for finite-turn multicounter machines
• Reversal-bounded multipushdown machines
• On the complexity and decidability of some problems involving shuffle
• Counter machines and verification problems.
• Deletion operations on deterministic families of automata
• SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED
• On Decidability and Closure Properties of Language Classes with Respect to Bio-operations
• 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
• Morphisms preserving densities
• THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
• Deterministic context free languages