DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1317

Analytic aspects of the shuffle product

Authors: Marni Mishna and Mike Zabrocki

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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.

Cite as

Marni Mishna and Mike Zabrocki. Analytic aspects of the shuffle product. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 561-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{mishna_et_al:LIPIcs.STACS.2008.1317,
  author =	{Mishna, Marni and Zabrocki, Mike},
  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 =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1317},
  URN =		{urn:nbn:de:0030-drops-13178},
  doi =		{10.4230/LIPIcs.STACS.2008.1317},
  annote =	{Keywords: Generating functions, formal languages, shuffle product}
}

Search Results

Documents authored by Zabrocki, Mike

Analytic aspects of the shuffle product

Abstract

Cite as

Thanks for your feedback!

Could not send message