On the complexity of events recognizable in real time
Miloslav Nekvinda (1973)
Kybernetika
Similarity:
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying similar documents to “Hyper-minimizing minimized deterministic finite state automata”
On the complexity of events recognizable in real time
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.
Translation from classical two-way automata to pebble two-way automata
Viliam Geffert, L'ubomíra Ištoňová (2010)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles....
On the k-reversibility of finite automata.
Falucskai, János (2008)
Annales Mathematicae et Informaticae
Similarity:
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.
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...