RISC-Linz RISC-Linz Research Institute for Symbolic Computation  
about
|
people
|
publications
|
research
|
education
|
industry
|
conferences
|
media
|
projects
internal
  
search:
  
  • @mastersthesis{RISC2954,
    author = {Christoph Koutschan},
    title = {{Regular Languages and Their Generating Functions: The Inverse Problem}},
    language = {english},
    abstract = {The technique of determining a generating function for an unambiguous context-free language, is known as the Sch\"utzenberger methodology. For regular languages, Barcucci et al. proposed in their paper ``A Technology for Reverse-Engineering a Combinatorial Problem from a Rational Generating Function'' 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. },
    year = {2005},
    month = {August},
    translation = {0},
    school = {Friedrich-Alexander-Universität Erlangen-Nürnberg},
    keywords = {schützenberger regular language formal power series},
    length = {94},
    url = {http://www.risc.uni-linz.ac.at/people/ckoutsch/research/en_da.html}
    }