Title: STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA
Abstract: It is known that the neighborhood of a regular language with respect to an additive distance is regular. We introduce an additive weighted finite automaton model that provides a conceptually simple way to reprove this result. We consider the state complexity of converting additive weighted finite automata to deterministic finite automata. As our main result we establish a tight upper bound for the state complexity of the conversion.
Publication Year: 2007
Publication Date: 2007-10-29
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 13
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot