Technical Report TR-1997-05

BibliographyDiekert, Volker; Kobayashi, Yuji: Some Identities Related to Automata, Determinants, and Möbius Functions.
University of Stuttgart, Faculty of Computer Science, Technical Report No. 1997/05.
23 pages, english.
CR-SchemaF.4.3 (Formal Languages)
G.2.1 (Combinatorics)
Abstract

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.

Full text and
other links
HTML (generated from PostScript)
Department(s)University of Stuttgart, Institute of Computer Science, Theoretical Computer Science
Entry dateJune 18, 1997
   Publ. Computer Science