Invited Speakers
)
THE POWER OF "AFTER THE FACT" ARITHMETIC CONSTRAINTS ON COUNTERS: PARIKH AUTOMATA AND THEIR MANY FRIENDS
Michaël Cadilhac (DePaul University, USA)
A knee-jerk reaction to learning that {a^n b^n | n > 0} is not regular is to say: "Well, that's preposterous, that's easy to check, so add it to your model!" Then, one quickly learns that adding counters to machines leads to a world of undecidability, and is left with the uneasy feeling that "simple" arithmetic properties are surprisingly complex. But it doesn't have to be this way. What if, instead of equipping the model with counters that can be tested throughout the run, one equips it with counters that can only be tested at the end? Surely, if emptiness is decidable with the original model, there are good chances that emptiness stays decidable with the augmented model, right? In the case of automata, the augmented model is called Parikh Automata, and they are very well behaved — but is the tameness of "after the fact" constraints universal?
In this talk, I will review models defined in that fashion, exploring their many equivalent models throughout the literature, from the dawn of language theory to this day — chief among them reversal-bounded counter machines — and will focus on recent salient open questions.
STACK AUTOMATA AND RESTRICTIONS
Ian McQuillan (University of Saskatchewan, Canada)
Stack automata are generalizations of pushdown automata with the added ability of reading from the inside of the stack in a two-way read-only fashion --- but they can edit the stack by pushing and popping when reading from the top of the stack. We examine many properties of stack automata, including a recently developed restriction called visit-bounded stack automata which are more powerful than pushdown automata but that can only accept semilinear languages. Furthermore, we investigate the size of the stack needed for a given machine, and for a given language, using several different complexity measures. Finally, we investigate decidability problems and the complexity of languages (in terms of complexity classes of Turing machines) that can be accepted by augmenting different types of automata with one or more checking stacks.
ON APPROXIMATE RECOGNITION OF NON-REGULAR LANGUAGES
Bala Ravikumar (Sonoma Sate University, USA)
Language acceptance by a machine is based on all strings being correctly processed by it. Approximate recognition relaxes this requirement by allowing some strings (not) in the language to be rejected (accepted). It has been shown in a prior work that the set of strings with more 1's than 0's can't be approximated by a finite automaton in a nontrivial way. In this talk, after quickly surveying prior work on this topic, we present a framework that allows us to establish strong non-approximability results with a 1-sided error and present some applications. We also present efficient algorithms to compute the error in approximating a subclass of context-free languages by finite automata and some related results. Some results on approximability, when the measure of error is defined over strings of fixed length, are also presented and in some cases, are related to well-known open problems.