Automata Theory and Applications - IMS

Automata Theory and Applications
(1 - 30 Sep 2011)

~ Abstracts ~

Finite-state genericity: on the diagonalization strength of finite automata
Klaus Ambos-Spies, University of Heidelberg, Germany

Algorithmic and resource-bounded Baire category concepts and corresponding genericity concepts introduced in computability theory and computational complexity theory, respectively, have become elegant and powerful tools in these settings. Here we discuss some more recent genericity notions which are based on extension functions computable by finite automata and which are tailored for capturing diagonalizations over regular sets and functions. We show that the generic sets obtained by partial regular extension functions of any fixed constant length or by all total regular extension functions of constant length are just the sets with disjunctive characteristic sequences. We also show that these finite-state generic sets are not regular but may be context free.
Furthermore, we introduce some stronger finite-state genericity notions based on regular extension functions of nonconstant length and discuss their properties.
(The presented results are joint work with Edgar Busse.)

Information in and size of timed languages
Eugene Asarin, Université Paris Diderot - Paris 7, France

For timed languages, we define measures of their size: volume for a fixed finite number of events, and entropy (growth rate) as asymptotic measure for an unbounded number of events. These measures can be used for comparison of languages, and the entropy can be viewed as information contents of a timed language. In case of languages of deterministic timed automata, we give exact formulas for volumes. Next we characterize the entropy, using methods of functional analysis, as a logarithm of the leading eigenvalue (spectral radius) of a positive integral operator. We devise several methods to compute the entropy: a symbolical one for so-called "1 1/2-clock" automata, and two numerical ones: one using techniques of functional analysis, another based on discretization.

(The talk is based on Concur'09, FORMATS'09, FSTTCS'10 articles with A. Degorre, and ongoing work with N. Basset, A. Degorre, D. Perrin, )

Rational subsets of groups
Robert Gilman, Stevens Institute of Technology, USA

The rational subsets of a group are the closure of its finite subsets under union, product, and generation of submonoid, i.e., the images of regular languages under monoid homomorphisms. Rational subsets of groups have been studied for many years and are closely connected with many group-theoretic phenomena. We will review these connections and mention some recent developments.

Learning XML specifications from well-formed documents
Timo Kötzing, Max-Planck-Institute for Computer Science, Germany

Given a sample of well-formed XML documents produced with a general XML specification in mind, can we extract (learn) a well-fitting XML specification? This problem arises when no such schema is provided by the originator(s) of the sample, maybe doesn't even exist, or is much too general. The most difficult to learn part of an XML specification is in the regular expressions used, which are, in general, not learnable in the limit from positive data. Bex et al. 2010, as well as others, consider the learnability of subregular language classes which typically occur in XML specifications. They give a number of Gold-style learning results, including concrete algorithms for generalizing from incomplete data. The two language classes we consider here are those based on Chain Regular Expressions and Single Occurrence Regular Expressions, respectively. In our work we give new learning algorithms for these two language classes. Both of them are very efficient, and both return a minimal generalization of the provided sample (each hypothesis is "descriptive").

This is ongoing work, joint with Dominik Freydenberger.

Isomorphism of automatic trees
Jiamou Liu, Auckland University of Technology, New Zealand

This talk continues from the previous talk to focus on the isomorphism problem of classes of automatic structures. In particular, the talk will focus on automatic trees. Among other results we will show the following:

(a) The isomorphism problem for automatic trees of height n \geq 2 is $\Pi^0_{2n-3}$-complete.

(b) The isomorphism problem for well-founded automatic order trees is recursively equivalent to true first-order arithmetic.

(c) The isomorphism problem for automatic order trees is $\Sigma^1_1$-complete. We will also discuss isomorphism of \omega-automatic trees and tree-automatic well-founded trees.

Isomorphism of automatic equivalence relations
Markus Lohrey, University of Leipzig, Germany

The isomorphism problem for a class C of computable structures asks, whether two given members of C are isomorphic. It is well-known that the isomorphism problem for the class of all computable structures is complete for the class Sigma^1_1.
Khoussainov, Nies, Rubin, and Stephan proved that even for automatic structures the isomorphism problem is complete for Sigma^1_1. In this talk, I will show that the isomorphism problem for automatic equivalence relations is undecidable (in fact, it is co-r.e.-complete. The proof uses Hilbert's 10th problem.

An application of automatic structures to inductive inference and the notion of robust learning
Eric Martin, University of New South Wales, Australia

The field of inductive inference is mainly concerned with the identification in the limit of recursively enumerable sets of natural numbers from positive data: given such a set L and an infinite enumeration (e_i) of all members of L (possibly with repetitions, and possibly using a special "non-number" symbol), the goal is to output the description of a Turing machine that halts on a natural number n provided as input if and only if n belongs to L. Sanjay Jain, Frank Stephan and myself propose to restrict the class of languages under consideration to automatic classes of languages. Rather than being natural numbers, the elements of a language in such a class are strings over a fixed alphabet. It is furthermore required that if (L_i) is such a class, then some multi-input automaton recognises the set of all pairs (i,x) such that string x belongs to language L_i. We focus on a constraint imposed on learners, that of robustness. Intuitively, a class is robustly learnable in the limit if that class is closed under the application of particular transformations such as general recursive operators. While the topic of robust learning has been investigated in depth in the context of identification in the limit of graphs of functions, and has proved to be a particularly important concept, no satisfactory notion of robust learning for language learning had emerged so far. We show that restricting to automatic classes of languages makes it possible to propose a natural notion of robust learning that yields appealing characterisation results (results that provide a natural necessary and sufficient condition for a class of languages to be robustly learnable). More precisely, we consider a number of extra constraints on learning such as consistency (making sure that the conjectures made by a learner are consistent with the data seen so far), conservativeness (making sure that a conjecture does not change unless a new datum makes the previous conjecture impossible), confidence (which bounds the number of mind changes a learner can make), and strong-monotonicity (which rules out that a hypothetical language L_1 not larger than a hypothetical language L_2 be proposed on the basis of an expanded set of data). These constraints can be combined in ways that also yield characterisation results. Finally, further characterisation results can be obtained in the context of a different family of learning paradigms, where learners ask membership, subset and superset queries rather than passively receiving data. Overall, the study presented in this talk provides strong evidence that the field of inductive inference can greatly benefit from the field of automatic structures.

Finite-state randomness: on the prediction strength of finite automata
Wolfgang Merkle, University of Heidelberg, Germany

We review the celebrated result of Agafonoff and of Schnorr and Stimm that with respect to finite automata the usual randomness notions defined by selecting from or betting on the bits of an infinite sequence are all equivalent to the concept of a normal sequence, i.e., a sequence in which every given word of length n occurs in the limit with its expected frequency of 2 to the power of minus n. Further we review work of Merkle and Reimann that shows that already for computation models that are slightly more powerful than finite automata this equivalence becomes invalid.

Automata for pattern languages
Daniel Reidenbach, Loughborough University, UK

The implementation of regular expressions in most programming languages and text editors (and the like) differs quite dramatically from the usual definition of this concept in theoretical computer science. In particular, the former variant (commonly referred to as REGEX) often supports so-called backreferences, which operate in a manner that is similar to that of variables in pattern languages and can be used to specify a variety of non-regular languages. While implementations of 'ordinary' regular expressions are supported by the well-developed theory of finite automata, the existing automata models that could be used for recognising pattern languages and REGEX do not fit with the specific properties of these concepts. Therefore, most REGEX engines make use of more or less sophisticated backtracking algorithms that completely ignore the achievements of automata theory. In order to fill this gap, an automata model shall be introduced and studied that (i) allows for an easy integration of well-established methods for DFA/NFA, (ii) can directly be applied to any given pattern or certain types of REGEX, and (iii) facilitates a thorough analysis of the complexity of the membership problem for classes of languages generated by such concepts.
(This is ongoing work with Markus L. Schmid, partly presented at the conference CIAA'10.)

The "Trio-zoo" - classes of formal languages generated from one language by rational transduction
Klaus Reinhardt, Eberhard-Karls Universt?t T?bingen, Germany

We consider nondeterministic automata with various kinds of storage devices (like for example a pushdown-store). Since the corresponding language classes are closed under homomorphism, inverse homomorphism and intersection with regular language (the trio-operations), the word problem is decidable if and only if the emptiness problem is decidable. We suggest that the most convenient (and shortest) way to formally describe such storage devices is to define corresponding protocol languages, which generate the class by rational transduction. For example the contextfree languages are generated by the Semi-Dyck-Language. A big advantage shows when we prove an inclusion between two classes: Instead of an algorithmic description of the simulation of one automaton by another, we can just give a rational transducer from one protocol language to another. We present many examples like variants of counters and consider decidability questions.

Monadic-interpretations in scattered trees
Sasha Rubin, INRIA Rennes, France

The MSO-theory of the full binary tree interprets many others. For instance, the rational order is 1-dimensionally MSO-interpretable in the tree. We present non-interpretability results in scattered trees --- these are trees that do not embed the full binary tree. As might be expected, these trees behave more like $\omega$ than the full binary tree. The results are of the following form: trees and orders of large rank can not be interpreted in trees of small rank. The most general interpretations we consider are multi-dimensional set-interpretations allowing finitely many unary predicates as parameters. Joint work with Alex Rabinovich.

Constructing invariants for hybrid automata
Sriram Sankaranarayanan, University of Colorado Boulder, USA

The connection between invariants of programs, mathematical induction and fixed points of monotone operators over lattices is well-known. In this work, we will discuss techniques for computing positive invariants of continuous systems described by Ordinary Differential Equations (ODE) and extensions to hybrid automata that combine the continuous evolution of state variables with discrete switching between modes. Since mathematical induction principle cannot, in general, be used as a basis for proving continuous system invariants, we present analogous approaches based on properties of continuous dynamical systems such as the Nagumo theorem.

Finally, we present extensions to some of the existing invariant generation approaches for programs to derive invariants for hybrid systems. These include constraint-based techniques which formulate and solve constraints over the unknowns of a template invariant form and the iterative technique based on the theory of abstract interpretation.

Automatic models of first-order theories
Pavel Semukhin, University of Regina, Canada

In joint work with F. Stephan, we study several model-theoretic properties of automatic structures. The topic of this research is inspired by computable model theory. Namely, we are interested in which results about computable structures can be transferred to the field of automatic structures. Typical questions here are:
1) given n>0, is there a theory with exactly n automatic models;
2) which models of an uncountably categorical theory can be automatic;
3) if the saturated model of the theory is automatic, is the prime model also automatic; and so on. In this talk we will discuss our progress on the above mentioned questions and related open problems.

The additive group of the rationals is not automatic
Todor Tsankov, Université Paris Diderot - Paris 7, France

A countable structure is called automatic if there exists a coding of the elements of its domain by strings in a finite alphabet so that the domain, the relations, and the graphs of the functions are regular languages. For example, the usual carry algorithm for adding integers translates into an automatic representation of the structure (Z, +).

The main result I am going to discuss is that the additive group of the rationals does not have such a presentation. This answers a question of Khoussainov and provides the first example of a finite rank abelian group which is not automatic. I will also explain the main ideas of the proof which relies on tools from additive combinatorics.

Time permitting, I will also discuss a recent extension of this result, due to Braun and Struengmann, that allows, for example, to classify all automatic torsion-free abelian groups of rank 1.

Towards automatic analysis of the chinese CTCS-3 high-speed train control regulations
Shaofa Yang, Shenzhen Institute of Advanced Technology and Chinese Academy of Sciences, China

We present preliminary work towards automatic analysis on the safety and efficiency of the Chinese CTCS-3 High-Speed Train Control Regulations, based on a publicly available technical overview. Emphasis is placed on developing techniques for fully automatic analysis of a dozen typical scenarios of operations.

Best viewed with IE 7 and above