Dohan Kim
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Dohan Kim has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Akihisa Yamada
National Institute of Advanced Industrial Science and Technology
1 shared publication - Christopher Lynch
Clarkson University
1 shared publication - René Thiemann
UNIVERSITY OF INNSBRUCK, INNSBRUCK, Austria
1 shared publication - Teppei Saito
JAIST
1 shared publication
Latest Publications
- Open Access
- 28 February 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Congruence Closure Modulo Groups
This paper presents a new framework for constructing congruence closure of a finite set of ground equations over uninterpreted symbols and interpreted symbols for the group axioms. In this framework, ground equations are flattened into certain forms by introducing new constants, and a completion procedure is performed on ground flat equations. The proposed completion procedure uses equational inference rules and constructs a ground convergent rewrite system for congruence closure with such interpreted symbols. If the completion procedure terminates, then it yields a decision procedure for the word problem for a finite set of ground equations with respect to the group axioms. This paper also provides a sufficient terminating condition of the completion procedure for constructing a ground convergent rewrite system from ground flat equations containing interpreted symbols for the group axioms. In addition, this paper presents a new method for constructing congruence closure of a finite set of ground equations containing interpreted symbols for the semigroup, monoid, and the multiple disjoint sets of group axioms, respectively, using the proposed framework.
- 28 February 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 21, Is
Open AccessCongruence Closure Modulo Groups
This paper presents a new framework for constructing congruence closure of a finite set of ground equations over uninterpreted symbols and interpreted symbols for the group axioms. In this framework, ground equations are flattened into certain forms by introducing new constants, and a completion procedure is performed on ground flat equations. The proposed completion procedure uses equational inference rules and constructs a ground convergent rewrite system for congruence closure with such interpreted symbols. If the completion procedure terminates, then it yields a decision procedure for the word problem for a finite set of ground equations with respect to the group axioms. This paper also provides a sufficient terminating condition of the completion procedure for constructing a ground convergent rewrite system from ground flat equations containing interpreted symbols for the group axioms. In addition, this paper presents a new method for constructing congruence closure of a finite set of ground equations containing interpreted symbols for the semigroup, monoid, and the multiple disjoint sets of group axioms, respectively, using the proposed framework.
- Open Access
- 10 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 272-282
An Isabelle Formalization of Co-rewrite Pairs for Non-reachability in Term Rewriting
In this paper, we present an Isabelle/HOL formalization of co-rewrite pairs for non-reachability analysis in term rewriting. In particular, we formalize polynomial interpretations over negative integers as well as the weighted path order (WPO) and its variant co-WPO. With this formalization, the verified certifier CeTA is now able to check such non-reachability proofs, including those for non-reachability problems of a database where existing tools fail to provide certified proofs.
- 10 January 2025
- Published by Association for Computing Machinery (ACM)
- p. 272-282
Open AccessAn Isabelle Formalization of Co-rewrite Pairs for Non-reachability in Term Rewriting
In this paper, we present an Isabelle/HOL formalization of co-rewrite pairs for non-reachability analysis in term rewriting. In particular, we formalize polynomial interpretations over negative integers as well as the weighted path order (WPO) and its variant co-WPO. With this formalization, the verified certifier CeTA is now able to check such non-reachability proofs, including those for non-reachability problems of a database where existing tools fail to provide certified proofs.
- Open Access
- 7 November 2024
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 40 (6) , 1-16
Finding k Shortest Paths in Cayley Graphs of Finite Groups
We present a new method for finding k shortest paths between any two vertices in the Cayley graph $$\text {Cay}(G, S)$$ of a finite group G with its generating set S closed under inverses. By using a reduced convergent rewriting system R for G, we first find the lexicographically minimal shortest path between two vertices in $$\text {Cay}(G, S)$$ . Then, by symmetrizing the length-preserving rules of R, we provide a polynomial time algorithm (in the size of certain rewrite rules, the lexicographically minimal shortest path, and k) for finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ . Our implementation of finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ is also discussed.- 7 November 2024
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 40 (6) , 1-16
Open AccessFinding k Shortest Paths in Cayley Graphs of Finite Groups
We present a new method for finding k shortest paths between any two vertices in the Cayley graph $$\text {Cay}(G, S)$$ of a finite group G with its generating set S closed under inverses. By using a reduced convergent rewriting system R for G, we first find the lexicographically minimal shortest path between two vertices in $$\text {Cay}(G, S)$$ . Then, by symmetrizing the length-preserving rules of R, we provide a polynomial time algorithm (in the size of certain rewrite rules, the lexicographically minimal shortest path, and k) for finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ . Our implementation of finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ is also discussed. - Open Access
- 18 April 2024
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 34 (10) , 1055-1078
Equational theorem proving for clauses over strings
Although reasoning about equations over strings has been extensively studied for several decades, little research has been done for equational reasoning on general clauses over strings. This paper introduces a new superposition calculus with strings and present an equational theorem proving framework for clauses over strings. It provides a saturation procedure for clauses over strings and show that the proposed superposition calculus with contraction rules is refutationally complete. In particular, this paper presents a new decision procedure for solving word problems over strings and provides a new method of solving unification problems over strings w.r.t. a set of conditional equations R over strings if R can be finitely saturated under the proposed inference system with contraction rules.
- 18 April 2024
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 34 (10) , 1055-1078
Open AccessEquational theorem proving for clauses over strings
Although reasoning about equations over strings has been extensively studied for several decades, little research has been done for equational reasoning on general clauses over strings. This paper introduces a new superposition calculus with strings and present an equational theorem proving framework for clauses over strings. It provides a saturation procedure for clauses over strings and show that the proposed superposition calculus with contraction rules is refutationally complete. In particular, this paper presents a new decision procedure for solving word problems over strings and provides a new method of solving unification problems over strings w.r.t. a set of conditional equations R over strings if R can be finitely saturated under the proposed inference system with contraction rules.
- Open Access
- 5 July 2021
- Published by Springer Nature
- p. 166-182
Equational Theorem Proving Modulo
Unlike other methods for theorem proving modulo with constrained clauses [12, 13], equational theorem proving modulo with constrained clauses along with its simplification techniques has not been well studied. We introduce a basic paramodulation calculus modulo equational theories E satisfying certain properties of E and present a new framework for equational theorem proving modulo E with constrained clauses. We propose an inference rule called Generalized E-Parallel for constrained clauses, which makes our inference system completely basic, meaning that we do not need to allow any paramodulation in the constraint part of a constrained clause for refutational completeness. We present a saturation procedure for constrained clauses based on relative reducibility and show that our inference system including our contraction rules is refutationally complete.
- 5 July 2021
- Published by Springer Nature
- p. 166-182
Open AccessEquational Theorem Proving Modulo
Unlike other methods for theorem proving modulo with constrained clauses [12, 13], equational theorem proving modulo with constrained clauses along with its simplification techniques has not been well studied. We introduce a basic paramodulation calculus modulo equational theories E satisfying certain properties of E and present a new framework for equational theorem proving modulo E with constrained clauses. We propose an inference rule called Generalized E-Parallel for constrained clauses, which makes our inference system completely basic, meaning that we do not need to allow any paramodulation in the constraint part of a constrained clause for refutational completeness. We present a saturation procedure for constrained clauses based on relative reducibility and show that our inference system including our contraction rules is refutationally complete.