[Prev][Next][Index]

dar seminar - Gene Stark: Symbolic Rational Function Calculations ...

		 Design and Analysis Research Seminar
                         Wed., Oct. 17, 2001
                     2-3pm, CS Seminar Room 1306

	       Symbolic Rational Function Calculations
		      via Linear Representations

		           Eugene Stark

The class of rational functions is the least class containing the
identity function, all constant functions, and which is closed under
"rational" operations of addition, subtraction, multiplication, and
division.  The observation that every rational function can be
expressed as a quotient of polynomials is the basis for the familiar
high-school algorithms for performing symbolic calculations with these
functions.  Rational functions bear a close relationship to finite
automata and formal power series.  These topics were well-studied in
the 1960's, but don't seem as popular or familiar today.  One result
of this study is the fact that every rational function that is
continuous at 0 can be expressed as a formal power series whose
coefficients are generated by a kind of vector automaton called a
"linear representation".

In this talk I will introduce linear representations and consider the
problem of how to calculate with rational functions expressed as
linear representations, rather than as quotients of polynomials.  I
became interested in this problem because of its potential for
speeding up rational function calculations that are part of some
algorithms I have developed for doing performance analysis on
probabilistic automata.