Displaying similar documents to “Algebraic elimination of ϵ -transitions.”

Series which are both max-plus and min-plus rational are unambiguous

Sylvain Lombardy, Jean Mairesse (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Consider partial maps Σ * → ℝ with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one...

Binary operations on automatic functions

Juhani Karhumäki, Jarkko Kari, Joachim Kupke (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Real functions on the domain [ 0 , 1 ) n – often used to describe digital images – allow for different well-known types of binary operations. In this note, we recapitulate how weighted finite automata can be used in order to represent those functions and how certain binary operations are reflected in the theory of these automata. Different types of products of automata are employed, including the seldomly-used full cartesian product. We show, however, the infeasibility of functional composition;...

How expressions can code for automata

Sylvain Lombardy, Jacques Sakarovitch (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper we investigate how it is possible to recover an automaton from a rational expression that has been computed from that automaton. The notion of derived term of an expression, introduced by Antimirov, appears to be instrumental in this problem. The second important ingredient is the co-minimization of an automaton, a dual and generalized Moore algorithm on non-deterministic automata. We show here that if an automaton is then sufficiently “decorated”, the combination of these...

Efficient simulation of synchronous systems by multi-speed systems

Tomasz Jurdziński, Mirosław Kutyłowski, Jan Zatopiański (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We consider systems consisting of finite automata communicating by exchanging messages and working on the same read-only data. We investigate the situation in which the automata work with constant but different speeds. We assume furthermore that the automata are not aware of the speeds and they cannot measure them directly. Nevertheless, the automata have to compute a correct output. We call this model multi-speed systems of finite automata. Complexity measure that we consider here is...

Corrigendum to our paper: How Expressions Can Code for Automata

Sylvain Lombardy, Jacques Sakarovitch (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms...

Distance desert automata and the star height problem

Daniel Kirsten (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 2 2 𝒪 ( n ) space whether the language accepted by an n -state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...