Regular Languages and Their Generating Functions: The Inverse Problem

(Master Thesis — Diplomarbeit)

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.

Kurzzusammenfassung

Mit dem Verfahren von Schützenberger kann zu einer eindeutigen, kontextfreien Sprache eine erzeugende Funktion bestimmt werden. Die Umkehrung dieses Verfahrens im Fall regulärer Sprachen wurde von Barcucci et al. (1) vorgestellt; damit ist es möglich, zu einer durch eine lineare Rekursion gegebenen Reihe positiver ganzer Zahlen eine kombinatorische Interpretation (in Form eines regulären Ausdrucks) anzugeben.
Im Rahmen der vorliegenden Diplomarbeit wurde dieses inverse Verfahren in Maple implementiert. Dazu wird zunächst die zu Grunde liegende Theorie, d.h. die Theorie der formalen Potenzreihen und insbesondere die Frage nach der N-Rationalität, dargestellt. Anschließend werden verschiedene Aspekte der Implementierung und dabei auftretende Probleme diskutiert. Einige Beispiele aus der Kombinatorik zeigen Anwendungsmöglichkeiten des vorgestellten Maple-Programms auf.

Material

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, 129–153 (2001).