CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES

DOI10.1142/S0129054112400539zbMath1272.68210OpenAlexW2082899028MaRDI QIDQ4923281

Oscar H. Ibarra, Shinnosuke Seki

Publication date: 6 June 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054112400539

zbMATH Keywords

semilinear setsbounded semilinear languagesfinite-turn and finite-crossing two-way headreversal-bounded counter machines

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 ⋮ On store languages and applications ⋮ On counting functions and slenderness of languages ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ On bounded languages and reversal-bounded automata ⋮ Input-Position-Restricted Models of Language Acceptors ⋮ On the Density of Context-Free and Counter Languages ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ On the Boundedness Property of Semilinear Sets ⋮ On store languages of language acceptors ⋮ Finitely distinguishable erasing pattern languages ⋮ On Families of Full Trios Containing Counter Machine Languages ⋮ On the overlap assembly of strings and languages ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L ⋮ On families of full trios containing counter machine languages ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• The complexity of the equivalence problem for two characterizations of Presburger sets
• The complexity of decision problems for finite-turn multicounter machines
• Reversal-bounded multipushdown machines
• A technique for proving decidability of containment and equivalence of linear constraint queries
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• An NP-Complete Number-Theoretic Problem
• On Context-Free Languages

This page was built for publication: CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES