Formal power series: Theory and applications 1000-2M26FPS
1. Classes of power series in commuting variables (e.g.. rational, algebraic, D-finite, CDA, differentially algebraic, etc..). Closure properties and zeroness problem. Relation with corresponding classes of number sequences (e.g., LRS).
2. Chomsky-Schützenberger’s theorem (generating power series of unambiguous context-free grammars are algebraic)
3. Applications to labelled and unlabelled counting in combinatorics.
4. Christol’s theorem (algebraic power series = automatic sequences, in positive characteristics)
5. Solvability in power series of systems of algebraic and differentially algebraic equations
6. Classes of series in noncommuting variables (rational, algebraic, etc.) and their corresponding automata models (weighted automata, weighted context-free grammars, etc.)
7. Universality of unambiguous Parikh automata via D-finite power series
8. Zeroness of weighted multi-tape finite automata via skew fields
9. Chen-Fliess series and Fliess’ theorem in control theory
10. Series of finite Hankel rank. Lie rank.
Main fields of studies for MISMaP
Course coordinators
Type of course
Mode
Assessment criteria
The evaluation is based on homeworks during the duration of the course and a final oral exam.
Bibliography
Lecture slides and selected chapters from the following books:
• Berstel, Reutenauer: “Noncommutative series with applications”
• Gray: “Formal power series methods in nonlinear control theory”
• Salomaa, Soittola: “Automata-theoretic aspects of formal power series”
• Kuich, Salomaa: “Semirings, automata, languages”
• Sakarovitch: “Elements of automata theory”
• Kauers, Paule: “The concrete tetrahedron”
• Kauers: “D-finite functions”
• Petkovsek, Wilf, Zeilberger: “A=B”
• Wilf: “Generatingfunctionology”
• Stanley: “Enumerative combinatorics”
• Bergeron, Labelle, Leroux: “Combinatorial species and treelike structures”
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes: