1. The relationships among several forms of weighted finite automata over strong bimonoids
- Author
-
Yongming Li, Shengling Geng, and Ping Li
- Subjects
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 - Abstract
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.
- Published
- 2017