The Experts below are selected from a list of 16095 Experts worldwide ranked by ideXlab platform
Paliath Narendran - One of the best experts on this subject based on the ideXlab platform.
-
Unification and Matching in Hierarchical Combinations of Syntactic Theories
2015Co-Authors: Serdar Erbatur, Deepak Kapur, Paliath Narendran, Andrew Marshall, Christophe RingeissenAbstract:We investigate a hierarchical combination approach to the Unification Problem in non-disjoint unions of equational theories. In this approach, the idea is to extend a base theory with some additional axioms given by rewrite rules in such way that the Unification algorithm known for the base theory can be reused without loss of completeness. Additional techniques are required to solve a combined Problem by reducing it to a Problem in the base theory. In this paper we show that the hierarchical combination approach applies successfully to some classes of syntactic theories, such as shallow theories since the required Unification algorithms needed for the combination algorithm can always be obtained. We also consider the matching Problem in syntactic extensions of a base theory. Due to the more restricted nature of the matching Problem, we obtain several improvements over the Unification Problem.
-
Equational Unification: algorithms and complexity with applications to cryptographic protocol analysis
2012Co-Authors: Paliath Narendran, Andrew M. MarshallAbstract:The techniques and tools of Unification theory have long been a core component of many areas of automated deduction and logic programming. In particular, equational Unification with the purpose of dealing with Unification modulo equational axioms is of critical importance to such areas as automated theorem proving and term rewriting. More recently Unification has become important in formal verification, particularly in cryptographic protocol analysis. We study the algorithmic and complexity issues of several equational theories with respect to the Unification Problem. Specifically, we study the one-sided distributive Unification Problem and the Unification Problem for modular exponentiation. We prove an exponential runtime bound on the algorithm developed by Tiden and Arnborg, for one-sided distributivity, demonstrating the previous polynomial runtime claim for this algorithm was incorrect. The result also implies the existence of exponential, with respect to the initial Unification Problem, most general unifiers. We next show that the decision form of the one-sided distributive Unification Problem is in P by developing a new algorithm with a polynomial bounded runtime. A construction, employing string compression, is used to achieve the polynomial bound. In addition, a new polynomial time algorithm for a variant of one-sided distributivity, called single homomorphism, is developed. We next study a theory for modular exponentiation and develop a new Unification algorithm for this theory. We then show that if this theory is extended in a natural way, by the addition of abelian group axioms for two of the operators, the Unification Problem becomes undecidable. These results help further define the boundary of what theories of exponentiation are usable in protocol analysis.
-
UNIF - Unification modulo a partial theory of exponentiation
Electronic Proceedings in Theoretical Computer Science, 2010Co-Authors: Deepak Kapur, Andrew M. Marshall, Paliath NarendranAbstract:Modular exponentiation is a common mathematical operation in modern cryptography. This, along with modular multiplication at the base and exponent levels (to different moduli) plays an important role in a large number of key agreement protocols. In our earlier work, we gave many decidability as well as undecidability results for multiple equational theories, involving various properties of modular exponentiation. Here, we consider a partial subtheory focussing only on exponentiation and multiplication operators. Two main results are proved. The first result is positive, namely, that the Unification Problem for the above theory (in which no additional property is assumed of the multiplication operators) is decidable. The second result is negative: if we assume that the two multiplication operators belong to two different abelian groups, then the Unification Problem becomes undecidable.
-
Active Intruders with Caps
2008Co-Authors: Siva Anatharaman, Paliath Narendran, Hai Lin, Chris Lynch, Michaël RusinowitchAbstract:We address the insecurity Problem for cryptographic protocols, for an active intruder and a bounded number of sessions. By modeling each protocol step as a rigid Horn clause, and the intruder abilities as an equational theory over a convergent rewrite system, the Problem of active intrusion is formulated as a Cap Unification Problem. Cap Unification is an extension of Equational Unification: we look for a cap to be placed on a given set of terms, so that it unifies with a given term modulo the equational theory.
-
A Unification Algorithm for Analysis of Protocols with Blinded Signatures
Mechanizing Mathematical Reasoning, 2005Co-Authors: Deepak Kapur, Paliath Narendran, Lida WangAbstract:Analysis of authentication cryptographic protocols, particularly finding flaws in them and determining a sequence of actions that an intruder can take to gain access to the information which a given protocol purports not to reveal, has recently received considerable attention. One effective way of detecting flaws is to hypothesize an insecure state and determine whether it is possible to get to that state by a legal sequence of actions permitted by the protocol from some legal initial state which captures the knowledge of the principals and the assumptions made about an intruder’s behavior. Relations among encryption and decryption functions as well as properties of number theoretic functions used in encryption and decryption can be specified as rewrite rules. This, for example, is the approach used by the NRL Protocol Analyzer, which uses narrowing to reason about such properties of cryptographic and number-theoretic functions.Following [15], a related approach is proposed here in which equation solving modulo most of these properties of cryptographic and number-theoretic functions is done by developing new Unification algorithms for such theories. A new Unification algorithm for an equational theory needed to reason about protocols that use the Diffie-Hellman algorithm is developed. In this theory, multiplication forms an abelian group; exponentiation function distributes over multiplication, and exponents can commute. This theory is useful for analyzing protocols which use blinded signatures. It is proved that the Unification Problem over this equational theory can be reduced to the Unification Problem modulo the theory of abelian groups with commuting homomorphisms with an additional constraint. Baader’s Unification algorithm for the theory of abelian groups with commuting homomorphisms, which reduces the Unification Problem to solving equations over the polynomial ring over the integers with the commuting homomorphisms serving as indeterminates, is generalized to give a Unification algorithm over the theory of abelian groups with commuting homomorphism with a linear constraint.It is also shown that the Unification Problem over a (simple) extension of the equational theory considered here (which is also an extension of the equational theory considered in [15]) is undecidable.
Tadao Kasami - One of the best experts on this subject based on the ideXlab platform.
-
Solving a Unification Problem under Constrained Substitutions Using Tree Automata
Journal of Symbolic Computation, 1997Co-Authors: Yuichi Kaji, Toru Fujiwara, Tadao KasamiAbstract:A Unification Problem under constrained substitutions, a generalization of the usual Unification Problems, is a useful formalization of a practical Problem in which there are some constraints on operations and objects that we can use. In this paper, a procedure to solve the Problem under some linearity conditions is introduced. Since the Problem is undecidable in general, the procedure falls into an infinite loop for some instances. We clarify a decidable sufficient condition under which our procedure terminates, and review known classes of term rewriting systems that satisfy the condition. The procedure uses tree automata to solve the Problem, which is quite a new and promising approach to Unification Problems.
-
solving a Unification Problem under constrained substitutions using tree automata
Foundations of Software Technology and Theoretical Computer Science, 1994Co-Authors: Yuichi Kaji, Toru Fujiwara, Tadao KasamiAbstract:A generalization of a Unification Problem for term rewriting systems, named a Unification Problem under constrained substitutions is investigated, and a procedure to solve the Problem with the help of tree automata is presented. Since the Problem is undecidable in general, there are rewriting systems for which our procedure does not terminate. We clarify a sufficient condition undet which the procedure always terminates, and review some classes of rewriting systems that satisfy the condition. These classes include a known decidable class introduced in [6].
-
FSTTCS - Solving a Unification Problem under Constrained Substitutions Using Tree Automata
Lecture Notes in Computer Science, 1994Co-Authors: Yuichi Kaji, Toru Fujiwara, Tadao KasamiAbstract:A generalization of a Unification Problem for term rewriting systems, named a Unification Problem under constrained substitutions is investigated, and a procedure to solve the Problem with the help of tree automata is presented. Since the Problem is undecidable in general, there are rewriting systems for which our procedure does not terminate. We clarify a sufficient condition undet which the procedure always terminates, and review some classes of rewriting systems that satisfy the condition. These classes include a known decidable class introduced in [6].
Michio Oyamaguchi - One of the best experts on this subject based on the ideXlab platform.
-
The Unification Problem for Confluent Semi-Constructor TRSs
IEICE Transactions on Information and Systems, 2010Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Kunihiro MatsuuraAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. We have shown that the Problem is decidable for confluent simple TRSs. Here, a simple TRS means one where the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS means one where all defined symbols appearing in the right-hand side of each rewrite rule occur only in its ground subterms.
-
RTA - The Joinability and Unification Problems for Confluent Semi-constructor TRSs
Rewriting Techniques and Applications, 2004Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Yoshikatsu Ohta, Toshiyuki YamadaAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. Mitsuhashi et al. have shown that the Problem is decidable for confluent simple TRSs. Here, a TRS is simple if the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS is such a TRS that every subterm of the right-hand side of each rewrite rule is ground if its root is a defined symbol. We first show the decidability of joinability for confluent semi-constructor TRSs. Then, using the decision algorithm for joinability, we obtain a Unification algorithm for confluent semi-constructor TRSs.
-
The joinability and Unification Problems for confluent semi-constructor TRSs
Lecture Notes in Computer Science, 2004Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Yoshikatsu Ohta, Toshiyuki YamadaAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. Mitsuhashi et al. have shown that the Problem is decidable for confluent simple TRSs. Here, a TRS is simple if the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS is such a TRS that every subterm of the right-hand side of each rewrite rule is ground if its root is a defined symbol. We first show the decidability of joinability for confluent semi-constructor TRSs. Then, using the decision algorithm for joinability, we obtain a Unification algorithm for confluent semi-constructor TRSs.
-
RTA - The Unification Problem for Confluent Right-Ground Term Rewriting Systems
Information and Computation, 2003Co-Authors: Michio Oyamaguchi, Yoshikatsu OhtaAbstract:The Unification Problem for term rewriting systems(TRSs) is the Problem of deciding, for a given TRS R and two terms M and N, whether there exists a substitution θ such that Mθ and Nθ are congruent modulo R (i.e., Mθ ↔R* Nθ). In this paper, the Unification Problem for confluent right-ground TRSs is shown to be decidable. To show this, the notion of minimal terms is introduced and a new Unification algorithm of obtaining a substitution whose range is in minimal terms is proposed. Our result extends the decidability of Unification for canonical (i.e., confluent and terminating) right-ground TRSs given by Hullot (1980) in the sense that the termination condition can be omitted. It is also exemplified that Hullot's narrowing technique does not work in this case. Our result is compared with the undecidability of the word (and also Unification) Problem for terminating right-ground TRSs.
-
the Unification Problem for confluent right ground term rewriting systems
Rewriting Techniques and Applications, 2001Co-Authors: Michio Oyamaguchi, Yoshikatsu OhtaAbstract:The Unification Problem for term rewriting systems(TRSs) is the Problem of deciding, for a given TRS R and two terms M and N, whether there exists a substitution θ such that Mθ and Nθ are congruent modulo R (i.e., Mθ ↔R* Nθ). In this paper, the Unification Problem for confluent right-ground TRSs is shown to be decidable. To show this, the notion of minimal terms is introduced and a new Unification algorithm of obtaining a substitution whose range is in minimal terms is proposed. Our result extends the decidability of Unification for canonical (i.e., confluent and terminating) right-ground TRSs given by Hullot (1980) in the sense that the termination condition can be omitted. It is also exemplified that Hullot's narrowing technique does not work in this case. Our result is compared with the undecidability of the word (and also Unification) Problem for terminating right-ground TRSs.
Toshiyuki Yamada - One of the best experts on this subject based on the ideXlab platform.
-
RTA - The Joinability and Unification Problems for Confluent Semi-constructor TRSs
Rewriting Techniques and Applications, 2004Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Yoshikatsu Ohta, Toshiyuki YamadaAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. Mitsuhashi et al. have shown that the Problem is decidable for confluent simple TRSs. Here, a TRS is simple if the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS is such a TRS that every subterm of the right-hand side of each rewrite rule is ground if its root is a defined symbol. We first show the decidability of joinability for confluent semi-constructor TRSs. Then, using the decision algorithm for joinability, we obtain a Unification algorithm for confluent semi-constructor TRSs.
-
The joinability and Unification Problems for confluent semi-constructor TRSs
Lecture Notes in Computer Science, 2004Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Yoshikatsu Ohta, Toshiyuki YamadaAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. Mitsuhashi et al. have shown that the Problem is decidable for confluent simple TRSs. Here, a TRS is simple if the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS is such a TRS that every subterm of the right-hand side of each rewrite rule is ground if its root is a defined symbol. We first show the decidability of joinability for confluent semi-constructor TRSs. Then, using the decision algorithm for joinability, we obtain a Unification algorithm for confluent semi-constructor TRSs.
Yoshikatsu Ohta - One of the best experts on this subject based on the ideXlab platform.
-
RTA - The Joinability and Unification Problems for Confluent Semi-constructor TRSs
Rewriting Techniques and Applications, 2004Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Yoshikatsu Ohta, Toshiyuki YamadaAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. Mitsuhashi et al. have shown that the Problem is decidable for confluent simple TRSs. Here, a TRS is simple if the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS is such a TRS that every subterm of the right-hand side of each rewrite rule is ground if its root is a defined symbol. We first show the decidability of joinability for confluent semi-constructor TRSs. Then, using the decision algorithm for joinability, we obtain a Unification algorithm for confluent semi-constructor TRSs.
-
The joinability and Unification Problems for confluent semi-constructor TRSs
Lecture Notes in Computer Science, 2004Co-Authors: Ichiro Mitsuhashi, Michio Oyamaguchi, Yoshikatsu Ohta, Toshiyuki YamadaAbstract:The Unification Problem for term rewriting systems (TRSs) is the Problem of deciding, for a TRS R and two terms s and t, whether s and t are unifiable modulo R. Mitsuhashi et al. have shown that the Problem is decidable for confluent simple TRSs. Here, a TRS is simple if the right-hand side of every rewrite rule is a ground term or a variable. In this paper, we extend this result and show that the Unification Problem for confluent semi-constructor TRSs is decidable. Here, a semi-constructor TRS is such a TRS that every subterm of the right-hand side of each rewrite rule is ground if its root is a defined symbol. We first show the decidability of joinability for confluent semi-constructor TRSs. Then, using the decision algorithm for joinability, we obtain a Unification algorithm for confluent semi-constructor TRSs.
-
RTA - The Unification Problem for Confluent Right-Ground Term Rewriting Systems
Information and Computation, 2003Co-Authors: Michio Oyamaguchi, Yoshikatsu OhtaAbstract:The Unification Problem for term rewriting systems(TRSs) is the Problem of deciding, for a given TRS R and two terms M and N, whether there exists a substitution θ such that Mθ and Nθ are congruent modulo R (i.e., Mθ ↔R* Nθ). In this paper, the Unification Problem for confluent right-ground TRSs is shown to be decidable. To show this, the notion of minimal terms is introduced and a new Unification algorithm of obtaining a substitution whose range is in minimal terms is proposed. Our result extends the decidability of Unification for canonical (i.e., confluent and terminating) right-ground TRSs given by Hullot (1980) in the sense that the termination condition can be omitted. It is also exemplified that Hullot's narrowing technique does not work in this case. Our result is compared with the undecidability of the word (and also Unification) Problem for terminating right-ground TRSs.
-
the Unification Problem for confluent right ground term rewriting systems
Rewriting Techniques and Applications, 2001Co-Authors: Michio Oyamaguchi, Yoshikatsu OhtaAbstract:The Unification Problem for term rewriting systems(TRSs) is the Problem of deciding, for a given TRS R and two terms M and N, whether there exists a substitution θ such that Mθ and Nθ are congruent modulo R (i.e., Mθ ↔R* Nθ). In this paper, the Unification Problem for confluent right-ground TRSs is shown to be decidable. To show this, the notion of minimal terms is introduced and a new Unification algorithm of obtaining a substitution whose range is in minimal terms is proposed. Our result extends the decidability of Unification for canonical (i.e., confluent and terminating) right-ground TRSs given by Hullot (1980) in the sense that the termination condition can be omitted. It is also exemplified that Hullot's narrowing technique does not work in this case. Our result is compared with the undecidability of the word (and also Unification) Problem for terminating right-ground TRSs.
