Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics.
For example, solving the intersection non-emptiness problem for a context-free language and a regular language.
2
-
1$\begingroup$ For me the best example is the wonderful paper by Flajolet : Flajolet, P. (1987). Analytic models and ambiguity of context-free languages. Theoretical Computer Science, 49(2-3), 283-309. Most of Flajolet's work is about the connection between (complex) analysis , formal languages and combinatorics. You can find much more examples in his book with Sedgewick. $\endgroup$– LamineJan 14, 2019 at 15:21
-
1$\begingroup$ @Lamine please consider converting your comment into an answer. $\endgroup$– Hermann GruberJan 20, 2019 at 21:07
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Lamine commented on the connection to the Chomsky-Schützenberger enumeration theorem. Recently, a few research problems in formal language theory were solved using continuous mathematics via this connection. For example:
Hermann Gruber, Jonathan Lee, and Jeffrey Shallit. Enumerating Regular Expressions and their Languages. available online at arxiv.org as arXiv:1204.4982, 2012
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: A Hitchhiker's Guide to descriptional complexity through analytic combinatorics. Theor. Comput. Sci. 528: 85-100 (2014)
Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: Average Size of Automata Constructions from Regular Expressions. Bulletin of the EATCS 116 (2015)
Rafaela Bastos, Sabine Broda, António Machiavelo, Nelma Moreira, Rogério Reis: On the Average Complexity of Partial Derivative Automata for Semi-extended Expressions. Journal of Automata, Languages and Combinatorics 22(1-3): 5-28 (2017)
The first two of the above references also give a survey of the mathematical and/or historical background.
answered Jan 20, 2019 at 21:06
$\begingroup$
$\endgroup$
One of the first connections is via generating functions. The Chomsky-Schützenberger theorem states that the generating function of the number of words of a unambiguous CFL is algebraic. In his paper, Flajolet proves that several CFL are inherently ambiguous by showing that their generating function is transcendental (their “local behavior” around their singularities is characteristic of transcendental functions, for example, logarithmic terms appear in the expansion).
More generally, you should look at Analytic combinatorics. It gives a beautiful connection between formal structures and complex analysis.
Flajolet, Philippe, Analytic models and ambiguity of context-free languages, Theor. Comput. Sci. 49, 283-309 (1987). ZBL0612.68069.
$\begingroup$
$\endgroup$
1
Works of Konstantin V. Safonov may be interesting. For example "On Solvability of Systems of Symbolic Polynomial Equations".
Systems of non-commutative polynomial equations which are discussed in this work may be treated as grammars that generate formal languages. For example, context-free languages. This relation is discussed in the Introduction.
There are more works of Konstantin V. Safonov on this topic, and some of them are more closed to formal languages theory, but they are in Russian. For example AN INTEGRAL REPRESENTATION OF THE SYNTACTICAL POLYNOMIAL.
A full list of publications you can found here: http://www.mathnet.ru/rus/person37125
-
$\begingroup$ I don’t think it answers the question. The paper linked is about an algebraic problem. I don’t see any interesting connection with analysis there. $\endgroup$ Jan 14, 2019 at 14:24