Formal series, finiteness properties and decision problems
A. Paz · Annales Academiae Scientiarum Fennicae Series A I Mathematica · 1971
Some finiteness properties of formal series over several non-commutative variables are invostigated.Somo unsolvability results for those properties are proved.A simple example of a context sensitive languago over å, single letter alphabet which is not probabilistic is exhibited. Introduetion IAn interesting connection between some classical results in analysis dating back to Cauchy and Jacobi and some quite new theories such as System Theory, Automata Theory and, Computability has been established in the past few years.The classical results &re concerned rvith a special type on infinite matrices, called Hankel matrices, connected with the Routh- Hurwitz problem (see Cantmacher (1959)), r,r'ith formal series expansion of rational and alg'braic funct'ions (see Hurwitz (1889)) and.approximations of formal series by an expansion of a rational function -Pade' approxi- mat'ion (see Frobenius (1881)).The formal approach has been rejuvenated recently by Schutzenberger (1961) followed by several others (e.g.Shamir (1967)), Nivat (1968), X'lies (1969) who introduced, noncommutative vari- ables and studied formal series in connection with the theory of formal languages and automata.Kalman and Ho and others (see Kalman Arbib and X'alb (1969)) have applied a getreralized form of Hankel matrices to System Theory and solved the realizatiotr problem of input-output linear maps.I{asu arrd Honda,emergirg from probabilistic autornata theorS', have established an interesting finiteness propertl' of a formal series gene a,- ted by a probablistic automaton, a ploperty rvhich rvas used by them to prove some undecidebilit5r theorems (see Nasu and.Honda (1969)).X'inally Carlyle and.Paz (1970) have found a connection between a generalized form of Hankel matrices and formal series u'hich are generated by pseudoprobabilistic a,utomata.The first three sections of this paper are concerned with four finiterress properties of formal series over several noncommutative variables.