## Research in Automata and Language Theory

by Vesa HalavaUpdated 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 automatonA, and an input word is accepted if there exists a path inAsuch 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 theFA(Z). The properties of the family of the languages accepted withFA(Z)automata were studied in [2].## Valence languages and shifted PCP

The family of languages accepted by the automataFA(Z)is equivalent to the family ofregular Valence languages. Our study of the automataFA(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 ashifted equality set. A shifted equality set is a set of solutions of the special modification of thePost Correspondence Problem. In the shifted PCP, the instances consists of two (word) morphismsg,h: A, where^{*}® B^{*}AandBare alphabets, and a letterainB. The task is to determine whether or not there exists a (nonempty) wordwinAsuch 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 asregular languagesandrecursively enumerablewere 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 byFA(Z)automata and the formal power series overLaurent polynomials, and this connection is via the matrices over the Laurent polynomials. This representation yield a nice undecidability result for5x5-matrices over Laurent polynomials. The connection might prove useful in connection with the decidability of other Diophantine problems.

My Homepage

Vesa Halava and Tero Harju

Undecidability in integer weighted finite automata

Fundamenta Informaticae39 (1999), 189 - 200.

Vesa Halava and Tero Harju

Languages accepted by integer weighted finite automata

inJewels are Forever

(Karhumäki, Maurer, Paun, Rozenberg, eds), Springer Verlag, 1999, 123 - 134.

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:

Valence languages generated by equality setspdf file:

J. Automata Lang. Combin.9 (2004), 399-406.

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, and Michel Latteux:

Equality sets for recursively enumerable languagespdf file:

Theoret. Informatics Appl.39(4) (2005), 661-675.

doi:10.1051/ita:2005035

Vesa Halava, Tero Harju, and Michel Latteux:

Representation of regular languages by equality sets

Bulletin of the EATCS86 (2005), 225-228.

Vesa Halava, Tero Harju and Michel Latteux:

Equality sets of prefix morphisms and regular star languagespdf file:

Information Proc. Let.94 (2005), 151-154.Vesa Halava and Tero Harju:

Undecidability in matrices over Laurent polynomialspdf file:

Adv. Applied Math.33 (2004), 747 - 752.doi:10.1016/j.aam.2004.04.002

Vesa Halava

Integer Weighted Finite Automata, Matrices and Formal Power Series over Laurent Polynomialspdf file:

inTheory is Forever, (J. Karhumäki, H. Maurer, G. Paun and G. Rozenberg, eds.) Springer, 2004 pp. 81-88.