Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On Rational Stochastic Languages

Denis F., Esposito Y.

Fundamenta Informaticae

2008

Vol. 86, nr 1-2

41-77

The goal of the present paper is to provide a study of rational stochastic languages over a semiring KÎ{ Q, R, Q+, R+}. A rational stochastic language is a probability distribution over a free monoid ?*, which is rational over K, that is, which can be generated by a multiplicity automaton with parameters in K. We study the relations between the classes of rational stochastic languages SKrat(σ). We define the notion of residual language of a stochastic language and we use it to investigate properties of several subclasses of rational stochastic languages. Then, we study the representation of rational stochastic languages by means of multiplicity automata. Lastly, we show some connections between properties of rational stochastic languages and results obtained in the field of probabilistic grammatical inference.

Residual Finite State Automata

Denis F., Lemay A., Terlutte A.

Fundamenta Informaticae

2002

Vol. 51, nr 4

339-368

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.