Reachability, confluence, and termination analysis with state-compatible automata

Citation data:

Information and Computation, ISSN: 0890-5401, Vol: 253, Page: 467-483

Publication Year:
Usage 18
Clicks 13
Abstract Views 5
Social Media 3
Tweets 3
Citations 1
Citation Indexes 1
Bertram Felgenhauer; René Thiemann
Elsevier BV
Mathematics; Computer Science
Most Recent Tweet View All Tweets
article description
Regular tree languages are a popular device for reachability analysis over term rewrite systems, with many applications like analysis of cryptographic protocols, or confluence and termination analysis. At the heart of this approach lies tree automata completion, first introduced by Genet for left-linear rewrite systems. Korp and Middeldorp introduced so-called quasi-deterministic automata to extend the technique to non-left-linear systems. In this paper, we introduce the simpler notion of state-compatible automata, which are slightly more general than quasi-deterministic, compatible automata. This notion also allows us to decide whether a regular tree language is closed under rewriting, a problem which was not known to be decidable before.