Wyniki wyszukiwania - BazTech

1

Once More on the Edge-Minimization of Nondeterministic Finite Automata and the Connected Problems

Melnikov B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 3

267-283

EN

We consider in this paper the problem of edge-minimization for nondeterministic finite automata and some connected questions. We shall formulate a new algorithm solving this problem; this algorithm is a simplification of two ones published before. The connected problems include at first algorithms of combining states. We formulate some new sufficient conditions for the possibility of such combining.

2

Extended Nondeterministic Finite Automata

Melnikov B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 3

255-265

EN

We consider a new expansion of nondeterministic finite automata. The goals of this consideration are: to apply some algorithms of such expansion for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; using such automata, we often can simplify some proofs for algorithms of simplification of usual nondeterministic automata.

3

Results on Transforming NFA into DFCA

Câmpeanu C., Kari L., Păun A.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

53-63

EN

In this paper we consider the transformation from (minimal) non-deterministic finite automata (NFAs) to deterministic finite cover automata (DFCAs). We want to compare the two equivalent accepting devices with respect to their number of states; this becomes in fact a comparison between the expression power of the nondeterministic device and the expression power of the deterministic with loops device. We prove a lower bound for the maximum state complexity of deterministic finite cover automata obtained from non-deterministic finite automata of a given state complexity n, considering the case of a binary alphabet. We show, for such binary alphabets, that the difference between maximum blow-up state complexity of DFA and DFCA can be as small as [..]compared to the number of states of the minimal DFA. Moreover, we show the structure of automata for worst case exponential blow-up complexity from NFA to DFCA. We conjecture that the lower bound given in the paper is also the upper bound. Several results clarifying some of the structure of the automata in the worst case are given (we strongly believe they will be pivotal in the upper bound proof).

4

Theoretical study and implementation of the canonical automaton

Champarnaud J-M., Coulon F.

Fundamenta Informaticae

|

2003

|

Vol. 55, nr 1

23-38

EN

We can represent the canonical automaton of a language as the smallest automaton which contains any other automaton recognizing this language, providing equivalent states are merged. Indeed, the canonical automaton appears to be a good representative element in the equivalence class of non-deterministic automata recognizing a given language. Our aim is to provide a detailed description of the canonical automaton based on the notions of syntactical rectangle and characteristic event. In our approach, a state of the canonical automaton of a language L is associated with a rectangle (L,R) Í S*×S*, which is maximal w.r.t. the property L.R Í L. We explicit the link with other characterizations, like considering a state as a residual intersection which was given by Arnold et al., and the fundamental automaton defined by Matz and Potthoff. In particular, we pretend that the construction of the canonical automaton has the same time complexity as the construction of the fundamental automaton. Our last section briefly discusses the problem of searching minimal NFAs using the canonical automaton.

5

Residual Finite State Automata

Denis F., Lemay A., Terlutte A.

Fundamenta Informaticae

|

2002

|

Vol. 51, nr 4

339-368

EN

We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes ; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic construction of the canonical RFSA similar to the subset construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our constructions.