4 Search Results for "Flajolet, Philippe"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.41
New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages

Authors: Florent Koechlin

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
This article extends the work of Flajolet [Philippe Flajolet, 1987] on the relation between generating series and inherent ambiguity. We first propose an analytic criterion to prove the infinite inherent ambiguity of some context-free languages, and apply it to give a purely combinatorial proof of the infinite ambiguity of Shamir’s language. Then we show how Ginsburg and Ullian’s criterion on unambiguous bounded languages translates into a useful criterion on generating series, which generalises and simplifies the proof of the recent criterion of Makarov [Vladislav Makarov, 2021]. We then propose a new criterion based on generating series to prove the inherent ambiguity of languages with interlacing patterns, like {a^nb^ma^pb^q | n≠p or m≠q, with n,m,p,q ∈ ℕ^*}. We illustrate the applicability of these two criteria on many examples.
Cite as

Florent Koechlin. New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{koechlin:LIPIcs.FSTTCS.2022.41,
  author =	{Koechlin, Florent},
  title =	{{New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.41},
  URN =		{urn:nbn:de:0030-drops-174331},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.41},
  annote =	{Keywords: Inherent ambiguity, Infinite ambiguity, Ambiguity, Generating series, Context-free languages, Bounded languages}
}
Document
DOI: 10.4230/DagSemRep.185
`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9728)

Authors: Philippe Flajolet, Rainer Kemp, Hosam M. Mahmoud, and Helmut Prodinger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, Hosam M. Mahmoud, and Helmut Prodinger. `Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9728). Dagstuhl Seminar Report 185, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.185,
  author =	{Flajolet, Philippe and Kemp, Rainer and Mahmoud, Hosam M. and Prodinger, Helmut},
  title =	{{`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9728)}},
  pages =	{1--23},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{185},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.185},
  URN =		{urn:nbn:de:0030-drops-150720},
  doi =		{10.4230/DagSemRep.185},
}
Document
DOI: 10.4230/DagSemRep.119
`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527)

Authors: Philippe Flajolet, Rainer Kemp, Helmut Prodinger, and Robert Sedgewick

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, Helmut Prodinger, and Robert Sedgewick. `Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527). Dagstuhl Seminar Report 119, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.119,
  author =	{Flajolet, Philippe and Kemp, Rainer and Prodinger, Helmut and Sedgewick, Robert},
  title =	{{`Average-Case'-Analysis of Algorithms (Dagstuhl Seminar 9527)}},
  pages =	{1--20},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{119},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.119},
  URN =		{urn:nbn:de:0030-drops-150079},
  doi =		{10.4230/DagSemRep.119},
}
Document
DOI: 10.4230/DagSemRep.68
"Average-Case"-Analysis of Algorithms (Dagstuhl Seminar 9328)

Authors: Philippe Flajolet, Rainer Kemp, and Helmut Prodinger

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Philippe Flajolet, Rainer Kemp, and Helmut Prodinger. "Average-Case"-Analysis of Algorithms (Dagstuhl Seminar 9328). Dagstuhl Seminar Report 68, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)

Copy BibTex To Clipboard

@TechReport{flajolet_et_al:DagSemRep.68,
  author =	{Flajolet, Philippe and Kemp, Rainer and Prodinger, Helmut},
  title =	{{"Average-Case"-Analysis of Algorithms (Dagstuhl Seminar 9328)}},
  pages =	{1--32},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{68},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.68},
  URN =		{urn:nbn:de:0030-drops-149562},
  doi =		{10.4230/DagSemRep.68},
}
  • Refine by Author
  • 3 Flajolet, Philippe
  • 3 Kemp, Rainer
  • 3 Prodinger, Helmut
  • 1 Koechlin, Florent
  • 1 Mahmoud, Hosam M.
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Grammars and context-free languages

  • Refine by Keyword
  • 1 Ambiguity
  • 1 Bounded languages
  • 1 Context-free languages
  • 1 Generating series
  • 1 Infinite ambiguity
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 1993
  • 1 1996
  • 1 1998
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact