Displaying similar documents to “Series which are both max-plus and min-plus rational are unambiguous”

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...

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...

How expressions can code for automata

Sylvain Lombardy, Jacques Sakarovitch (2010)

RAIRO - Theoretical Informatics and 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...

Returning and non-returning parallel communicating finite automata are equivalent

Ashish Choudhary, Kamala Krithivasan, Victor Mitrana (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

A parallel communicating automata system consists of several automata working independently in parallel and communicating with each other by request with the aim of recognizing a word. Rather surprisingly, returning parallel communicating finite automata systems are equivalent to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata. Some open problems are finally formulated.

The factor automaton

Milan Šimánek (2002)

Kybernetika

Similarity:

This paper concerns searching substrings in a string using the factor automaton. The factor automaton is a deterministic finite automaton constructed to accept every substring of the given string. Nondeterministic factor automaton is used to achieve new operations on factor automata for searching in non-constant texts.