Infinite trees in the algorithm for checking the equivalence condition of iterations of finite languages. Part I

Boris Melnikov, Aleksandra Melnikova

Abstract


In this paper, we return to the topic, related to one important binary relation on the set of formal languages (considered primarily on the set of iterations of nonempty finite languages), i.e. the equivalence relation at infinity. First of all, we consider examples of the application of this relation (both examples of the need for its implementation, and examples of its use) in various fields of the theory of formal languages, discrete mathematics, and abstract algebra. To simplify the consideration of equivalence at infinity we formulate a simpler binary relation over the set of languages, i.e. the covering relation, the double application of which is equivalent to the application of the equivalence relation at infinity. Next, we consider an algorithm for verifying the fulfillment of the coverage relation, and then we define auxiliary objects used both for proving the correctness of this algorithm and for other problems in the theory of formal languages. As one of the comments on the algorithm, we give the corresponding computer program, consider examples of its operation for specific input languages, after that, we formulate the definitions of the objects associated with them, in particular, the definition of infinite trees of the coverage relation. With their help we prove the correctness of the algorithm for checking the fulfillment of the coverage relation, and also estimate the complexity of this algorithm.

Full Text:

PDF (Russian)

References


Melnikov B. Some consequences of the equivalence condition of unambiguous bracketed grammars // Bulletin of the Moscow University, Series 15 (“Computational Mathematics and Cybernetics”). – 1991. – No. 10. – P. 51–53 (in Russian).

Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundation of Computer Science. – 1993. – Vol. 4. No. 3. – P. 267–274.

Melnikov B. Some equivalence problems for free monoids and for subclasses of the CF­grammars class // Number theoretic and algebraic methods in computer science, World Sci Publ. – 1995. – P. 125–137.

Dubasova О., Melnikov B. On an extension of the context­free language class // Programming (Russian Academy of Sciences). – 1995. – No. 6. – P. 46–58 (in Russian).

Melnikov B. Algoritm proverki ravenstva beskonechnyh iteracij konechnyh jazykov // Bulletin of the Moscow University, Series 15 (“Computational Mathematics and Cybernetics”). – 1996. – No. 4. – P. 49–54 (in Russian).

Brosalina A., Melnikov B. Commutation in global supermonoid of free monoids // Informatica (Lithuanian Academy of Sciences). – 2000. – Vol. 11. No. 4. – P. 353–370.

Melnikov B., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuanian Academy of Sciences). – 2000. – Vol. 11. No. 4. – P. 441– 454.

Melnikov B. The description of special submonoids of the global supermonoid of the free monoid // News of Higher Educational Institutions. Mathematics. – 2004. – No. 3. – P. 46–56 (in Russian).

Алексеева А., Melnikov B. Iterations of finite and infinite languages and nondeterministic finite automata // Vector of Science of Togliatti State University. – 2011. – No. 3 (17). – P. 30–33 (in Russian).

Melnikov B., Korabelshchikova S., Dolgov V. On the task of extracting the root from the language // International Journal of Open Information Technologies. – 2019. – Vol. 7. No. 3. – P. 1–6.

Melnikov B., Melnikova A. The problem of equality in the class of bracketed languages and its use in automation systems for building compilers // IOP Conference Series: Materials Science and Engineering. – 2020. – No. 919 (5). – 052061.

Lallement G. Semigroups and Combinatorial Applications. – NJ, Wiley & Sons, Inc. – 1979. – 376 p.

Aho A., Ullman J. The Theory of Parsing, Translation and Compiling. Vol. 1. Parsing. NJ, Prentice Hall. – 1972. – 2051 p.

Sénizergues G. L(A) = L(B)? decidability results from complete formal systems // Theoretical Computer Science. – 2001. – Vol. 251. No. 1–2. – P. 1–166.

Staneviciené L. On a research facility without contextual languages // Cybernetics. – 1989. – No. 4. – P. 135–136 (in Russian).

Staneviciené L. D­graphs in context­free language theory // Informatica (Lithuanian Academy of Science Ed.) – 1997. – Vol. 8. No. 1. – P. 43–56.

Meytus V. The solvability of the equivalence problem of deterministic pushdown automata // Cybernetics and systems analysis. – 1992. – No. 5. – P. 20–45 (in Russian).

Marchenkov S. About alphabetic coding for superwords // Problems of information transmission. – 2019. – Vol. 55. No. 3. – P. 275–282.

Horváth S., Leupold P., Lischke G. Roots and Powers of Regular Languages // 6th International Conference “Developments in Language Theory”, Kyoto, Japan, 2002. – Lecture Notes in Computer Science, vol. 2450, pp. 220–230. Springer, Heidelberg. – 2003. DOI: 10.1007/3­540­45005­X_19.

Frei F., Hromkovic J., Karhumäki J. Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata // In book: A Mosaic of Computational Topics: from Classical to Novel. – 2020. – DOI: 10.3233/STAL200010.

Salomaa A. Jewels of Formal Language Theory. – Rockville, Maryland, Computer Science Press. – 1981. – 144 p.

Melnikov B., Melnikova A. Some more on omega­finite automata and omega­regular languages. Part I: The main definitions and properties // International Journal of Open Information Technologies. – 2020. – Vol. 8. No. 8. – P. 1–7.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162