Diploma Thesis
Regular Languages and Their Generating Functions: The Inverse Problem
- Thesis
- Maple Package: RLangGFun.mla (documentation is part of the thesis)
- Maple Worksheet with Examples: RLangGFunExamples.mw
- Slides from the talk (given on 14-12-2005 and 18-01-2006 in the RISC Combinatorics Seminar)
Abstract
The technique of determining a generating function for an unambiguous context-free language, is known as the Schützenberger methodology. For regular languages, Barcucci et al. (1) proposed a technology for inverting this methodology, which allows to give a combinatorial interpretation (by means of a regular expression) of certain positive integer sequences that are defined by a linear recurrence.In this thesis, we provide an implementation of this inverse methodology in Maple. Therefore, a detailed introduction to the underlying theory, i.e., the theory of formal power series and especially the question of deciding N-rationality, is given. Further, various aspects and problems concerning the implementation are discussed, and some examples from combinatorics illustrate its applicability.
Literature
| (1) |
E. Barcucci, A. Del Lungo, A. Frosini, S. Rinaldi:
A technology for reverse-engineering a combinatorial problem from a rational generating function, Advances in Applied Mathematics, 26, (2001) 129-153. |
Christoph Koutschan