CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
Óscar H. Ibarra, Shinnosuke Seki · International Journal of Foundations of Computer Science · 2012
A bounded language [Formula: see text] (for some k ≥ 1 and not-necessarily distinct nonempty words x1, …, xk) is bounded semilinear if the set [Formula: see text] is semilinear. We give characterizations of bounded semilinear languages in terms of one-way and two-way deterministic counter machines.