A unified framework for disambiguating finite transductions (Q1115635)

The paper studies the finite state transductions; they are a simple and effective tool for the efficient analysis and transformation of large bodies of text. For their study the concept of a *-semiring is defined. It is a semiring with a unary operation * added which satisfies \[ a^*=(a\odot (a^*))\oplus 1=((a^*)\odot a)\oplus 1 \] for each element a, where \(\oplus\), \(\odot\) are the addition and the multiplication in the semiring, respectively, and 1 is the unit element of the semiring. By means of *-semirings the *-semiring automata are introduced. These concepts are then applied in the mentioned topic.