The robust theory of regular languages is based on three important pillars: computation
(automata), logic, and algebra. In this paper, we survey old and recent results on extensions …

Finite automata with weights in the max-plus semiring are considered. The main result is: it
is decidable whether a series that is recognized by a finitely ambiguous max-plus automaton …

Regular word transductions extend the robust notion of regular languages from a qualitative
to a quantitative reasoning. They were already considered in early papers of formal …

In the paper, we generalize an algorithm and some related results by Mohri [25] for
determinization of weighted finite automata (WFA) over the tropical semiring. We present the …

Pioneered by Büchi, Elgot and Trakhtenbrot, connections between automata and logics that
define languages of words and trees are now well-established. During the last decade …

This paper is a survey where we try to organise the known answers to the question whether
a given finite automaton with multiplicity in a semiring K is equivalent to a sequential, or …

Transductions are binary relations of finite words. For rational transductions, ie,
transductions defined by finite transducers, the inclusion, equivalence and sequential …

A weighted automaton is functional if any two accepting runs on the same finite word have
the same value. In this paper, we investigate functional weighted automata for four different …

Any two-way finite state automaton is equivalent to some one-way finite state automaton.
This well-known result, shown by Rabin and Scott and independently by Shepherdson …

Finite-state methods are the most efficient mechanisms for analysing textual and symbolic
data, providing elegant solutions for an immense number of practical problems in …