3 papers
cs.FL2026
Language Acceptors with a Pushdown: Characterizations and Complexity
Oscar H. Ibarra, Ian McQuillan
We study one-way nondeterministic pushdown automata (NPDA), optionally with reversal-bounded counters. Finite-turn pushdown automata are pushdown automata with a bound on the numbe…
cs.FL2025
Store Languages of Turing Machines and Counter Machines
Noah Friesen, Oscar H. Ibarra, Jozef Jirásek +1
The store language of an automaton is the set of store configurations (state and store contents, but not the input) that can appear as an intermediate step in an accepting computat…
cs.FL2024
Techniques for Showing the Decidability of the Boundedness Problem of Language Acceptors
Oscar H. Ibarra, Ian McQuillan
There are many types of automata and grammar models that have been studied in the literature, and for these models, it is common to determine whether certain problems are decidable…