DKDohan Kim

Dohan Kim

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Open Access

    Congruence Closure Modulo Groups

    by Dohan Kim

    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

    An Isabelle Formalization of Co-rewrite Pairs for Non-reachability in Term Rewriting

    by Dohan Kim, Teppei Saito, René Thiemann, Akihisa Yamada

    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

    Finding k Shortest Paths in Cayley Graphs of Finite Groups

    by Dohan Kim

    We present a new method for finding k shortest paths between any two vertices in the Cayley graph $$\text {Cay}(G, S)$$ 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)$$ 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)$$ Cay ( G , S ) . Our implementation of finding k shortest paths between two vertices in $$\text {Cay}(G, S)$$ Cay ( G , S ) is also discussed.

  • Open Access

    Equational theorem proving for clauses over strings

    by Dohan Kim

    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

    Equational Theorem Proving Modulo

    by Dohan Kim, Christopher Lynch

    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.