Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Rationality of the Mobius function of a composition poset
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).ORCID-id: 0000-0002-7497-2764
2006 (Engelska)Ingår i: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 359, nr 3-Jan, s. 282-298Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider the zeta and Mobius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-Melou, and Dulucq. The Mobius function of this poset was determined by Sagan and Vatter. We prove rationality of various formal power series in noncommuting variables whose coefficients are evaluations of the zeta function, zeta, and the Mobius function, mu. The proofs are either directly from the definitions or by constructing finite-state automata. We also obtain explicit expressions for generating functions obtained by specializing the variables to commutative ones. We reprove Sagan and Vatter's formula for it using this machinery. These results are closely related to those of Bjorner and Reutenauer about subword order, and we discuss a common generalization.

Ort, förlag, år, upplaga, sidor
2006. Vol. 359, nr 3-Jan, s. 282-298
Nyckelord [en]
automaton, composition, generating function, hypergeometric series, monoid, rationality, subword order, identities, permutations, algorithm
Identifikatorer
URN: urn:nbn:se:kth:diva-15927DOI: 10.1016/j.tcs.2006.03.025ISI: 000239885600020Scopus ID: 2-s2.0-33746508424OAI: oai:DiVA.org:kth-15927DiVA, id: diva2:333969
Anmärkning
QC 20100525Tillgänglig från: 2010-08-05 Skapad: 2010-08-05 Senast uppdaterad: 2017-12-12Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Björner, Anders

Sök vidare i DiVA

Av författaren/redaktören
Björner, Anders
Av organisationen
Matematik (Avd.)
I samma tidskrift
Theoretical Computer Science

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 48 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf