\input zb-basic
\input zb-ioport
\iteman{io-port 06084446}
\itemau{Gastin, Paul; Monmege, Benjamin}
\itemti{Adding pebbles to weighted automata.}
\itemso{Moreira, Nelma (ed.) et al., Implementation and application of automata. 17th international conference, CIAA 2012, Porto, Portugal, July 17--20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31605-0/pbk). Lecture Notes in Computer Science 7381, 28-51 (2012).}
\itemab
Summary: We extend weighted automata and weighted rational expressions with 2-way moves and (reusable) pebbles. We show with examples from natural language modeling and quantitative model-checking that weighted expressions and automata with pebbles are more expressive and allow much more natural and intuitive specifications than classical ones. We extend Kleene-Sch\"utzenberger theorem showing that weighted expressions and automata with pebbles have the same expressive power. We focus on an efficient translation from expressions to automata. We also prove that the evaluation problem for weighted automata can be done very efficiently if the number of (reusable) pebbles is low.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-31606-7\_4}
\end