Regular approximations to shuffle products of context-free languages, and convergence of their generating functions

Robert S. Maier; René Schott

doi:10.1007/3-540-57163-9_30

Regular approximations to shuffle products of context-free languages, and convergence of their generating functions

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We approximate certain languages, obtained as shuffle products of Dyck languages, by regular languages. These regular approximants are obtained by restricting the automaton accepting the original language to a finite maximum amount of storage, N. We study the dominant singularities of the multivariate generating functions of the approximants. By using formal asymptotic methods drawn from applied probability to work out the N → ∞ asymptotics of these singularities, we quantify the rate at which the approximants approach the original languages.

Original language	English (US)
Title of host publication	Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings
Editors	Zoltan Esik
Publisher	Springer-Verlag
Pages	352-362
Number of pages	11
ISBN (Print)	9783540571636
DOIs	https://doi.org/10.1007/3-540-57163-9_30
State	Published - 1993
Event	9th International Conference on Fundamentals of Computation Theory, FCT 1993 - Szeged, Hungary Duration: Aug 23 1993 → Aug 27 1993

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	710 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	9th International Conference on Fundamentals of Computation Theory, FCT 1993
Country/Territory	Hungary
City	Szeged
Period	8/23/93 → 8/27/93

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-57163-9_30

Cite this

Maier, R. S., & Schott, R. (1993). Regular approximations to shuffle products of context-free languages, and convergence of their generating functions. In Z. Esik (Ed.), Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings (pp. 352-362). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 710 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-57163-9_30

Regular approximations to shuffle products of context-free languages, and convergence of their generating functions. / Maier, Robert S.; Schott, René.
Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings. ed. / Zoltan Esik. Springer-Verlag, 1993. p. 352-362 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 710 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Maier, RS & Schott, R 1993, Regular approximations to shuffle products of context-free languages, and convergence of their generating functions. in Z Esik (ed.), Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 710 LNCS, Springer-Verlag, pp. 352-362, 9th International Conference on Fundamentals of Computation Theory, FCT 1993, Szeged, Hungary, 8/23/93. https://doi.org/10.1007/3-540-57163-9_30

Maier RS, Schott R. Regular approximations to shuffle products of context-free languages, and convergence of their generating functions. In Esik Z, editor, Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings. Springer-Verlag. 1993. p. 352-362. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-57163-9_30

Maier, Robert S. ; Schott, René. / Regular approximations to shuffle products of context-free languages, and convergence of their generating functions. Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings. editor / Zoltan Esik. Springer-Verlag, 1993. pp. 352-362 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3f505a2836f0448595a3a7890eda5ebb,

title = "Regular approximations to shuffle products of context-free languages, and convergence of their generating functions",

abstract = "We approximate certain languages, obtained as shuffle products of Dyck languages, by regular languages. These regular approximants are obtained by restricting the automaton accepting the original language to a finite maximum amount of storage, N. We study the dominant singularities of the multivariate generating functions of the approximants. By using formal asymptotic methods drawn from applied probability to work out the N → ∞ asymptotics of these singularities, we quantify the rate at which the approximants approach the original languages.",

author = "Maier, {Robert S.} and Ren{\'e} Schott",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 9th International Conference on Fundamentals of Computation Theory, FCT 1993 ; Conference date: 23-08-1993 Through 27-08-1993",

year = "1993",

doi = "10.1007/3-540-57163-9_30",

language = "English (US)",

isbn = "9783540571636",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "352--362",

editor = "Zoltan Esik",

booktitle = "Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings",

}

TY - GEN

T1 - Regular approximations to shuffle products of context-free languages, and convergence of their generating functions

AU - Maier, Robert S.

AU - Schott, René

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - We approximate certain languages, obtained as shuffle products of Dyck languages, by regular languages. These regular approximants are obtained by restricting the automaton accepting the original language to a finite maximum amount of storage, N. We study the dominant singularities of the multivariate generating functions of the approximants. By using formal asymptotic methods drawn from applied probability to work out the N → ∞ asymptotics of these singularities, we quantify the rate at which the approximants approach the original languages.

AB - We approximate certain languages, obtained as shuffle products of Dyck languages, by regular languages. These regular approximants are obtained by restricting the automaton accepting the original language to a finite maximum amount of storage, N. We study the dominant singularities of the multivariate generating functions of the approximants. By using formal asymptotic methods drawn from applied probability to work out the N → ∞ asymptotics of these singularities, we quantify the rate at which the approximants approach the original languages.

UR - http://www.scopus.com/inward/record.url?scp=85029471295&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029471295&partnerID=8YFLogxK

U2 - 10.1007/3-540-57163-9_30

DO - 10.1007/3-540-57163-9_30

M3 - Conference contribution

AN - SCOPUS:85029471295

SN - 9783540571636

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 352

EP - 362

BT - Fundamentals of Computation Theory - 9th International Conference, FCT 1993, Proceedings

A2 - Esik, Zoltan

PB - Springer-Verlag

T2 - 9th International Conference on Fundamentals of Computation Theory, FCT 1993

Y2 - 23 August 1993 through 27 August 1993

ER -

Regular approximations to shuffle products of context-free languages, and convergence of their generating functions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this