12 citations · 96 across the 17 of their papers we have counts for
17 papers
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…
On Store Languages and Applications
Oscar H. Ibarra, Ian McQuillan
The store language of a machine of some arbitrary type is the set of all store configurations (state plus store contents but not the input) that can appear in an accepting computat…
Insertion Operations on Deterministic Reversal-Bounded Counter Machines
Joey Eremondi, Oscar H. Ibarra, Ian McQuillan
Several insertion operations are studied applied to languages accepted by one-way and two-way deterministic reversal-bounded multicounter machines. These operations are defined by…
On counting functions and slenderness of languages
Oscar H. Ibarra, Ian McQuillan, Bala Ravikumar
We study counting-regular languages -- these are languages for which there is a regular language such that the number of strings of length in and are the same…
On the Density of Languages Accepted by Turing Machines and Other Machine Models
Oscar H. Ibarra, Ian McQuillan
A language is dense if the set of all infixes (or subwords) of the language is the set of all words. Here, it is shown that it is decidable whether the language accepted by a nonde…
On the Density of Context-Free and Counter Languages
Joey Eremondi, Oscar H. Ibarra, Ian McQuillan
A language is said to be dense if every word in the universe is an infix of some word in . This notion has been generalized from the infix operation to arbitrary word operat…
Variations of Checking Stack Automata: Obtaining Unexpected Decidability Properties
Oscar H. Ibarra, Ian McQuillan
We introduce a model of one-way language acceptors (a variant of a checking stack automaton) and show the following decidability properties: (1) The deterministic version has a dec…
On Store Languages of Language Acceptors
Oscar H. Ibarra, Ian McQuillan
It is well known that the "store language" of every pushdown automaton -- the set of store configurations (state and stack contents) that can appear as an intermediate step in acce…
On Finite-Index Indexed Grammars and Their Restrictions
Flavio D'Alessandro, Oscar H. Ibarra, Ian McQuillan
The family, L(INDLIN), of languages generated by linear indexed grammars has been studied in the literature. It is known that the Parikh image of every language in L(INDLIN) is sem…
Deletion Operations on Deterministic Families of Automata
Joey Eremondi, Oscar H. Ibarra, Ian McQuillan
Many different deletion operations are investigated applied to languages accepted by one-way and two-way deterministic reversal-bounded multicounter machines, deterministic pushdow…
On the Complexity and Decidability of Some Problems Involving Shuffle
Joey Eremondi, Oscar H. Ibarra, Ian McQuillan
The complexity and decidability of various decision problems involving the shuffle operation are studied. The following three problems are all shown to be -complete: given a no…
On Languages Accepted by P/T Systems Composed of joins
Pierluigi Frisco, Oscar H. Ibarra
Recently, some studies linked the computational power of abstract computing systems based on multiset rewriting to models of Petri nets and the computation power of these nets to t…