The number of automata, boundedly determined functions and hereditary properties of automata
A. D. Koršunov (1976)
Kybernetika
Similarity:
A. D. Koršunov (1976)
Kybernetika
Similarity:
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.
Andrej Bebják, Ivana Štefáneková (1988)
Kybernetika
Similarity:
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.
Andrew Badr, Viliam Geffert, Ian Shipman (2009)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications,...