2026-07-23T20:16:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24608 2025-12-12T15:09:54Z ddc:004 open_access

An Isabelle/HOL Formalization of Semi-Thue and Conditional Semi-Thue Systems Kim, Dohan semi-Thue systems conditional semi-Thue systems conditional string rewriting monoids word problem We present a formalized framework for semi-Thue and conditional semi-Thue systems for studying monoids and their word problem using the Isabelle/HOL proof assistant. We provide a formalized decision procedure for the word problem of monoids if they are finitely presented by complete semi-Thue systems. In particular, we present a new formalized method for checking confluence using (conditional) critical pairs for certain conditional semi-Thue systems. We propose and formalize an inference system for generating conditional equational theories and Thue congruences using conditional semi-Thue systems. Then we provide a new formalized decision procedure for the word problem of monoids which have finite complete (reductive) conditional presentations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dohan Kim 2025 Is Part Of LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITP.2025.10 urn:nbn:de:0030-drops-246081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode