Automata, Languages, and Machines

2-automaton algebraic assume automata behavior bijective called card Q coaccessible coefficients complete semiring composition computed Consequently consider COROLLARY defined denote deterministic deterministic automaton disjoint edges equation equivalence relation EXAMPLE EXERCISE exists f is rational finite alphabet formal power series formula free monoid function f given go-module gs-machine gsp-function implies infinite integer Jºy K-module K-morphism k-recognizable K-subset Kleene's Theorem label length-preserving Let f Let Q locally finite matrix minimal automaton module morphism f multiplication non-singular notation obtain output partial function polynomial prefix Proof PROPOSITION 3.1 prove q e Q rational relation rational subset Ratk recognizable subset relation f replaced satisfying semigroup semiring sequence sequential machine Show submonoid successful path surjective surjective function syntactic monoid terminal transducer unambiguous subset unitary monoid