Abstracts
The authors of accepted papers and posters can upload their camera-ready versions. See the pre-proceedings information.
Invited Papers
- Rusins Freivalds
Languages Recognizable by Quantum Finite Automata
There are several nonequivalent definitions of quantum finite automata. Nearly all of them recognize only regular languages but not all regular languages. On the other hand, for all these definitions there is a result showing that there is a language L such that the size of the quantum automaton recognizing L is essentially smaller than the size of the minimal deterministic automaton recognizing L.
For most of the definitions of quantum finite automata the problem to describe the class of languages recognizable by the quantum automata is still open. The partial results are surveyed in the talk.
The main part of the talk is devoted to unpublished results of the description of the class of the recognizable languages in terms of the second order predicate logics. This research is influenced by the results of R. Büchi (description of regular languages in terms of MSO), R. Fagin (description of NP in terms of ESO), J. v. Neumann (quantum logics), A. Barenco, C. H. Bennett et al. (universal quantum gates).
- Jacques Sakarovitch
The Language, the Expression and the (Small) Automaton.
Formal language theory, especially that part which consists in the study of the so-called regular or recognisable languages, is a model instance of Plato's myth of the cavern. The real objects are the languages—or the power series—potentially infinite and what we, poor computer scientists bound to manipulate finite objects, can only see are the expressions that denote, or the automata that recognize them. Hopefully, these expressions and automata are fairly faithful descriptions of the languages (or of the series) they stand for and all the more effective that one can take advantage of this double light.
In this talk, mostly a survey, I shall review the means that allow to go from one representation of the languages to the other and how, and to what extend, one can keep them small.
The first part will be a survey of the classical methods of computing an expression from an automaton and of computing an automaton from an expression. We shall discuss the relationship between the different expressions obtained from a given automaton and the ways of reaching a compact one. We shall classify the methods that build an automaton from an expression and present with more details the one which is probably the lesser known: Antimirov's construction of derived term automaton.
The second part will consists in a brief presentation of the notions of morphism and of quotient of automata: the latter being a way of reducing the size of an automaton while retaining its structure and keeping the accepted language. The minimal quotients of all automata that recognize a given language L are to be found in an automaton UL canonically associated to L: the universal automaton of L, an object often rediscovered in the last 35 years.
In the third and last part, I shall address the problem of finding an algorithm that is inverse to those which compute an expression from an automaton, hence taming the combinatorial explosion induced by the latter ones. A solution has been given—to some extend—which makes use of the notions presented in the first two parts; it requires the addition of some information to the original automaton. Reducing the amount of such information is the subject of ongoing work and I shall indicate three directions of research that seem promising for this purpose.
This talk will be based on recent papers of mine, written in collaboration with Sylvain Lombardy, and where complete references are to be found.
References
- S. Lombardy and J. Sakarovitch, Star height of reversible languages and universal automata. Proc. of LATIN'02, Lect. Notes in Comp. Sc. 2286 (2002), 76–90.
- S. Lombardy and J. Sakarovitch, Derivatives of rational expressions with multiplicity. Theoretical Comput. Sci. 332 (2005), 141–177.
- S. Lombardy and J. Sakarovitch, How expressions can code for automata. RAIRO -- Theoret. Informatics and Application 39 (2005), 217–237.
Accepted Papers
Here are the twenty six accepted papers, in alphabetical order of the first author:
- Marcella Anselmo and Maria Madonia
Simulating Two-Dimensional Recognizability by Pushdown and Queue Automata.
The aim of this paper is to investigate sequential models to describe two-dimensional languages. The intent is to add more capabilities to 4NFA in order to encompass a wider class of languages. We show that any (tiling) recognizable language can be simulated by a 4NFA with an extra queue whose size is bounded by the minimum of the two dimensions of a picture; and that 2NFA (i.e. automata moving only in two directions) with an analogous queue are sufficient when the alphabet is unary. A special class of recognizable languages can be simulated also by 4-way pushdown automata with a stack of size bounded by the sum of the two dimensions of the picture. Such a class is also characterized by a recursive definition involving the operations of union, intersection and a new diagonal overlapping operation applied to languages recognized by 2NFA.
- Arnaud Bailly, Mireille Clerbout and Isabelle Simplot-Ryl
Component Composition Preserving Behavioural Contracts Based on Communication Traces.
This paper investigates the compositional properties of reusable software components defined with explicit dependencies and behavioural contracts expressing rely-guarantee specifications in the form of communication traces. In this setting, connection of components through their matching ports is indeed compositional and yields a new component or composite that respects its constituents' contracts. Thus the behaviour of the composite is computed from the behaviours of its constituents and is known to conform to the contracts without any new proof.
- Miklos Bartha
Strong Retiming Equivalence of Synchronous Schemes.
Strong retiming equivalence is the join of two basic equivalence relations of synchronous schemes: strong equivalence and retiming equivalence, which play an important role in the optimization of synchronous systems. Each of these equivalences is characterized separately in an algebraic/category theoretic framework, and the characterization is carried over to the join of them. Tree-reducible schemes are introduced to facilitate the proof that strong retiming equivalence is decidable.
- Cedric Bastien, Jurek Czyzowicz, Wojciech Fraczak and Wojciech Rytter
Prime Normal Form and Equivalence of Simple Grammars.
We give the first algorithm to decompose a simple context-free language into primes. A prefix-free language is a prime if it cannot be decomposed into a concatenation of two prefix-free languages. We show that we can check in polynomial time if a language generated by a simple context-free grammar is a prime. Our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into Prime Normal Form (PNF); a simple grammar is in PNF if all its nonterminals define primes. We also improve the complexity of testing the equivalence of simple grammars. The best previously known algorithm for this problem worked in O(n13) time. We improve it to O(n7 log2 n) and O(n5 polylog v) deterministic time, and O(n4 polylog n) randomized time, where n is the total size of the grammars involved, and v is the length of a shortest string derivable from a nonterminal, maximized over all nonterminals. Our improvement is based on a version of Caucal's algorithm from [Caucal 1989].
- Cezar Câmpeanu, Andrei Paun and Jason R. Smith
An Incremental Algorithm for Minimal Deterministic Finite Cover Automata.
A fast incremental algorithm for constructing minimal DFCA for a given language is presented. Since it was shown that DFCA for a language L can have less states than the DFA for L, this techniques seems to be the best choice for incrementally building the automaton for a large language especially when the number of states in the DFCA is significantly less than the number of states in the
equivalent
DFA. We have implemented the proposed algorithm and have tested it with the best known DFCA minimization technique.- Antonio Cano and Pedro García
Finite Automata and Unions of Regular Patterns With Bounded Constant Segments.
The class of unbounded unions of regular pattern languages with bounded constant segments is identifiable from positive data in the limit. Otherwise, no efficient algorithm that performs the inference of this class of languages is known. We propose a solution to this problem using the existing connexion between the positive variety of languages of dot depth 1/2, LJ+ and the class of unbounded union of pattern languages RP+L.
- Thomas Claveirole, Sylvain Lombardy, Louis-Noël Pouchet and Jacques Sakarovitch
Inside Vaucanson.
This paper presents some features of the Vaucanson plateform. We describe some original algorithms on weighted automata and transducers (computation of the quotient, conversion of a regular expression into a weighted automaton, and composition). We explain how complex declarations due to the generic programming are masked from the user and finally we present a proposal for an XML format that allows implicit descriptions for simple types of automata.
- Akio Fujiyoshi and Ikuo Kawaharada
Deterministic Recognition of Trees Accepted by a Linear Pushdown Tree Automaton.
In this paper, a deterministic recognition algorithm for the class of tree languages accepted by (nondeterministic) linear pushdown tree automata (L-PDTA) is proposed. L-PDTA accept an important class of tree languages since the class of their yield languages coincides with that generated by tree adjoining grammars (TAGs). The proposed algorithm is obtained by combining a bottom-up parsing procedure on trees with the CKY algorithm. The run time of the algorithm is O(n4), where n is the number of nodes of an input tree.
- Yo-Sub Han and Derick Wood
Shorter Regular Expressions from Finite-State Automata.
We consider the use of state elimination to construct shorter regular expressions from finite-state automata. Although state elimination is an intuitive method for computing regular expressions from finite-state automata, the resulting regular expressions are often very long and complicated. We examine the minimization of finite-state automata to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given finite-state automata. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that lead to shorter regular expressions based on vertical chopping and horizontal chopping.
- Subramanian Hariharan and Priti Shankar
Compressing XML Documents with Finite State Automata.
We propose a scheme for automatically generating compressors from DTD specifications. Our algorithm is a lossless adaptive algorithm where the model used for compression and decompression is generated automatically from the DTD, and is used in conjunction with an arithmetic compressor to produce a compressed version of the document. The structure of the model mirrors the syntactic specification of the document. We have implemented the compressor and provide the results of experiments on some large XML databases whose DTD's are specified. We note that the average compression is better than that of XMLPPM, the only other on-line tool that we are aware of. Our tool is able to compress massive documents where XMLPPM failed to work as it ran out of memory. We believe that the main appeal of this technique is the fact that the underlying model is so simple and yet so effective.
- Johanna Högberg
Wind in the Willows—Generating Music by Means of Tree Transducers.
We implement a rule-based system for algorithmic composition. This system, that we call Willow, resides in the Treebag environment and consists of a sequence of formal devices, familiar from the field of tree grammars and tree transducers. Since these devices are well studied, we can apply known results to derive the descriptive complexity of the system as a whole.
- Oscar H. Ibarra and Hsu-Chun Yen
On Deterministic Catalytic Systems.
We look at a 1-membrane catalytic P system with evolution rules of the form Ca → Cv or a → v, where C is a catalyst, a is a noncatalyst symbol, and v is a (possibly null) string representing a multiset of noncatalyst symbols. (Note that we are only interested in the multiplicities of the symbols.) A catalytic system can be regarded as a language acceptor in the following sense. The system starts with an initial configuration wz, where w is a fixed string of catalysts and noncatalysts not containing any symbol in z, and z = a1n1…aknk for some nonnegative integers n1,…,nk, with {a1,…,ak} a distinguished subset of noncatalyst symbols (the input alphabet). At each step, a maximal multiset of rules are nondeterministically selected and applied in parallel to the current configuration to derive the next configuration (note that the next configuration is not unique, in general). The string z is accepted if the system eventually halts. It is known that a 1-membrane catalytic system is universal in the sense that any unary recursively enumerable language can be accepted by a 1-membrane catalytic system (even when all the rules are purely catalytic, i.e., of the form Ca → Cv). A catalytic system is said to be deterministic if at each step, there is a unique maximally parallel multiset of rules applicable. It has been an open problem whether deterministic such systems are universal. We resolve this question in the negative: We show that the membership problem for deterministic catalytic systems is decidable. In fact, we show that the Parikh map of the language ⊆a1*…ak* accepted by any deterministic catalytic system is a simple semilinear set which can be effectively constructed. Since nondeterministic 1-membrane catalytic system acceptors (with 2 catalysts) are universal, our result gives the first example of a P system for which the nondeterministic version is universal, but the deterministic version is not. We also show that for a deterministic 1-membrane catalytic system using only rules of type Ca → Cv, the set of reachable configurations from a given initial configuration is an effective semilinear set. The application of rules of type a → v, however, is sufficient to render the reachability set non-semilinear. Our results generalize to multi-membrane deterministic catalytic systems. We also consider deterministic catalytic systems which allow rules to be prioritized and investigate three classes of such systems, depending on how priority in the application of the rules is interpreted. For these three prioritized systems, we obtain contrasting results: two are universal and one only accepts semilinear sets.
- Tomasz Jurdzinski and Friedrich Otto
Restricting the Use of Auxiliary Symbols for Restarting Automata.
The most general models of restarting automata make use of auxiliary symbols in their rewrite operations. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.
- André Kempe, Jean-Marc Champarnaud, Jason Eisner, Franck Guingne and Florent Nicart
A Class of Rational n-WFSM Auto-Intersections.
Weighted finite-state machines with n tapes describe n-ary rational string relations. The join n-ary relation is very important regarding to applications. It is shown how to compute it via a more simple operation, the auto-intersection. Join and auto-intersection generally do not preserve rationality. We define a class of triples ⟨A,i,j⟩ such that the auto-intersection of the machine A w.r.t. tapes i and j can be computed by a delay-based algorithm. We point out how to extend this class and hope that it is sufficient for many practical applications.
- Joachim Klein and Christel Baier
Experiments with Deterministic ω-Automata for Formulas of Linear Temporal Logic
This paper addresses the problem of generating deterministic ω-automata for formulas of linear temporal logic, which can be solved by applying well-known algorithms to construct a nondeterministic Büchi automaton for the given formula on which we then apply a determinization algorithm. We study here in detail Safra's determinization algorithm, present several heuristics that attempt to decrease the size of the resulting automata and report on experimental results.
- Louis Latour
Computing Affine Hulls Over Q and Z From Sets Represented by Number Decision Diagrams.
Number Decision Diagrams (NDD) are finite automata representing sets of integer vectors and have recently been proposed as an efficient data structure for representing sets definable in Presburger arithmetic. In this context, some work has been done in order to generate formulas or set of generators from the NDDs. Taking another step in this direction, this paper present algorithms that takes as input an NDD and computes the affine hull over Q or over Z of the set represented by the NDD, i.e., the smallest set defined by a conjunction of equations (and congruence relations over Z) which includes the set represented by the NDD. Our algorithms run in time O(|Q| · |Σrn| · n) and O(|Q|3 · |Σrn| · n3) respectively, where n is the number of components of the vectors represented by the NDD, and |Q| and Σrn are the number of states and the alphabet of the NDD. On a prototype implementation, the computations of affine hulls of NDDs with more than 100000 states are done in seconds and numbers remain small.
- Markus Lohrey and Sebastian Maneth
Tree Automata and XPath on Compressed Trees.
The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts in a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the XPath evaluation problem on trees that are compressed via straight-line context-free tree grammars is investigated.
- Parosh Aziz Abdulla, Johann Deneux, Lisa Kaati and Marcus Nilsson
Minimization of Nondeterministic Automata with Large Alphabets.
There has been several attempts over the years to solve the minimization problem for finite automata. One of the most famous algorithms is the one suggested by Paige and Tarjan. The algorithm has a complexity of O(m log n) time where m is the number of edges and n is the number of states in the automaton. A bottleneck in the application of the algorithm is often the number of labels which may appear on the edges of the automaton. In this paper we adapt the Paige-Tarjan algorithm to the case where the labels are symbolically represented using Binary Decision Diagrams (BDDs). We show that our algorithm has an overall complexity of O(l · m · log n) where l is the size of the alphabet. This means that our algorithm will have the same worst case behaviour as other algorithms. However, as shown by our prototype implementation, we get a vast improvement in performance due the compact representation provided by the BDDs.
- Radek Pelanek and Jan Strejcek
Deeper Connections between LTL and Alternating Automata.
It is known that Linear Temporal Logic (LTL) has the same expressive power as alternating 1-weak automata (A1W automata, also called alternating linear automata or very weak alternating automata). A translation of LTL formulae into a language equivalent A1W automata has been introduced in [MSS88]. The inverse translation has been developed independently in [Roh97] and [LT00]. In the first part of the paper we show that the latter translation wastes temporal operators and we propose some improvements of this translation. The second part of the paper draws a direct connection between fragments of the Until-Release hierarchy [CP03] and alternation depth of nonaccepting and accepting states in A1W automata. We also indicate some corollaries and applications of these results.
- Wojciech Rytter
The Structure of Subword Graphs and Suffix Trees of Fibonacci Words.
We use automata-theoretic approach to analyze properties of Fibonacci words. The directed acyclic subword graph (DAWG) is a useful deterministic automaton accepting all suffixes of the word. We show that DAWGs of Fibonacci words have particularly simple structure. The simple structure of paths in these graphs gives simplified alternative proofs and new interpretation of several known properties of Fibonacci words. The structure of lengths of paths in the compacted subword graph corresponds to a number-theoretic characterization of occurrences of subwords in terms of Zekendorff Fibonacci number system. Using the structural properties of DAWGs it can be easily shown that for a string w we can check if w is a subword of a Fibonacci word in time O(|w|) and O(1) space. Compact DAWGs of Fibonacci words show a very regular structure of their suffix trees and show how the suffix tree for the Fibonacci word grows (extending the leaves in a very simple way) into the suffix tree for the next Fibonacci word.
- Christoph Schulte Althoff, Wolfgang Thomas and Nico Wallmeier
Observations on Determinization of Büchi Automata.
The two determinization procedures of Safra and Muller-Schupp for Büchi automata are compared, based on an implementation in a program called OmegaDet.
- Tamara L. Shcherbak
The Interval Rank of Monotonic Automata.
We solve the 'order preserving' version of the generalized Cerný problem (also known as the rank problem). Namely, for all n and k such that 2≤k≤n, we determine the least number l (n,k) such that for each monotonic automaton with n states and interval rank k there exists a word of length l (n,k) that compresses the state set of the automaton to an interval of length k.
- Tadahiro Suda and Haruo Hosoya
Non-backtracking Top-down Algorithm for Checking Tree Automata Containment.
Checking tree automata containment is a fundamental operation in static verification of XML processing programs. However, tree automata containment problem is known to be EXPTIME-complete and a standard algorithm with determinization of automata easily blows up even in practical cases. Hosoya, Vouillon, and Pierce have proposed a top-down algorithm that efficiently works for a large class of typical instances. However, there still remains a considerable inefficiency because of repeated calculation incurred by backtracking. In this paper, we propose a non-backtracking top-down algorithm which improves this inefficiency. In the algorithm, we introduce
dependencies
among performed computations and, by exploiting these, we can recover certain kinds of information lost by backtracking. One difficulty in constructing such algorithm is, however, that, since some dependency information can be useless, we may be misled to needless computation by using such information. To alleviate this problem, we carefully check the usefulness of each dependency whenever we use it. Since these checks introduce a subtlety to our algorithm, we rigorously formalize it with a correctness proof. Our preliminary experiments show that our algorithm works more efficiently compared to the previous algorithm.- Hellis Tamm, Matti Nykänen and Esko Ukkonen
Size Reduction of Multitape Automata.
We present a method for size reduction of two-way multitape automata. Our algorithm applies local transformations that change the order in which transitions concerning different tapes occur in the automaton graph, and merge suitable states into a single state. Our work is motivated by implementation of a language for string manipulation in database systems where string predicates are compiled into two-way multitape automata. Additionally, we present a (one-tape) NFA reduction algorithm that is based on a method proposed for DFA minimization by Kameda and Weiner, and apply this algorithm, combined with the multitape automata reduction algorithm, on our multitape automata.
- Manuel Vilares, Juan Otero and Jesús Vilares
Robust Spelling Correction.
The paper introduces a robust spelling correction technique do deal with ill-formed input strings, including unknown parts of unknown length. In contrast to previous works, we derive profit from a finer dynamic programming construction, which takes advantage of the underlying grammatical structure, leading to an improved computational behavior and repair quality. The formal description applies a deductive approach in order to simplify this task, separating it from the interpretation strategy, and including cut-off facilities.
- Jan Zdarek and Borivoj Melichar
On Two-Dimensional Pattern Matching By Finite Automata.
This paper presents a general concept of two-dimensional pattern matching using conventional (one-dimensional) finite automata. Then two particular models and methods, implementations of the general principle, are presented. First of these two models presents automata based version of Bird and Baker approach with lower space complexity than has the original algorithm. The second one introduces a new model for the two-dimensional approximate pattern matching using the two-dimensional Hamming distance.
Accepted Posters
Eight papers have been accepted as posters:
- Monica del Pilar Canales Chacon and Michael Vielhaber
On a Class of Bijective Binary Transducers with Finitary Description Despite Infinite State Set.
Isometries f on infinite symbol sequences a∈Aω, where A is some alphabet, can be computed by bijective transducers. Some of these f are computable by a transducer with finite state set (we then say
f is finite
), but most are not. However, every f has an associated shift commutator [σ,f] := σ-1 • f-1 • σ • f, again an isometry. We focus now on the case, where this [σ,f] is finite, but f is not.We show that iterated application of n copies of [σ,f] simulates f, with n→∞ the growing length of the input to f. We then use this result to define a (necessarily infinite) transducer Tf for f in terms of T[σ,f], e.g. state set Qf defined as words from Q*[σ,f], nextstate and output functions for Tf defined in terms of those for T[σ,f].
It turns out that every state working on an nth input symbol an never needs more than O(n) bit operations to define its output and to determine the next state. Also, all the N := 2n+1-1 states sufficient to deal with all possible input prefixes of length up to n from ∪k=0…n Ak, can be tested for pairwise equivalence in O(N2+2log2q) operations, where q=|Q[σ,f]| is the number of states of the finite shift commutator.
An interesting example is the isometry c induced by Collatz' 3N+1 conjecture, where the states in Q*[σ,c] are
telling names
for what happens within c.- Jan Daciuk, Agata Savary and Denis Maurel
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata.
Pseudo-minimal automata can be used to implement such important functions as dynamic perfect hashing. The only existing algorithm requires data to be sorted in an unusual way. We present three other algorithms that can use either unsorted data, or data in a more natural order.
- Pedro García, José Ruiz, Antonio Cano and Gloria Alvarez
Is learning RFSAs better than learning DFAs?
Inference of RFSAs has been recently presented as an alternative to inference of DFAs if the target language has been obtained by a random generation of NFAs. We propose in this paper the algorithm RPNI2, which is a variation of the previous RPNI, that also outputs DFAs as hypothesis. The experiments done show that RPNI2 has an error rate very similar to the rate obtained in the inference of RFSAs, but the size of the hypothesis is substantially smaller.
- Colin de la Higuera, Frédéric Piat and Frédéric Tantini
Learning Stochastic Finite Automata for Music.
Stochastic deterministic finite automata have been introduced and are used in a variety of settings. We use them to model musical styles: a same automaton can be used to classify new melodies but also to generate them. Through grammatical inference these automata are learned and new pieces of music can be parsed. We show that this works by proposing promising classification results and discuss further work.
- Miklós Krész
Simulation of Soliton Circuits.
Soliton automata are the mathematical models of certain possible molecular switching devices called soliton circuits. An efficient method is worked out for the simulation of soliton circuits in terms of soliton automata. The running time of the algorithm is polynomial in the number of states, vertices and edges of the underlying soliton graph.
- José João Morais, Nelma Moreira and Rogério Reis
Acyclic Automata with Easy to Find Short Regular Expressions.
Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is easy to find a regular expression that has linear size. We call those automata UDR. An UDR automaton is characterized by properties of its underlying digraph. We present a characterisation theorem and an efficent algorithm to determine if an acyclic automaton is UDR. This algoritm can be adapted to compute a short regular expression equivalent to a given UDR automaton.
- Rimma Podlovchenko, Dmitry Rusakov and Vladimir Zakharov
On the Equivalence Problem for Programs with Mode Switching.
We study a formal model of imperative sequential programs. In this model programs are viewed as deterministic finite automata whose semantics is defined on Kripke structures used in the framework of dynamic logics. We focus on the equivalence problem for some specific class of programs—programs with mode switching—whose runs can be divided into two stages. In the first stage a program selects an appropriate mode of computation. Several modes may be tried (switched) in turn before making the ultimate choice. Every time when the next mode is put to a test, the program brings the data back to the initial state. In the second stage of the run, once a definitive mode is fixed, the final result of computation is generated. We develop a new technique for simulating the behavior of such programs by means of finite automata and demonstrate that the equivalence problem for programs with mode switching is decidable within a polynomial space. By revealing a close relationship between the equivalence problem for this class of programs and the intersection emptiness problem for deterministic finite state automata we show that the former is PSPACE-complete.
- Isabelle Tellier
Automata and AB-Categorial Grammars.
In this paper, we study the relationships between automata and a linguistic formalism known as AB-categorial grammars, which can generate every ε-free context-free language. First, we identify subclasses of AB-categorial grammars generating regular languages and explain how they relate to usual finite state automata. Then, a new class of generalized automata called recursive automata is introduced. A recursive automaton can be considered as a special case of a recursive transition network, but reduced to one single automaton. We define two variants of recursive automata and show that each of them can generate at least the same structures as the ones produced by one of the two variants of unidirectionnal AB-categorial grammars. Finally, to generate the structures produced by bidirectional AB-categorial grammars, we show that a pair of mutually recursive automata is always enough.