The Experts below are selected from a list of 51 Experts worldwide ranked by ideXlab platform
Mateu Villaret - One of the best experts on this subject based on the ideXlab platform.
-
Simplifying the signature in second-order unification
Applicable Algebra in Engineering Communication and Computing, 2009Co-Authors: Jordi Levy, Mateu VillaretAbstract:Second-Order Unification is undecidable even for very specialized fragments. The signature plays a crucial role in these fragments. If all Symbols are monadic, then the problem is NP-complete, whereas it is enough to have just one Binary constant to lose decidability. In this work we reduce Second-Order Unification to Second-Order Unification with a signature that contains just one Binary Function Symbol and constants. The reduction is based on partially currying the equations by using the Binary Function Symbol for explicit application @. Our work simplifies the study of Second-Order Unification and some of its variants, like Context Unification and Bounded Second-Order Unification.
-
RTA - Currying Second-Order Unification Problems
Rewriting Techniques and Applications, 2002Co-Authors: Jordi Levy, Mateu VillaretAbstract:The Curry form of a term, like f(a, b), allows us to write it, using just a single Binary Function Symbol, as @(@(f, a), b). Using this technique we prove that the signature is not relevant in second-order unification, and conclude that one Binary Symbol is enough. By currying variable applications, like X(a), as @(X, a), we can transform second-order terms into first-order terms, but we have to add beta-reduction as a theory. This is roughly what it is done in explicit unification. We prove that by currying only constant applications we can reduce second-order unification to second-order unification with just one Binary Function Symbol. Both problems are already known to be undecidable, but applying the same idea to context unification, for which decidability is still unknown, we reduce the problem to context unification with just one Binary Function Symbol.We also discuss about the difficulties ofapplying the same ideas to third or higher order unification.
-
Currying second-order unification problems
Lecture Notes in Computer Science, 2002Co-Authors: Jordi Levy, Mateu VillaretAbstract:The Curry form of a term, like f(a,b), allows us to write it, using just a single Binary Function Symbol, as @(@(f,a),b). Using this technique we prove that the signature is not relevant in second-order unification, and conclude that one Binary Symbol is enough. By currying variable applications, like X(a), as @(X,a), we can transform second-order terms into first-order terms, but we have to add betareduction as a theory. This is roughly what it is done in explicit unification. We prove that by currying only constant applications we can reduce second-order unification to second-order unification with just one Binary Function Symbol. Both problems are already known to be undecidable, but applying the same idea to context unification, for which decidability is still unknown, we reduce the problem to context unification with just one Binary Function Symbol. We also discuss about the difficulties of applying the same ideas to third or higher order unification.
Jordi Levy - One of the best experts on this subject based on the ideXlab platform.
-
Simplifying the signature in second-order unification
Applicable Algebra in Engineering Communication and Computing, 2009Co-Authors: Jordi Levy, Mateu VillaretAbstract:Second-Order Unification is undecidable even for very specialized fragments. The signature plays a crucial role in these fragments. If all Symbols are monadic, then the problem is NP-complete, whereas it is enough to have just one Binary constant to lose decidability. In this work we reduce Second-Order Unification to Second-Order Unification with a signature that contains just one Binary Function Symbol and constants. The reduction is based on partially currying the equations by using the Binary Function Symbol for explicit application @. Our work simplifies the study of Second-Order Unification and some of its variants, like Context Unification and Bounded Second-Order Unification.
-
RTA - Currying Second-Order Unification Problems
Rewriting Techniques and Applications, 2002Co-Authors: Jordi Levy, Mateu VillaretAbstract:The Curry form of a term, like f(a, b), allows us to write it, using just a single Binary Function Symbol, as @(@(f, a), b). Using this technique we prove that the signature is not relevant in second-order unification, and conclude that one Binary Symbol is enough. By currying variable applications, like X(a), as @(X, a), we can transform second-order terms into first-order terms, but we have to add beta-reduction as a theory. This is roughly what it is done in explicit unification. We prove that by currying only constant applications we can reduce second-order unification to second-order unification with just one Binary Function Symbol. Both problems are already known to be undecidable, but applying the same idea to context unification, for which decidability is still unknown, we reduce the problem to context unification with just one Binary Function Symbol.We also discuss about the difficulties ofapplying the same ideas to third or higher order unification.
-
Currying second-order unification problems
Lecture Notes in Computer Science, 2002Co-Authors: Jordi Levy, Mateu VillaretAbstract:The Curry form of a term, like f(a,b), allows us to write it, using just a single Binary Function Symbol, as @(@(f,a),b). Using this technique we prove that the signature is not relevant in second-order unification, and conclude that one Binary Symbol is enough. By currying variable applications, like X(a), as @(X,a), we can transform second-order terms into first-order terms, but we have to add betareduction as a theory. This is roughly what it is done in explicit unification. We prove that by currying only constant applications we can reduce second-order unification to second-order unification with just one Binary Function Symbol. Both problems are already known to be undecidable, but applying the same idea to context unification, for which decidability is still unknown, we reduce the problem to context unification with just one Binary Function Symbol. We also discuss about the difficulties of applying the same ideas to third or higher order unification.
Mateu Villaret Auselle - One of the best experts on this subject based on the ideXlab platform.
-
On some variants of second-order unification
2004Co-Authors: Mateu Villaret AuselleAbstract:In this thesis we present several results about Second-Order Unification. It is well known that the Second-Order Unification Problem is in general undecidable; the frontier between its decidable and undecidable subclasses is thin and it still has not been completely defined. Our purpose is to shed some light on the Second-Order Unification problem and study some of its variants. We have mainly focused our attention on Context Unification and Linear Second-Order Unification. Roughly speaking, these problems are variants of Second-Order Unification where second-order variables are required to be linear. Context Unification was defined more than ten years ago and its decidability has been an open question since then. Here we make relevant contributions to the study of this question. The first result that we present is a simplification on these problems thanks to "curryfication". We show that the Context Unification problem can be NP-reduced to the Context Unification problem where, apart from variables, just a single Binary Function Symbol, and first-order constants, are used. We also show that a similar result also holds for Second-Order Unification. The main result of this thesis is the definition of a non-trivial sufficient and necessary condition on the unifiers, for the decidability of Context Unification. The condition is called rank-bound conjecture in order to enforce our belief about its truthness. It lies on a non-trivial measure of terms, the rank, and claims that, whenever an instance of the Context Unification problem is satisfiable, there exists a unifier with a rank not exceeding a certain bound depending on the size of the problem. Under the assumption of this conjecture, we give a reduction of the satisfiability problem for Context Unification to the (decidable) satisfiability problem of Word Unification with regular constraints. Finally, in the same spirit of the extension of Word Unification with reg
Wolfgang Rautenberg - One of the best experts on this subject based on the ideXlab platform.
-
COMMON LOGIC OF Binary CONNECTIVES HAS FINITE MAXIMALITY DEGREE (Preliminary report)
2005Co-Authors: Wolfgang RautenbergAbstract:Let Fp be a set of all properly Binary Boolean Functions f : 2 −→ 2, i.e., f depends on both arguments. Of the 16 Binary truth Functions 10 belongs to Fp, namely ∨,→,↔,← (reverse implication), ↑ (Sheffer Function) and the duals of these. For F ⊆ Fp let `F denote the common logic of the f ∈ F in the propositional language with one Binary Function Symbol, `F = ⋂ f∈F |=2f , where 2 denotes the 2-element matrix ((2, f), 1). A study of `F is useful for various purposes, e.g. for information processing, see [3]. `F axiomatizes the common sequential rules of the f ∈ F . It needs not to have tautologies but this is a minor point. Particularly interesting is the question how ambiguous `F actually is, i.e., how much information in form of additional rules needs a system of information proccesing dealing with `F in order to identify a connective f ∈ F . This clearly amounts to an analysis of the strenghtenings ` ⊃ `F . Our main result is
Franz Baader - One of the best experts on this subject based on the ideXlab platform.
-
Extensions of unificationmodulo ACUI
Mathematical Structures in Computer Science, 2019Co-Authors: Franz Baader, Pavlos Marantidis, Antoine Mottet, Alexander OkhotinAbstract:Abstract The theory ACUI of an associative, commutative, and idempotent Binary Function Symbol + with unit 0 was one of the first equational theories for which the complexity of testing solvability of unification problems was investigated in detail. In this paper, we investigate two extensions of ACUI. On one hand, we consider approximate ACUI-unification, where we use appropriate measures to express how close a substitution is to being a unifier. On the other hand, we extend ACUI-unification to ACUIG-unification, that is, unification in equational theories that are obtained from ACUI by adding a finite set G of ground identities. Finally, we combine the two extensions, that is, consider approximate ACUI-unification. For all cases we are able to determine the exact worst-case complexity of the unification problem.
-
The Unification Type of ACUI w.r.t. the Unrestricted Instantiation Preorder is not Finitary
2016Co-Authors: Franz Baader, Pierre LudmannAbstract:The unification type of an equational theory is defined using a preorder on substitutions, called the instantiation preorder, whose scope is either restricted to the variables occurring in the unification problem, or unrestricted such that all variables are considered. It is known that the unification type of an equational theory may vary, depending on which instantiation preorder is used. More precisely, it was shown that the theory ACUI of an associative, commutative, and idempotent Binary Function Symbol with a unit is unitary w.r.t. the restricted instantiation preorder, but not unitary w.r.t. the unrestricted one. Here, we improve on this result, by showing that, w.r.t. the unrestricted instantiation preorder, ACUI is not even finitary.
