The effect of end-markers on counter machines and commutativity

DOI10.1016/J.TCS.2016.02.034MaRDI QIDQ265080zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra, Ian McQuillan

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

commutativitycounter machinesdeterminismfinite automatareversal-bounds

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Some decision problems concerning semilinearity and commutation.
• Automata with Reversal-Bounded Counters: A Survey
• New Decidability Results Concerning Two-Way Counter Machines
• scientific article; zbMATH DE number 3932419
• One-reversal counter machines and multihead automata: revisited

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1418342 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• Affine Parikh automata
• Automata with Reversal-Bounded Counters: A Survey
• Bounded Parikh automata
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• Commutative languages and their composition by consensual methods
• Cônes rationnels commutatifs
• Deterministic context free languages
• On Context-Free Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Some decision problems concerning semilinearity and commutation.

Cited in

(9)

• scientific article; zbMATH DE number 1754622 (Why is no real title available?)
• Input-Position-Restricted Models of Language Acceptors
• On bounded semilinear languages, counter machines, and finite-index ET0L
• On the complexity of decision problems for some classes of machines and applications
• State grammars with stores
• On store languages of language acceptors
• On store languages and applications
• Semilinearity of families of languages
• Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity

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

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