Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System

• Autorzy: Adinayev Arthur , Stein Itamar

Identyfikatory

DOI

10.3233/FI-2021-2002

• Języki publikacji: EN

Abstrakty

EN

In this paper, we study a certain case of a subgraph isomorphism problem. We consider the Hasse diagram of the lattice M_k (the unique lattice with k + 2 elements and one anti-chain of length k ) and find the maximal k for which it is isomorphic to a subgraph of the reduction graph of a given one-rule string rewriting system. We obtain a complete characterization for this problem and show that there is a dichotomy. There are one-rule string rewriting systems for which the maximal such k is 2 and there are cases where there is no maximum. No other intermediate option is possible.

Słowa kluczowe

EN

one-rule string rewriting systems; reduction graph; subgraph isomorphism problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 3
• Strony: 173--185
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Adinayev Arthur

• Software Engineering Department, Shamoon College of Engineering, Israel

autor

Stein Itamar

• Mathematics Unit, Shamoon College of Engineering, Israel

Bibliografia

• [1] Lallement G. The word problem for Thue rewriting systems. In: Term rewriting (Font Romeux, 1993), volume 909 of Lecture Notes in Comput. Sci., pp. 27-38. Springer, Berlin, 1995. doi:10.1007/3-540-59340-3_3.
• [2] Geser A. Termination of string rewriting rules that have one pair of overlaps. In: Rewriting techniques and applications, volume 2706 of Lecture Notes in Comput. Sci., pp. 410-423. Springer, Berlin, 2003. doi:10.1007/3-540-44881-0_29.
• [3] Shikishima-Tsuji K, Katsura M, Kobayashi Y. On termination of confluent one-rule string-rewriting systems. Inform. Process. Lett., 1997. 61(2):91-96. doi:10.1016/S0020-0190(96)00200-1.
• [4] Dershowitz N. Open. Closed. Open. In: Term rewriting and applications, volume 3467 of Lecture Notes in Comput. Sci., pp. 376-393. Springer, Berlin, 2005. doi:10.1007/978-3-540-32033-3_28.
• [5] Adjan SI. Defining relations and algorithmic problems for groups and semigroups. Proceedings of the Steklov Institute of Mathematics, No. 85 (1966). Translated from the Russian by M. Greendlinger. American Mathematical Society, Providence, R.I., 1966. URL http://mi.mathnet.ru/eng/tm/v85/p3.
• [6] Adjan S, Oganesjan G. On the word and divisibility problems in semigroups with a single defining relation. Mathematics of the USSR-Izvestiya, 1978. 12(2):207. doi:10.1070/im1978v012n02abeh001848.
• [7] Book RV, Otto F. String-rewriting systems. Texts and Monographs in Computer Science. Springer-Verlag, New York, 1993. ISBN 0-387-97965-4. doi:10.1007/978-1-4613-9771-7.
• [8] Stein I. Reducing the gradedness problem of string rewriting systems to a termination problem. RAIRO Theor. Inform. Appl., 2015. 49(3):233-254. doi:10.1051/ita/2015008.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).