cl-banner

Deciding Confluence and Normal Form Properties of Ground Term Rewrite Systems Efficiently

Bertram Felgenhauer

Logical Methods in Computer Science 14(4:7), pp. 1 – 35, 2018.

Abstract

It is known that the first-order theory of rewriting is decidable for ground term rewrite systems, but the general technique uses tree automata and often takes exponential time. For many properties, including confluence (CR), uniqueness of normal forms with respect to reductions (UNR) and with respect to conversions (UNC), polynomial time decision procedures are known for ground term rewrite systems. However, this is not the case for the normal form property (NFP). In this work, we present a cubic time algorithm for NFP, an almost cubic time algorithm for UNR, and an almost linear time algorithm for UNC, improving previous bounds. We also present a cubic time algorithm for CR.

 

  PDF |    doi:10.23638/LMCS-14(4:7)2018 |  © Creative Commons License – CC BY 4.0

BibTeX 

@article{BF-LMCS18,
author = "Bertram Felgenhauer",
title = "Deciding Confluence and Normal Form Properties of
Ground Term Rewrite Systems Efficiently",
journal = "Logical Methods in Computer Science",
volume = 14,
number = "4:7",
pages = "1--35",
year = 2018,
doi = "10.23638/LMCS-14(4:7)2018"
}
Nach oben scrollen