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

Article type: Research Article

Authors: Adinayev, Arthur^a | Stein, Itamar^{b; *}

Affiliations: [a] Software Engineering Department, Shamoon College of Engineering, Israel. arthuad@ac.sce.ac.il | [b] Mathematics Unit, Shamoon College of Engineering, Israel. Steinita@gmail.com

Correspondence: [*] Address for correspondence: Mathematics Unit, Shamoon College of Engineering, Israel.

Abstract: In this paper, we study a certain case of a subgraph isomorphism problem. We consider the Hasse diagram of the lattice Mk (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.

Keywords: one-rule string rewriting systems, reduction graph, subgraph isomorphism problem

DOI: 10.3233/FI-2021-2002

Journal: Fundamenta Informaticae, vol. 178, no. 3, pp. 173-185, 2021