12 citations · 116 across the 27 of their papers we have counts for
27 papers
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…
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…
Unboundedness problems for machines with reversal-bounded counters
Pascal Baumann, Flavio D'Alessandro, Moses Ganardi +4
We consider a general class of decision problems concerning formal languages, called ``(one-dimensional) unboundedness predicates'', for automata that feature reversal-bounded coun…
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…
A Novel Technique Combining Image Processing, Plant Development Properties, and the Hungarian Algorithm, to Improve Leaf Detection in Maize
Nazifa Khan, Oliver A. S. Lyon, Mark Eramian +1
Manual determination of plant phenotypic properties such as plant architecture, growth, and health is very time consuming and sometimes destructive. Automatic image analysis has be…
DNA Methylation Data to Predict Suicidal and Non-Suicidal Deaths: A Machine Learning Approach
Rifat Zahan, Ian McQuillan, Nathaniel D. Osgood
The objective of this study is to predict suicidal and non-suicidal deaths from DNA methylation data using a modern machine learning algorithm. We used support vector machines to c…
Stochastic L-system Inference from Multiple String Sequence Inputs
Jason Bernard, Ian McQuillan
Lindenmayer systems (L-systems) are a grammar system that consist of string rewriting rules. The rules replace every symbol in a string in parallel with a successor to produce the…
Techniques for Inferring Context-Free Lindenmayer Systems With Genetic Algorithm
Jason Bernard, Ian McQuillan
Lindenmayer systems (L-systems) are a formal grammar system, where the most notable feature is a set of rewriting rules that are used to replace every symbol in a string in paralle…
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…
From Helmut Jürgensen's Former Students: The Game of Informatics Research
Mark Daley, Mark Eramian, Christopher Power +1
Personal reflections are given on being students of Helmut Jürgensen. Then, we attempt to address his hypothesis that informatics follows trend-like behaviours through the use of a…
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…
New Techniques for Inferring L-Systems Using Genetic Algorithm
Jason Bernard, Ian McQuillan
Lindenmayer systems (L-systems) are a formal grammar system that iteratively rewrites all symbols of a string, in parallel. When visualized with a graphical interpretation, the ima…
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…