12 citations · 96 across the 17 of their papers we have counts for
6 papers · 1 filter
State Grammars with Stores
Oscar H. Ibarra, Ian McQuillan
State grammars are context-free grammars where the productions have states associated with them, and a production can only be applied to a nonterminal if the current state matches…
On Families of Full Trios Containing Counter Machine Languages
Oscar H. Ibarra, Ian McQuillan
We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by s…
Relationships Between Bounded Languages, Counter Machines, Finite-Index Grammars, Ambiguity, and Commutative Regularity
Arturo Carpi, Flavio D'Alessandro, Oscar H. Ibarra +1
It is shown that for every language family that is a trio containing only semilinear languages, all bounded languages in it can be accepted by one-way deterministic reversal-bounde…
Semilinearity of Families of Languages
Oscar H. Ibarra, Ian McQuillan
Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that f…
Generalizations of Checking Stack Automata: Characterizations and Hierarchies
Oscar H. Ibarra, Ian McQuillan
We examine different generalizations of checking stack automata by allowing multiple input heads and multiple stacks, and characterize their computing power in terms of two-way mul…
Space Complexity of Stack Automata Models
Oscar H. Ibarra, Jozef Jirásek, Ian McQuillan +1
This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum s…