Rational and Recognisable Power Series

摘要: This chapter presents the theory of weighted automata over graded monoids and with weights taken in arbitrary semirings. The first benefit broadening scope beyond free is that it makes clearer distinction between rational recognisable series. As topological machinery set anyway, star series defined a slightly more general setting than cycle-free main subjects covered are then: notion covering (also called bisimulation by some authors) its relationship conjugacy automata; closure Hadamard shuffle products; derivation expressions monoid; reduction monoid (skew) field, leads to procedure for decidability equivalence (with cubic complexity); basics relations. result, this chapter, among other things, lays bases proof deterministic k-tape transducers which one most striking examples application algebra ‘machine theory’.