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

DOI10.3233/FI-2021-2002MaRDI QIDQ4989173zbMATH OpenOpenAlexFDO

Authors Arthur Adinayev, Itamar Stein

Publication date 21 May 2021

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.02644

zbMATH Keywords

one-rule string rewriting systemsreduction graphsubgraph isomorphism problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Grammars and rewriting systems (68Q42)

Abstract: 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 want to 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.

Recommendations

• Graph reducibility of term rewriting systems
• A framework for rewriting families of string diagrams
• Directed diagrammatic reducibility
• scientific article; zbMATH DE number 177461
• Diameters of graphs of reduced words and rank-two root subsystems
• String diagram rewrite theory. I: Rewriting with Frobenius structure
• Termination and derivational complexity of confluent one-rule string-rewriting systems
• Decidability of string graphs
• Decidability of string graphs
• Confluence of indirection reductions in graph rewrite systems

Cites work

• scientific article; zbMATH DE number 2043544 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 3323852 (Why is no real title available?)
• On termination of confluent one-rule string-rewriting systems
• ON THE WORD AND DIVISIBILITY PROBLEMS IN SEMIGROUPS WITH A SINGLE DEFINING RELATION

This page was built for publication: Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989173)