Displaying similar documents to “Commutative images of rational languages and the abelian kernel of a monoid”

Commutative images of rational languages and the Abelian kernel of a monoid

Manuel Delgado (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Natural algorithms to compute rational expressions for recognizable languages, even those which work well in practice, may produce very long expressions. So, aiming towards the computation of the commutative image of a recognizable language, one should avoid passing through an expression produced this way. We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative image of a recognizable language. We also give a second modification...

A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata

Daniel Kirsten (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.