Rational and Recognisable Power Series
Rational and Recognisable Power Series
复制标题
有理且可识别的幂级数
DOI：
10.1007/978-3-642-01492-5_4
复制
发表时间：
2009
影响因子：
1.3
通讯作者：
J. Sakarovitch
中科院分区：
文献类型：
--
作者：
J. Sakarovitch
This chapter presents the theory of weighted automata over graded monoids and with weights taken in arbitrary semirings. The first benefit of broadening the scope beyond free monoids is that it makes clearer the distinction between the rational and the recognisable series. As the topological machinery is set anyway, the star of series is defined in a slightly more general setting than cycle-free series. The main subjects covered in the chapter are then: the notion of covering of automata (also called bisimulation by some authors) and its relationship with the conjugacy of automata; the closure of recognisable series by Hadamard and shuffle products; the derivation of weighted rational expressions over a free monoid; the reduction theory of series over a free monoid and with weights in a (skew) field, that leads to a procedure for the decidability of equivalence (with a cubic complexity); and the basics for a theory of weighted rational relations. As a result, this chapter, among other things, lays the bases for the proof of the decidability of the equivalence of deterministic k-tape transducers which is one of the most striking examples of the application of algebra to ‘machine theory’.
