License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1317
URN: urn:nbn:de:0030-drops-13178
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1317/
Go to the corresponding LIPIcs Volume Portal

Mishna, Marni ; Zabrocki,Mike

Analytic aspects of the shuffle product

pdf-format:
22011.MishnaMarni.Paper.1317.pdf (0.2 MB)

Abstract

There exist very lucid explanations of the combinatorial origins of
rational and algebraic functions, in particular with respect to
regular and context free languages. In the search to understand
how to extend these natural correspondences, we find that the
shuffle product models many key aspects of D-finite generating
functions, a class which contains algebraic. We consider several
different takes on the shuffle product, shuffle closure, and
shuffle grammars, and give explicit generating function
consequences. In the process, we define a grammar class that
models D-finite generating functions.

BibTeX - Entry

@InProceedings{mishna_et_al:LIPIcs:2008:1317,
  author =	{Marni Mishna and Mike Zabrocki},
  title =	{{Analytic aspects of the shuffle product}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{561--572},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1317},
  URN =		{urn:nbn:de:0030-drops-13178},
  doi =		{10.4230/LIPIcs.STACS.2008.1317},
  annote =	{Keywords: Generating functions, formal languages, shuffle product}
}

Keywords: Generating functions, formal languages, shuffle product
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI