The relationships among several forms of weighted finite automata over strong bimonoids
| Autor: | Yongming Li, Shengling Geng, Ping Li |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Information Systems and Management Powerset construction 05 social sciences 050301 education Büchi automaton 02 engineering and technology Computer Science Applications Theoretical Computer Science Combinatorics Deterministic finite automaton DFA minimization Artificial Intelligence Control and Systems Engineering Deterministic automaton Probabilistic automaton 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Two-way deterministic finite automaton Nondeterministic finite automaton 0503 education Software Mathematics |
| Zdroj: | Information Sciences. 402:149-164 |
| ISSN: | 0020-0255 |
| DOI: | 10.1016/j.ins.2017.03.021 |
| Popis: | Given a strong bimonoid P, we introduce three different behaviors of a weighted finite automaton over P (called a P − valued finite automaton), named the initial object semantics, final object semantics and run semantics. We define four forms for a P − valued nondeterministic finite automaton ( P − NFA) and three forms for a P − valued deterministic finite automaton ( P − DFA). Under the above-mentioned semantics, the equivalence and differences among the four forms of P − NFAs are discussed and the equivalence among the three forms of P − DFAs are given. Moreover, we show that some equivalence depends on right distributivity or left distributivity, or even requires P to degenerate into a semiring. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect