Let A be a finite alphabet. A set of words over the alphabet a is called a language. In the formal language theory a language can be a by three different ways:
  1) by a device (automaton),
  2) by a grammar, or
  3) by certain operations.

A (finite) automaton can be thought as a very simple model for computer. It is a device, which has a finite memory and it either accepts or rejects given inputs. Some models have also outputs. If M is a finite automaton, which takes the words over the alphabet  A as inputs, then the set of words accepted by M is said to be a language accepted by M. There are many different models of automata, for example, (deterministic) finite automata, push-down automata, multitape automata and weighted automata. Turing machines can also be regarded as automata. So called tree automata are a very special form of automata. Different models of automata accept a different family of languages.

In the COWAT group the research of automata theory has focused on the following topics:

Image compression and generation: K. Culik and J. Karhumäki formalized the mathematical and automata theoretical concept of finite automata computing a real function. Using these weighted finite automata it is possible to compress images and also generate them. This method has been further developed by Culik and J. Kari.

Tree and directable automata: Balázs Imreh (Szeged) and Magnus Steinby have co-operated since the mid-1990s mainly on the following two topics.
  (1)  Directable automata and directing words. In this area especially bounds for minimal-length directing words for special classes of automata, sets of directing words and directable non-deterministic automata have been studied.
  (2)  Subdirect decompositions of finite automata and unary algebras. The subdirectly irreducible members of some varieties of finite automata have been characterised. On the other hand, subdirect decompositions of general unary algebras have been considered in terms of some notions, such as cores and Rees congruences, originating mostly in semigroup theory. This work has been done in co-operation with a group based in Nis. Since Tatjana Petkovic from that group is presently in Turku as a Post-doctorate Fellow, work along this line is expected to continue.

Decidability questions on automata theory: The equivalence problem for multitape finite automata was shown to be decidable by T. Harju and J. Karhumäki in 1991. This problem was considered as one of the most important problem for which the decidability status was not known until their proof.
   In 1997 V. Halava and T. Harju proved that the universality problem of the integer weighted finite automata is undecidable. This result was used in the new proof for undecidability of the equivalence of the finite substitutions on regular languages.
   See also Decidability questions  for these matters.

Cryptography: Finite automata can also been used in cryptography. These methods are studied in the Licentiate's Thesis of T. Meskanen.

  In a grammar system we have an initial symbol and a set of rewriting rules, which state how a word is derived from an other. A language defined by a grammar system is set of words over some (terminal) alphabet derived from the initial symbol by using the rewriting rules. Linear, context-free and context-sensitive grammars are mentioned as examples for grammar systems.  

  In the COWAT group the research on grammar systems has focus on the co-operating (or communicating) grammar systems. In the dissertation of V. Mihalache these systems were studied. Context-free and -sensitive languages have also been studied by L. Ilie.

  The third way of defining formal languages was with certain operations. For example, the regular languages can be defined with so called rational relations  and the L-systems (a word and a morphism) define sets of words. Also the behaviour of operations on different families of languages are often studied. 

  In COWAT group the research on the operational models has had two main topics:

L-systems and formal power series: J. Honkala has studied D0L systems and their generalizations. In particular, he has found a new solution to the D0L sequence equivalence problem, which avoids almost all difficulties of the earlier solutions. He has also obtained a polynomial bound for certain cases of  the D0L sequence equivalence problem. All earlier bound were huge. Following the approach used by S. Eilenberg in his monograph Automata, Languages and Machines and W. Kuich and A. Salomaa in Semirings, Automata and Languages he has studied the D0L and their generalizations in monoids and free algebras.

Slender languages: The study of the lengths of words in a language is an important oart of the language theory. In the number of the words of the of all lengths is bounded by some constant then the language is called slender. The slender context-free languages were studied in the dissertation of L. Ilie. L. Ilie, G. Rozenberg and A. Salomaa also proved that the slender context-free languages are strongly linear. 

References:

• S. Bogdanovic, M. Ciric, T. Petkovic, B. Imreh and M. Steinby: Traps, cores, extensions and subdirect decompositions of unary algebras. Fundamenta Informaticae 38 (1999), 51-60.
• M. Ciric, B. Imreh and M. Steinby: Subdirectly irreducible definite, reverse definite, and generalized definite automata. Publications of the faculty of electrical engineering, University of Belgrade, Series: Mathematics 10 (1999), 69-79.
• K. Culik II, J. Karhumäki, Finite automata computing real functions. SIAM J. Comp. 23, 789-814, 1994.
• K.Culik, J. Kari. Image Compression Using Weighted Finite Automata. Computers & Craphics 17, 305-313, 1993.
• V. Halava and T. Harju, Undecidability in Integer Weighted Finite Automata, Fund. Inf. 34 (1999) 189-200.
• V. Halava and T. Harju, Undecidability of the Equivalence of Finite Substitutions on Regular Language, RAIRO Theoret. Informatics Appl. 33 (1999) 117-124
• T. Harju and J. Karhumäki, The equivalence problem of multitape finite automata, Theoret. Comput. Sci. 78 (1991), 347 - 355.
• L. Ilie, An attempt to define a class of mildly context-sensitive languages, in: A. Adam, P. Domosi, eds., Proc. of the 8th ICAFL (Salgotarjan, 1996), Publ. Math. Debrecen 54 (1999) 865 - 876. 
• L. Ilie, On lengths of words in context-free languages,  Theoret. Comput. Sci. to appear. 
• Lucian Ilie, Grzegorz Rozenberg and Arto Salomaa,  Slender Context-Free Languages Are Strongly Linear, TUCS Tech report 248.
• B. Imreh and M. Steinby, Some remarks on directable automata. Acta Cybernetica 12 (1995), 23-35.
• B. Imreh and M. Steinby, Directable nondeterministic automata. Acta Cybernetica 14 (1999), 105-115.
• T. Meskanen, Äärellisiin automaatteihin perustuvista julkisen avaimen kryptosysteemeistä, Licentiate's Thesis, to appear.
• A. Salomaa, Formal Languages, Academic Press, 1973.