On the task of extracting the root from the language
Abstract
In this paper,we consider a special case of constructing the inverse morphism for the given finite language: we try to extract the root from this language. For such extracting, we consider some special simple cases.
We shall firstly look at some special class of languages, for which the problem is solved easily. Namely, we describe this class, consider some examples, and give some obtained results of computer experiments. Then we define antiderivative roots and give some propositions that show, how to use antiderivative roots for obtaining any root of the given degree.
Then we give an interesting example, which refutes a possible simple algorithm for this task. Therefore, if there exists a polynomial-time algorithm that solves this problem, then it should be formulated more complicated.
We hope that the further development of the theory described in this paper will provide an opportunity to describe a polynomial-time algorithms for solving the general case of this problem.
Full Text:
PDFReferences
Melnikov B., Vylitok A., and Melnikova E. Iterations of languages and finite automata. International Journal of Open Information Technologies. 2017, vol. 5, no. 12, pp. 1-7. (in Russian, http://injoit.org/index.php/j1/article/view/496)
Melnikov B. The equality condition for infinite catenations of two sets of finite words. International Journal of Foundations of Computer Science. 1993, vol. 4, no. 3, pp. 267-274.
Melnikov B. Description of special submonoids of the global supermonoid of the free monoid. News of higher educational institutions. Mathematics. 2004, no. 3, pp. 46-56. (in Russian, https://elibrary.ru/item.asp?id=9083702)
Korabelshchikova S., and Melnikov B. Maximum prefix codes and subclasses of the context-free language class. Bulletin of Northern (Arctic) Federal University. Series: Natural Sciences. 2015, no. 1, pp. 121-129. (in Russian, https://elibrary.ru/item.asp?id=23141792)
Korabelshchikova S., and Melnikov B. On the common root of elements
of the global supermonoid. Bulletin of Northern (Arctic) Federal University. Series: Natural Sciences. 2016, no. 3, pp. 91-96.
(in Russian, https://elibrary.ru/item.asp?id=27126372)
Salomaa A. Jewels of formal language theory. Computer Science Press, Inc. (Maryland, USA), 1981, 157 p.
Melnikov B. Some consequences of the equivalence condition of unambiguous bracketed grammars. Bulletin of Moscow University, ser. 15 (Moscow University Computational Mathematics and Cybernetics). 1991, no. 3, pp. 51-53. (in Russian, https://elibrary.ru/title_about.asp?id=8373)
Dubasova O., and Melnikov B. About one extension of CF-languages class. Programmirovanie (Programming and Computer Software). 1995, no. 6, pp. 46-58. (in Russian, https://elibrary.ru/title_about.asp?id=7966)
Melnikov B., and Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages. Informatica (Lithuania). 2000, vol. 11, no. 4, pp. 441-454. (https://www.mii.lt/informatica/htm/INFO222.htm)
Ginsburg S. The Mathematical Theory of Context-free Languages. McGraw-Hill Ed. (N.Y., USA), 1966, 245 p.
Stanevichene L. About one tool of context-free languages research. Cybernetics. 1989, no. 4, pp. 135-136. (in Russian, http://www.kibernetika.org/contents/89.doc)
Gomozov A., and Stanevichene L. A generalization of regular expressions. Informatica (Lithuania). 1999, vol. 10, no. 1, pp. 27-44.(https://www.mii.lt/informatica/htm/INFO140.htm)
Meytus V. The decidability of the problem of equivalence for deterministic push-down automata. Cybernetics and system analysis. 1992, no. 5, pp. 20-45. (in Russian, http://www.kibernetika.org/contents/92.doc)
Senizergues G. L(A)=L(B)? Decidability results from complete formal systems. Theoretical Computer Science. 2001, vol. 251, no. 1-2, pp. 1- 166.
Melnikov B. Some equivalence problems for free monoids and for subclasses of the CF-grammars class. Number theoretic and algebraic methods in computer science, Proceedings of the International Conference, World Scientific Publ. 1995, pp. 125-137. (https://doi.org/10.1142/9789814532532)
Melnikov B. $2omega$-finite automata and sets of obstructions of their languages The Korean Journal of Computational and Applied Mathematics.
, vol. 6, no. 3, pp. 565-574. (https://doi.org/10.1007/BF03009949)
Melnikov B. On $omega$-languages of special billiards Discrete Mathematics. 2002, vol. 14, no. 3, pp. 95-108. (http://www.mathnet.ru/dm)
Melnikov B., and Melnikova E. Some more on the billiard languages
and corresponding forbidden languages. Proceedings of International Conference on Infinity in Logic & Computation. Cape Town. 2007, pp. 35-36.
Ufnarovskii V. Combinatorial and asymptotic methods in algebra. Results of science and technology, ser. Modern Problems of Mathematics, Algebra. 1990, vol. 6, pp. 5-177. (in Russian, (http://mi.mathnet.ru/intf160)
Belov A., Borisenko V., and Latyshev V. Monomial algebras. Journal of Mathematical Sciences, 1997, vol. 87, no. 3, pp. 3463-3575.
Vylitok A. About building the graph of a push-down automaton. Bulletin of Moscow University, ser. 15 (Moscow University Computational Mathematics and Cybernetics). 1996, no. 3, pp. 68-73. (in Russian, https://elibrary.ru/title_about.asp?id=8373)
Vylitok A., Zubova M., and Melnikov B. An extension of the class of finite automata to specify the context-free languages. Bulletin of Moscow University, ser. 15 (Moscow University Computational Mathematics and Cybernetics). 2013, no. 1, pp. 39-45. (in Russian, https://elibrary.ru/item.asp?id=18862999)
Generalova T., Melnikov B., and Vylitok A. On the extension of the finite automata class for context-free languages specification. International Journal of Open Information Technologies. 2018, vol. 6, no. 9, pp. 1-8.
(in Russian, http://injoit.org/index.php/j1/article/view/602)
Brosalina A., and Melnikov B.. Commutation in global supermonoid
of free monoids. Informatica (Lithuania). 2000, vol. 11, no. 41, pp. 353-370. (https://www.mii.lt/informatica/htm/ INFO220.htm)
Birkhoff G., and Mak Lane S. A DServey of Modern Algebra. Macmillan Publishing Co., Inc. (N.Y., USA), 1977, 500 p.
Zyablitseva L., Korabelshchikova S., and Chesnokov A. Linear codes correcting errors and their counting algorithms. Heuristic Algorithms and Distributed Computing. 2014, vol. 1, no. 3, pp. 47-59. (in Russian, https://elibrary.ru/item.asp?id=22376177).
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162