Automata with Auxiliary Weights
Abstract
We introduce a new generalization of weighted automata – automata with auxiliary weights. They allow to compute several quantities not directly computable over semirings by generalizing both semiring addition and semiring multiplication. Moreover, our automata retain key properties of ordinary weighted automata. We prove that automata over multi-hemirings of Droste and Kuich [7] can be modelled using our framework, and that automata with auxiliary weights can be used to describe several additional settings. Finally, we introduce rational expressions with auxiliary weights and prove that they are equivalent to our automata.
This work has been supported by the grants VEGA 1/0967/16 and UK/258/2015.
Communicated by Mitsunori Ogihara
Remember to check out the Most Cited Articles! |
---|
Check out these Handbooks in Computer Science |