Research in Automata and Language Theory
by Vesa Halava

Updated November 2006

Integer weighted finite automata

An integer weighted finite automaton, FA(Z) for short, is a machine, which consist of a finite automaton and a counter. The counter operates in additive group of integers (and the transitions in the automaton do not depend on the value of it). An integer weight is assigned to every transition of the underlying automaton A, and an input word is accepted if there exists a path in A such that: (1) it starts from the initial state, (2) reads the input word, and, (3) the sum of the weights of the transitions used in the reading is zero. This model of a machine was defined in [1], where the universality was proven to be undecidable for the FA(Z). The properties of the family of the languages accepted with FA(Z) automata were studied in [2].

Valence languages and shifted PCP

The family of languages accepted by the automata FA(Z) is equivalent to the family of regular Valence languages. Our study of the automata FA(Z) produced new results on the representations of Valence languages. Namely, a language is a regular Valence language if and only if it is a coding of a shifted equality set. A shifted equality set is a set of solutions of the special modification of the Post Correspondence Problem. In the shifted PCP, the instances consists of two (word) morphisms g,h: A* ® B*, where A and B are alphabets, and a letter a in B. The task is to determine whether or not there exists a (nonempty) word w in A* such that

a g(w)=h(w).

Now a shifted equality set is for an instance J=(a,g,h) is

E(J)={w | a g(w)=h(w)}.

The connections between the FA(Z) languages, Valence languages and shifted equality sets was found in [3]. The representations using the equality sets of the shifted PCP was extended to some classical families such as regular languages and recursively enumerable were studied in [4-6].

Matrices over Laurent polynomials

There exists a classical connection between the finite automaton and rational formal power series, via the integer matrices. In [7] and [8] it was shown that there exist a similar connection between the languages defined by FA(Z) automata and the formal power series over Laurent polynomials, and this connection is via the matrices over the Laurent polynomials. This representation yield a nice undecidability result for 5 x 5-matrices over Laurent polynomials. The connection might prove useful in connection with the decidability of other Diophantine problems.

My Homepage
  1. Vesa Halava and Tero Harju
    Undecidability in integer weighted finite automata
    Fundamenta Informaticae 39 (1999), 189 - 200.
  2. Vesa Halava and Tero Harju
    Languages accepted by integer weighted finite automata
    in
    Jewels are Forever
    (Karhumäki, Maurer, Paun, Rozenberg, eds), Springer Verlag, 1999, 123 - 134.
  3. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:
    Valence languages generated by equality sets pdf file:
    J. Automata Lang. Combin. 9 (2004), 399-406.
  4. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:
    Equality sets for recursively enumerable languages pdf file:
    Theoret. Informatics Appl. 39(4) (2005), 661-675.
    doi:10.1051/ita:2005035
  5. Vesa Halava, Tero Harju, and Michel Latteux:
    Representation of regular languages by equality sets
    Bulletin of the EATCS 86 (2005), 225-228.
  6. Vesa Halava, Tero Harju and Michel Latteux:
    Equality sets of prefix morphisms and regular star languages pdf file:
    Information Proc. Let. 94 (2005), 151-154.
  7. Vesa Halava and Tero Harju:
    Undecidability in matrices over Laurent polynomials ps.gz pdf file: pdf
    Adv. Applied Math. 33 (2004), 747 - 752.
    doi:10.1016/j.aam.2004.04.002
  8. Vesa Halava
    Integer Weighted Finite Automata, Matrices and Formal Power Series over Laurent Polynomials pdf file:
    in Theory is Forever, (J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg, eds.) Springer, 2004 pp. 81-88.