Technischer Bericht TR-1997-05

Bibliograph.
Daten
Diekert, Volker; Kobayashi, Yuji: Some Identities Related to Automata, Determinants, and Möbius Functions.
Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1997/05.
23 Seiten, englisch.
CR-Klassif.F.4.3 (Formal Languages)
G.2.1 (Combinatorics)
Kurzfassung

We define the Möbius function for a language S being closed under factors as the formal inverse of the characteristic series over the set S. We derive identities in commuting and non-commutating variables characterizing this function as a quotient of polynomials which can be expressed as certain determinants. These determinants in turn are obtained by some matrix related to the minimal automaton recognizing S. Our contribution extends some recent work of Choffrut and Goldwurm.

Volltext und
andere Links
HTML (aus PostScript generiert)
Abteilung(en)Universität Stuttgart, Institut für Informatik, Theoretische Informatik
Eingabedatum18. Juni 1997
   Publ. Informatik