Eliminating ε-Transitions in Weighted Automata

Title: Eliminating ε-Transitions in Weighted Automata

Abstract: This research focuses on the elimination of ε-transitions in weighted automata, a type of automaton used to model various purposes such as image compression, speech recognition, and formal linguistic. The study presents an algebraic method to compute the star of transition matrices for ε, which is used to eliminate ε-transitions and preserve the automaton's behavior. The running time complexity of the method is discussed, and it is shown to be efficient for well-known semirings like boolean and tropical. The paper concludes with a discussion on the equivalence between k-automata and k-ε-automata, and the validity of the method.

Main Research Question: Can we develop an efficient method to eliminate ε-transitions in weighted automata while preserving the automaton's behavior?

Methodology: The study uses the concept of semirings, which are sets with two laws and their neutrals. The paper introduces the notions of k-automaton and k-ε-automaton, and presents the main results: a method to eliminate ε-transitions and an algorithm to suppress them while preserving the behavior. The method's running time complexity is discussed, and it is shown to be efficient for well-known semirings.

Results: The research presents an algebraic method to compute the star of transition matrices for ε, which is used to eliminate ε-transitions and preserve the automaton's behavior. The method's running time complexity is discussed, and it is shown to be efficient for well-known semirings like boolean and tropical.

Implications: The results of this research have implications in various fields such as image compression, speech recognition, formal linguistic, and probabilistic modeling. The ability to eliminate ε-transitions in weighted automata can lead to more efficient and accurate models, and the developed method can be applied to a wide range of problems.

Keywords: Weighted Automata, ε-Transitions, Behavior, Star of Matrices, Semirings, Algebraic Method, Running Time Complexity

Link to Article: https://arxiv.org/abs/0401012v2 Authors: arXiv ID: 0401012v2