{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,9]],"date-time":"2024-11-09T05:20:17Z","timestamp":1731129617607,"version":"3.28.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["FI"],"published-print":{"date-parts":[[2021,1,15]]},"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.<\/jats:p>","DOI":"10.3233\/fi-2021-2002","type":"journal-article","created":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T17:18:18Z","timestamp":1610731098000},"page":"173-185","source":"Crossref","is-referenced-by-count":0,"title":["Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System"],"prefix":"10.1177","volume":"178","author":[{"given":"Arthur","family":"Adinayev","sequence":"first","affiliation":[{"name":"Software Engineering Department, Shamoon College of Engineering, Israel. arthuad@ac.sce.ac.il"}]},{"given":"Itamar","family":"Stein","sequence":"additional","affiliation":[{"name":"Mathematics Unit, Shamoon College of Engineering, Israel. Steinita@gmail.com"}]}],"member":"179","container-title":["Fundamenta Informaticae"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/FI-2021-2002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T17:14:49Z","timestamp":1731086089000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.medra.org\/servlet\/aliasResolver?alias=iospress&doi=10.3233\/FI-2021-2002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,15]]},"references-count":0,"journal-issue":{"issue":"3"},"URL":"https:\/\/doi.org\/10.3233\/fi-2021-2002","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2021,1,15]]}}}