The effect of end-markers on counter machines and commutativity

DOI10.1016/j.tcs.2016.02.034zbMath1338.68150OpenAlexW2288306272MaRDI QIDQ265080

Ian McQuillan, Oscar H. Ibarra

Publication date: 1 April 2016

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.034

zbMATH Keywords

determinismfinite automatacommutativitycounter machinesreversal-bounds

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (10)

On store languages and applications ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On the complexity and decidability of some problems involving shuffle ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ State grammars with stores ⋮ On store languages of language acceptors ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ Semilinearity of Families of Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cônes rationnels commutatifs
• Reversal-bounded multipushdown machines
• Some decision problems concerning semilinearity and commutation.
• Deletion operations on deterministic families of automata
• Insertion operations on deterministic reversal-bounded counter machines
• BOUNDED PARIKH AUTOMATA
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Affine Parikh automata
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Automata with Reversal-Bounded Counters: A Survey
• Deterministic context free languages
• On Context-Free Languages

This page was built for publication: The effect of end-markers on counter machines and commutativity