Computing knowledge in equational extensions of subterm convergent theories
- 2 March 2020
- journal article
- conference paper
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 30 (6) , 683-709
Abstract
We study decision procedures for two knowledge problems critical to the verification of security protocols, namely the intruder deduction and the static equivalence problems. These problems can be related to particular forms of context matching and context unification. Both problems are defined with respect to an equational theory and are known to be decidable when the equational theory is given by a subterm convergent term rewrite system (TRS). In this work, we extend this to consider a subterm convergent TRS defined modulo an equational theory, like Commutativity. We present two pairs of solutions for these important problems. The first solves the deduction and static equivalence problems in rewrite systems modulo shallow theories such as Commutativity. The second provides a general procedure that solves the deduction and static equivalence problems in subterm convergent systems modulo syntactic permutative theories, provided a finite measure is ensured. Several examples of such theories are also given.Keywords
This publication has 39 references indexed in Scilit:
- YAPAACM Transactions on Computational Logic, 2013
- Folding variant narrowing and optimal variant terminationThe Journal of Logic and Algebraic Programming, 2012
- Decidability and Combination Results for Two Notions of Knowledge in Security ProtocolsJournal of Automated Reasoning, 2010
- Computing Knowledge in Security Protocols Under Convergent Equational TheoriesJournal of Automated Reasoning, 2010
- Hierarchical combination of intruder theoriesInformation and Computation, 2008
- Deciding knowledge in security protocols under equational theoriesTheoretical Computer Science, 2006
- An NP decision procedure for protocol insecurity with XORTheoretical Computer Science, 2005
- Syntacticness, Cycle-Syntacticness, and Shallow TheoriesInformation and Computation, 1994
- Unification in permutative equational theories is undecidableJournal of Symbolic Computation, 1989
- Completion of a Set of Rules Modulo a Set of EquationsSIAM Journal on Computing, 1986