AFL 2008

The 12th International Conference on
Automata and Formal Languages
May 27-30, 2008, Balatonfüred, Hungary

Invited speakers

 

  Viliam Geffert  (Kosice, Slovakia): Hyper-Minimizing Minimized Deterministic Automata

Abstract: We present an algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs.

Within a class of finitely differing languages, the hyper-minimized automaton is not necessarily unique. There may exist several non-isomorphic machines using the minimum number of states, each accepting a separate language finitely-different from the original one. We will show that there are large structural similarities among all these smallest automata.

(Joint work with Andrew Badr, Nashville/TN, U.S.A. and Ian Shipman, Chicago/IL, U.S.A.)

 

  Markus Lohrey  (Leipzig, Germany): Algorithmics on compressed strings

Abstract: In recent years, straight-line programs (SLPs) turned out to be a convenient formalism for investigating algorithms on compressed string data. An SLP is a context-free grammar that generates exactly one string w. Since the length of the generated string w may grow exponentially with the size of the SLP, the latter may be seen as a compressed representation of w. The output of many practical compression algorithms, like for instance those of the Lempel-Ziv family, can be considered as SLPs. The talk will give an overview on recent complexity results for algorithmic string problems, where the input string is given compressed as an SLP. In particular, upper and lower complexity bounds for word problems for various language classes will be considered. Also applications in combinatorial group theory will be presented.

 

  Ion Petre  (Turku, Finland): Mathematics of gene assembly in ciliates

Abstract: Ciliates are an old and diverse group of unicellular eukaryotes. One of their unique features is that they have two types of functionally different nuclei, each present in multiple copies in each cell: micronuclei and macronuclei. The difference between the micronuclear and the macronuclear genome is striking, especially in Stichotrichs, on which we concentrate in this talk. While macronuclear genes are contiguous sequences placed in general on their own molecules, micronuclear genes are placed on long chromosomes, interrupted by stretches of non-coding material. Even more striking is that the micronuclear genes are split into several blocks (up to 44 of them in certain species), with the blocks arranged in a shuffled order, separated by non-coding material. Some blocks may even be inverted! At some stage during sexual reproduction, ciliates assemble the blocks in the orthodox order to yield the transcription able macronuclear gene. In this process, ciliates make use of some short specific sequences at the extremities of each MDS in the same way as pointers are used in computer science. Indeed, each coding block ends with a short sequence of nucleotides that is repeated in the beginning of the coding block that should follow it in the orthodox order.

We will give in the talk an overview of some of the research done on the mathematics of gene assembly in ciliates. Some of the techniques are from formal language theory, others are from combinatorics and graph theory, while others are from theory of computability. We discuss several models stemming from the process of gene assembly, based on permutations, strings, graphs, or formal languages. We discuss results on closure properties of various language families, invariants, completeness, parallelism, and even computing paradigms based on gene assembly. We will also discuss a number of open problems in the area.

 

  Jacques Sakarovitch  (Paris, France): The sequentiality of automata and transducers

Abstract: Being sequential --- or input deterministic --- is a fundamental property of machines, understood here as automata with output, the output being taken in an arbitrary semiring of multiplicities. To some extent, it amounts to say that the model can readily translate into a physical device. Whether a function realised by a given finite automaton can be realised by an equivalent sequential one is thus a natural as well as an essential question: a negative answer somehow implies that there is no finite realisation of the machine or that performing the computations described by the model may be very costly.

Every finite automaton may be seen as an automaton with output, as it was the case at the dawn of the theory with the Moore or Mealy machines and the first characterisation of sequentiality, due to Raney, goes back to the late fifties.

In this talk, I will try to survey and organise the known answers to the question of sequentiality. We shall see that depending on the semiring of multiplicities, the question goes from obvious to open, that the answer goes from yes to undecidable. One may note that two distinct complexity functions then arise, according to whether one wants just to know the answer or to compute the equivalent sequential automaton (in case it exists).

(Joint work with Sylvain Lombardy)

 

Maintained by the author.