TSTeppei Saito

Teppei Saito

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Teppei Saito has a total of 7 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    An Applicative Multiset Path Order

    by Nao Hirokawa, Teppei Saito, Teppei Tanaka, Wataru Yachi

    We present a variant of the multiset path order for untyped applicative term rewriting. Compared to existing work, our variant incorporates two distinctive features, dubbed arity assignment and reification, to overcome difficulties in handling partial and variable application.

  • Open Access

    The ARI Infrastructure for Automated Confluence Analysis

    by Nao Hirokawa, Aart Middeldorp, Teppei Saito, René Thiemann

    We report on the new ARI infrastructure that supports tools and competitions in term rewriting. It offers ARI-COPS, a database for confluence problems and competition results, and ARIWeb, a convenient web interface for tools that participate in the annual confluence competition. These are built on top of the new ARI format for rewrite systems, a format converter, certifiers for competition results, and a duplicate checker.

  • Open Access

    Lexicographic Combination of Reduction Pairs

    by Teppei Saito, Nao Hirokawa

    We present a simple criterion for combining reduction pairs lexicographically. The criterion is applicable to arbitrary classes of reduction pairs, such as the polynomial interpretation, the matrix interpretation, and the Knuth–Bendix order. In addition, we investigate a variant of the matrix interpretation where the lexicographic order is employed instead of the usual component-wise order. Effectiveness is demonstrated by experiments and examples, including Touzet’s Hydra Battle.


  • 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

    Weighted Path Orders Are Semantic Path Orders

    by Teppei Saito, Nao Hirokawa

    We explore the relationship between weighted path orders and (monotonic) semantic path orders. Our findings reveal that weighted path orders can be considered instances of a variant of semantic path orders that comprise order pairs. This observation leads to a generalization of weighted path orders that does not impose simplicity on their underlying algebras. As a result, the generalized version is capable of proving termination of term rewrite systems beyond the realm of simple termination. In order to assess practicality we provide experimental data comparing generalized weighted path orders with the original ones as well as other well-known classes of reduction orders.