Document Open Access Logo

New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages

Author Florent Koechlin

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2022.41.pdf
  • Filesize: 0.79 MB
  • 22 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Grammars and context-free languages
Keywords
  • Inherent ambiguity
  • Infinite ambiguity
  • Ambiguity
  • Generating series
  • Context-free languages
  • Bounded languages

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.FSTTCS.2022.41

Author Details

Florent Koechlin
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

References

  1. Cyril Banderier and Michael Drmota. Formulae and asymptotics for coefficients of algebraic functions. Combinatorics, Probability and Computing, 24(1):1-53, 2015. URL: https://doi.org/10.1017/S0963548314000728.
  2. Jason P. Bell and Shaoshi Chen. Power series with coefficients from a finite set. J. Comb. Theory, Ser. A, 151:241-253, 2017. URL: https://doi.org/10.1016/j.jcta.2017.05.002.
  3. Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech. Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. Eur. J. Comb., 61:242-275, 2017. URL: https://doi.org/10.1016/j.ejc.2016.10.010.
  4. Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc., 138(9):3063-3078, 2010. With an Appendix by Mark van Hoeij. URL: https://doi.org/10.1090/S0002-9939-2010-10398-2.
  5. Mireille Bousquet-Mélou and Marko Petkovsek. Walks confined in a quadrant are not always D-finite. Theor. Comput. Sci., 307(2):257-276, 2003. URL: https://doi.org/10.1016/S0304-3975(03)00219-6.
  6. Noam Chomsky and Marcel-Paul Schützenberger. The Algebraic Theory of Context-Free Languages, volume 35 of Studies in Logic and the Foundations of Mathematics. Elsevier, 1963. URL: https://doi.org/10.1016/S0049-237X(08)72023-8.
  7. JP Crestin. Un langage non ambigu dont le carré est d'ambiguité non bornée. In ICALP, pages 377-390, 1972. Google Scholar
  8. Samuel Eilenberg and Marcel-Paul Schützenberger. Rational sets in commutative monoids. J. Algebra, 13(2):173-191, 1969. URL: https://doi.org/10.1016/0021-8693(69)90070-2.
  9. Georges Elencwajg. Necessary and sufficient condition for xⁿ - y^m to be irreducible in c[x,y]. Mathematics Stack Exchange. URL:https://math.stackexchange.com/q/489703 (version: 2013-09-10).
  10. Philippe Flajolet. Analytic models and ambiguity of context-free languages. Theor. Comput. Sci., 49(2):283-309, 1987. URL: https://doi.org/10.1016/0304-3975(87)90011-9.
  11. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Google Scholar
  12. Seymour Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, Inc., USA, 1966. Google Scholar
  13. Seymour Ginsburg and Edwin Spanier. Semigroups, Presburger formulas, and languages. Pac. J. Math., 16(2):285-296, 1966. Google Scholar
  14. Seymour Ginsburg and Joseph Ullian. Ambiguity in context free languages. J. ACM, 13(1):62-89, 1966. URL: https://doi.org/10.1145/321312.321318.
  15. Sheila Greibach. A note on undecidable properties of formal languages. Mathematical Systems Theory, 2(1):1-6, 1968. URL: https://doi.org/10.1007/BF01691341.
  16. Thomas N. Hibbard and Joseph Ullian. The independence of inherent ambiguity from complementedness among context-free languages. J. ACM, 13(4):588-593, October 1966. URL: https://doi.org/10.1145/321356.321366.
  17. Juha Honkala. On parikh slender languages and power series. Journal of Computer and System Sciences, 52(1):185-190, 1996. URL: https://doi.org/10.1006/jcss.1996.0014.
  18. Ryuichi Ito. Every semilinear set is a finite union of disjoint linear sets. J. Comput. Syst. Sci., 3(2):221-231, 1969. URL: https://doi.org/10.1016/S0022-0000(69)80014-0.
  19. Manuel Kauers and Alin Bostan. Automatic classification of restricted lattice walks. Discrete Mathematics & Theoretical Computer Science, 2009. Google Scholar
  20. Serge Lang. Algebra, volume 211. Springer Science & Business Media, 2012. Google Scholar
  21. Vladislav Makarov. Bounded languages described by gf(2)-grammars. In Nelma Moreira and Rogério Reis, editors, Developments in Language Theory - 25th International Conference, DLT 2021, Porto, Portugal, August 16-20, 2021, Proceedings, volume 12811 of Lecture Notes in Computer Science, pages 279-290. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-81508-0_23.
  22. Marni Mishna. Classifying lattice walks restricted to the quarter plane. Journal of Combinatorial Theory, Series A, 116(2):460-477, 2009. Google Scholar
  23. Marni Mishna and Andrew Rechnitzer. Two non-holonomic lattice walks in the quarter plane. Theoretical Computer Science, 410(38-40):3616-3630, 2009. Google Scholar
  24. Mohamed Naji. Grad der mehrdeutigkeit kontextfreier grammatiken und sprachen. Diplomarbeit, Johann Wolfgang Goethe-Universität, 1998. Google Scholar
  25. William Ogden. A helpful result for proving inherent ambiguity. Mathematical systems theory, 2(3):191-194, 1968. URL: https://doi.org/10.1007/BF01694004.
  26. Rohit J Parikh. Language generating devices. Quarterly Progress Report, 60:199-212, 1961. Google Scholar
  27. Rohit J. Parikh. On context-free languages. J. ACM, 13(4):570-581, 1966. URL: https://doi.org/10.1145/321356.321364.
  28. Holger Petersen. The ambiguity of primitive words. In Annual Symposium on Theoretical Aspects of Computer Science, pages 679-690. Springer, 1994. Google Scholar
  29. Arnold L Rosenberg. A note on ambiguity of context-free languages and presentations of semilinear sets. Journal of the ACM (JACM), 17(1):44-50, 1970. Google Scholar
  30. Eliahu Shamir. Some inherently ambiguous context-free languages. Inf. Cont., 18(4):355-363, 1971. URL: https://doi.org/10.1016/S0019-9958(71)90455-4.
  31. Klaus Wich. Exponential ambiguity of context-free grammars. In Developments In Language Theory: Foundations, Applications, and Perspectives, pages 125-138. World Scientific, 2000. Google Scholar
  32. Klaus Wich. Sublinear ambiguity. In Mogens Nielsen and Branislav Rovan, editors, Mathematical Foundations of Computer Science 2000, pages 690-698, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. Google Scholar
  33. Klaus Wich. Ambiguity functions of context-free grammars and languages. PhD thesis, Universität Stuttgart, 2005. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »