Journal of Software Engineering and Applications
Vol.7 No.4(2014), Article ID:44915,26 pages DOI:10.4236/jsea.2014.74028
Fuzzy Logic Programming in Action with
Ginés Moreno, Carlos Vázquez
Department of Computing Systems, University of Castilla-La Mancha, Albacete, Spain
Email: Gines.Moreno@uclm.es, Carlos.Vazquez@uclm.es
Copyright © 2014 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Received 14 February 2014; revised 10 March 2014; accepted 18 March 2014
ABSTRACT
During the last years, we have developed the platform for providing a practical support to the so-called Multi-Adjoint Logic Programming approach (MALP in brief), which represents an extremely flexible framework into the Fuzzy Logic Programming arena. Nowadays, is useful for compiling (to standard Prolog code), executing and debugging (by drawing execution trees) MALP programs, and it is ready for being extended in the near future with powerful transformation and optimization techniques designed in our research group during the recent past. Our last update consists in the integration of a graphical interface for a comfortable interaction with the system which allows, among other capabilities, the use of projects for packing scripts and auxiliary definitions of fuzzy sets/connectives, together with fuzzy programs and their associated lattices modeling truth-degrees beyond the simpler crisp case.
Keywords:Fuzzy Logic Programming, Language Design and Implementation, New Programming Concepts and Paradigms, Software Tools, Cost Measures
1. Introduction
Logic programming [1] has been widely used for problem solving and knowledge representation in the past. Nevertheless, traditional pure logic programming languages (i.e., Prolog ) do not incorporate techniques or constructs to explicitly deal with uncertainty and approximated reasoning. To overcome this situation, during the last decades several fuzzy logic programming systems have been developed where the classical inference mechanism of SLD-resolution is replaced with a fuzzy variant able to handle partial truth and to reason with uncertainty, thus promoting the development of real-world applications in the fields of artificial/computational intelligence, soft-computing, semantic web, etc. Most of these systems implement the fuzzy resolution principle introduced by Lee in [2] , such as languages Prolog-Elf [3] , F-Prolog [4] , Fril [5] , (S-)QLP [6] [7] , RFuzzy [8] and MALP [9] , being this last approach our target goal.
Since uncertainty and vagueness are constant elements present in most human thinking activities, fuzzy logic programming seems to be a computing paradigm with a level of expressiveness very close to human reasoning. Daily, we frequently deal with fuzzy predicates (not boolean, crisp ones). For instance, a person can be quite young or not very young: the frontier between “absolutely young” and “not young at all” is not sharp, but indefinite, fuzzy. If “John” is 18 year old, we can say that he is “young” at a 95% truth degree. If “Mary” is 70 years old, she is young at a lower truth degree. Then, the obvious question is how do we model the concept of “truth degree”. In our system, we work with the so-called multi-adjoint lattices to model them by providing a flexible, wide enough definition of such notion.
Informally speaking, in the multi-adjoint logic framework, a program can be seen as a set of rules each one annotated by a truth degree, and a goal is a query to the system, i.e., a set of atoms linked with connectives called aggregators. A state is a pair where is a goal and a substitution (initially, the identity substitution). States are evaluated in two separate computational phases. During the operational one, admissible steps (a generalization of the classical modus ponens inference rule) are systematically applied by a backward reasoning procedure in a similar way to classical resolution steps in pure logic programming, thus returning a computed substitution together with an expression where all atoms have been exploited. This last expression is then interpreted under a given lattice during what we call the interpretive phase, hence returning a pair which is the fuzzy counterpart of the classical notion of computed answer traditionally used in LP.
The main goal of this report is the detailed description of the system which is available from http://dectau.uclm.es/floper/. Nowadays, the tool provides facilities for executing as well as for debugging (by generating declarative traces) such kind of fuzzy programs, thus fulfilling the gap we have detected in the area. In order to explain the tool, we have structured this paper as follows: in Section 2 we present the essence of MALP , including syntax, procedural semantics, and some interesting computational cost measures defined for this programming style; the core of this paper is represented by Section 3, which is dedicated to explain the main capabilities of the system such as running/debugging MALP programs, managing lattices and dealing with additional fuzzy concepts; before finalizing in Section 5, we detail in Section 4 how the use of sophisticated multi-adjoint lattices are very useful for easily coding flexible real-world applications and obtaining low-cost traces at execution time.
2. Multi-Adjoint Logic Programming
This section summarizes the main features of multi-adjoint logic programming (for a complete formulation of this framework, see [9] -[12] ). In what follows, we use abbreviation MALP for referencing programs belonging to this setting.
2.1. MALP Syntax
We work with a first order language, , containing variables, constants, function symbols, predicate symbols, and several (arbitrary) connectives to increase language expressiveness: implication connectives; conjunctive operators (denoted by), disjunctive operators, and hybrid operators (usually denoted by), all of them are grouped under the name of “aggregators”.
Aggregation operators (or aggregators) are useful to describe/specify user preferences. An aggregation operator, when interpreted as a truth function, may be an arithmetic mean, a weighted sum or in general any monotone application whose arguments are values of a complete bounded lattice. For example, if an aggregator is interpreted as, we are giving the highest preference to the first argument, then to the second, being the third argument the least significant. Although these connectives are binary operators, we usually generalize them as functions with an arbitrary number of arguments. So, we often write instead of. By definition, the truth function for an n-ary aggregation operator is required to be monotonous and fulfills,.
Additionally, our language contains the values of a multi-adjoint lattice equipped with a collection of adjoint pairs (where each is a conjunctor which is intended to the evaluation of modus ponens [9] ) formally defined as follows.
Definition 2.1 (Multi-Adjoint Lattice) Let be a lattice. A multi-adjoint lattice is a tuple such that
1) is a bounded lattice, i.e. it has bottom and top elements, denoted by and, respectively.
2) is a complete lattice, i.e. for all subset, there are and.
3),.
4) Each operation is increasing in both arguments.
5) Each operation is increasing in the first argument and decreasing in the second one.
6) If is an adjoint pair in then, for any, we have that:
This last condition, called adjoint property, could be considered the most important feature of the framework (in contrast with many other approaches) which justifies most of its properties regarding crucial results for soundness, completeness, applicability, etc.
In general, may be the carrier of any complete bounded lattice where a -expression is a well-formed expression composed by values and connectives defined in, as well as variable symbols and primitive operators (i.e., arithmetic symbols such as etc...). In what follows, we assume that the truth function of any connective in is given by its corresponding connective definition, that is, an equation of the form, where is a -expression not containing variable symbols apart from. For instance, consider the following classical set of adjoint pairs (conjunctions and implications) in, where labels, and mean respectively ukasiewicz logic, Gödel intuitionistic logic and product logic (which different capabilities for modeling pessimist, optimist and realistic scenarios, respectively):
Moreover, the three disjunctions associated to the previous fuzzy logics are defined as follows: , , and.
At this point, we wish to make a mention to the notion of qualification domain used in the QLP ( Qualified Logic Programming) scheme described in [6] , which plays a role in that framework similar to multi-adjoint lattices in MALP . A qualification domain is a structure, such that is a lattice with top and bottom elements, a partial ordering, and where the so-called attenuation operation “” is a conjunction. Now, given two elements, means for the greatest lower bound of and, whereas represents its least upper bound. We also write as abbreviation of. The attenuation operator satisfies the following constraints.
1) is associative, commutative and monotonic w.r.t..
2).
3).
4).
5).
Note that the required properties in QLP and MALP are rather close, but instead of the last distributive law just pointed out in claim 5, in our setting we use the adjoint property (claim 6 in Definition 2.1). Translations between both worlds can be frequently performed, as occurs for instance with the simple boolean qualification domain, whose shape as a multi-adjoint lattice looks like, where is de boolean conjunction and its adjoint implication (i.e., the usual bi-valuated logic implication). Something similar occurs with the qualification domain of Van Emden’s uncertainty values used in QLP, , which is equivalent to the multi-adjoint lattice (in which most of our examples are interpreted) described above, as well as with the so-called weights domain, whose detailed explanation is delayed to Section 4 (where we will present powerful extensions and applications related with debugging tasks into the MALP framework).
In general, any qualification domain whose attenuation operation conforms an adjointpair with a given implication operation, can be expressed as the multi-adjoint lattice. Anyway, we wish to finish this brief comparison by highlighting that the variety of connectives definable in multi-adjoint lattices is clearly much greater than those appearing in qualification domains (where for a given program, all rules must always use the same attenuation operator), which justifies the higher expressive power of MALP w.r.t. QLP.
Continuing now with the description of the multi-adjoint logic programming approach, a MALP rule is a formula, where is an atomic formula (usually called the head) and (which is called the body) is a formula built from atomic formulas , truth values of, conjunctions, disjunctions and aggregations. Rules whose body is or equivalently, rules without body (or with empty body) are called facts. A goal is a body submitted as a query to the system.
Roughly speaking, a MALP program is a set of pairs (we often write “”), where is a rule and is a truth degree (a value of) expressing the confidence of a programmer in the truth of rule. By abuse of language, we sometimes refer a tuple as a “rule”. As an example, in Figure 1 we show a MALP program whose rules define fuzzy predicates modeling degrees of youth (“”), heritage (“”) and education (“”), as well as the confidence level (“”) on people for repaying a loan. Note that the seventh rule models this last notion by considering young persons having good heritage or education degrees. In what follows, we are going to explain the procedural principle of MALP programs, whose application to goal “” w.r.t. our program, will assign truth degrees 0.772 (i.e., a credibility of) and 0.38 (or of confidence level) to “mary” and “peter”, respectively.
2.2. MALP Procedural Semantics
The procedural semantics of the multi--adjoint logic language can be thought of as an operational phase (based on admissible steps) followed by an interpretive one. In the following, denotes a formula where is a sub-expression which occurs in the--possibly empty--context. Moreover, means the replacement of by in context, whereas refers to the set of distinct variables occurring in the syntactic object, and denotes the substitution obtained from by restricting its domain to.
Figure 1. MALP program with admissible/interpretive derivations for goal “c(X)”.
Definition 2.2 (Admissible Step) Let be a goal and let be a substitution. The pair is a state and we denote by the set of states. Given a program, an admissible computation is formalized as a state transition system, whose transition relation is the smallest relation satisfying the following admissible rules (where we always consider that is the selected atom in and denotes the most general unifier of an equation set [13] ):
1), if, in and is not empty.
2), if and in.
3), if there is no rule in whose head unifies with.
Note that the second case could be subsumed by the first one, after expressing each fact as a program rule of the form. Also, the third case is introduced to cope with (possible) unsuccessful admissible derivations. As usual, rules are taken renamed apart. We shall use the symbols, and to distinguish between computation steps performed by applying one of the specific admissible rules. Also, the application of a rule on a step will be annotated as a superscript of the symbol.
Definition 2.3 Let be a program, a goal and “” the empty substitution. An admissible derivation is a sequence. When is a formula not containing atoms (i.e., a -expression), the pair, where, is called an admissible computed answer (a.c.a.) for that derivation.
Example 2.4 In Figure 1 we illustrate an admissible derivation (note that the selected atom in each step appears underlined), where the admissible computed answer (a.c.a.) is composed by the pair:
where only refers to bindings related with variables in the goal, i.e.,
If we exploit all atoms of a given goal, by applying enough admissible steps, then it becomes a formula with no atoms (a -expression) which can be interpreted w.r.t. lattice by applying the following definition we initially presented in [14] :
Definition 2.5 (Interpretive Step) Let be a program, a goal and a substitution. Assume that is the truth function of connective in the lattice associated to, such that, for values, we have that. Then, we formalize the notion of interpretive computation as a state transition system, whose transition relation is defined as the least one satisfying:
.
Definition 2.6 Let be a program and an a.c.a., that is, does not contain atoms (i.e., it is a
-expression). An interpretive derivation is a sequence. When, being
the lattice associated to, the state is called a fuzzy computed answer (f.c.a.) for that derivation.
Example 2.7 If we complete the previous derivation of Example 2.4 by applying 3 interpretive steps in order to obtain the final f.c.a., we generate the interpretive derivation shown in Figure 1.
2.3. Interpretive Steps and Cost Measures
A classical, simple way for estimating the computational cost required to built a derivation, consists in counting the number of computational steps performed on it. So, given a derivation , we define its:
• operational cost, , as the number of admissible steps performed in.
• interpretive cost, , as the number of interpretive steps done in.
Note that the operational and interpretive costs of derivation performed in Figure 1 are and, respectively. Intuitively, informs us about the number of atoms exploited along a derivation. Similarly, seems to estimate the number of connectives evaluated in a derivation. However, this last statement is not completely true: only takes into account those connectives appearing in the bodies of program rules which are replicated on states of the derivation, but no those connectives recursively nested in the definition of other connectives. The following example highlights this fact.
Example 2.8 A simplified version of rule, whose body only contains an aggregator symbol is:
where is defined as. Note that has exactly the same meaning (interpretation) than, although different syntax. In fact, both ones have the same sequence of atoms in their head and bodies. The differences are regarding the set of connectives which explicitly appear in their bodies since in we have moved and from the body of the rule (see) to the connective definition of. Now, we use rule instead of for generating the following derivation which returns exactly the same f.c.a than:
Note that, since we have exploited the same atoms with the same rules (except for the first steps performed with rules and, respectively) in both derivations, then. However, although connectives and have been evaluated in both derivations, in such evaluations have not been explicitly counted as interpretive steps, and consequently they have not been added to increase the interpretive cost measure. This unrealistic situation is reflected by the abnormal result. It is important to note that must not be considered an optimized version of, even when the wrong measure seems to indicate the contrary.
This problem was initially pointed out in [15] , where a preliminary solution was proposed by assigning weights to connectives in concordance with the set of primitive operators involved in the definition of the proper connective as well as those ones recursively contained in the definitions of connectives invoked from. Moreover, in [16] we improved the previous notion of “connective weight” by also taken into account the number of recursive calls to fuzzy connectives (directly or indirectly) performed in the definition of.
A rather different way for facing the same problem is presented in [17] , where instead on connective weights, we opt for the more “visual” method we have just implemented into, based on the subsequent redefinition of the behaviour of the interpretive phase.
Definition 2.9 (Small Interpretive Step) Let be a program, a goal and a substitution. Assume that the (non interpreted yet) -expression occurs in, where is just a primitive operator or a connective defined in the lattice associated to, and are elements of. We formalize the notion of small interpretive computation as a state transition system, whose transition relation
is the smallest relation satisfying the following small interpretive rules (where we always consider that is the selected -expression in):
1), if is a connective defined as
and is obtained from the -expression by replacing each variable (formal parameter) by its corresponding value (actual parameter), , that is,.
2), if is a primitive operator such that, once evaluated with parameters, produces the result.
From now on, we shall use the symbols and to distinguish between computation steps performed by applying one of the specific “small interpretive” rules. Moreover, when we use the expression interpretive derivation, we refer to a sequence of small interpretive steps (according to the previous definition) instead of a sequence of interpretive steps (regarding Definition 2.5). Note that this fact supposes too a slight revision of Definition 2.6 which does not affect the essence of the notion of fuzzy computed answer: the repeated application of both kinds of small interpretive steps on a given state only affects to the length of the corresponding derivations, but both ones lead to the same final states (containing the corresponding fuzzy computed answers).
Example 2.10 Recalling again the a.c.a. obtained in Example 2.4, we can reach the final fuzzy computed answer (achieved in Example 2.7 by means of interpretive steps) by generating now the following interpretive derivation based on “small interpretive steps” (Definition 2.9):
Going back now to Example 2.8, we can rebuild the interpretive phase of Derivation in terms of small interpretive steps, thus generating the following interpretive derivation. Firstly, by applying a step on the -expression, it becomes, and from here, the interpretive derivation evolves exactly in the same way as derivation we have just done above.
At this moment, it is mandatory to meditate on cost measures regarding derivations and. First of all, note that the operational cost of all them coincides, which is quite natural. However, whereas, we have now that. This apparent contradiction might confuse us when trying to decide which program rule (or) is “better”. The use of Definition 2.9 in derivations and is the key point to solve our problem, as we are going to see. In Example 2.8 we justified that by simply counting the number of interpretive steps performed in Definition 2.5 might produce abnormal results, since the evaluation of connectives with different complexities were (wrongly) measured with the same computational cost. Fortunately, the notion of small interpretive step makes visible in the proper derivation all the connectives and primitive operators appearing in the (possibly recursively nested) definitions of any connective appearing in any derivation state. As we have seen, in we have expanded in three steps the definitions of three connectives, i.e., and twice, and we have applied five steps to solve five primitive operators, that is, , , and (three times). The same computational effort as been performed in, but also one more step was applied to accomplish with the expansion of the extra connective. This justifies why and contradicts the wrong measures of Example 2.8: the interpretive effort developed in derivations and (both using the program rule), is slightly lower than the one performed in derivations and (which used rule), and not the contrary.
The accuracy of our new way for measuring and performing interpretive computations seems to be crucial when comparing the execution behaviour of programs obtained by transformation techniques such as the fold/ unfold framework we describe in [18] [19] . In this sense, instead of measuring the absolute cost of derivations performed in a program, we are more interested in the relative gains/lost of efficiency produced on transformed programs. For instance, by applying the so-called “aggregation operation” described in [19] we can transform rule into and, in order to proceed with alternative transformations (fold,unfold, etc.) if the resulting program degenerates w.r.t. the original one (as occurs in this case), we need an appropriate cost measure as the one proposed here to help us for taken decisions. This fact has capital importance for discovering drastic situations which can appear in degenerated transformation sequences such as the generation of highly nested definitions of aggregators. For instance, assume the following sequence of connective definitions: and finally. When trying to solve two expression of the form and, cost measures based on number of interpretive steps ([14] ) and weights of interpretive steps ([15] ) would assign 1 unit of interpretive cost to both derivations. Fortunately, our new approach is able to clearly distinguish between both cases, since the number of
steps performed in each one is rather different (100 and 1, respectively).
3. The “Fuzzy LOgic Programming Environment for Research”
As shown in the web page http://dectau.uclm.es/floper/ designed in our research group for freely accessing -see also references [20] -[25] -during the last years we have been involved in the development of this tool for aliving MALP programs (which can be easily loaded into the system by means of plain-text files with extension “.fpl”). For example, our previous illustrative program included into file “P1.fpl”, contains the following rules where, note for instance that the fuzzy connectives for implication, disjunction and conjunction symbols belonging to the product logic are respectively referred as “prod”, “|prod” and “&prod”:
In order to simplify the task of coding fuzzy logic programs, our tool is able to parse MALP rules with “syntactic sugar” trying to look as conservative extensions of Prolog clauses:
• Since the weight of a rule can be omitted if it coincides with the element of the corresponding lattice then, a rule like “p(X) with 1.” can be simply expressed as “p(X).”.
• When the concrete implication symbol connecting the body and head of a given a rule be irrelevant, we can write “<-“ instead of using a particular label “<”, since will choose an arbitrary implication (i.e., the last one found when textually exploring the lattice stored into the system) for this rule. So, “p(X) < -q(X).” is a valid rule.
• Something similar occurs (but even without the need of “-”) for connectives used in the bodies of program rules, thus implying that “p(X) <- q(X) & r(X).” is a valid rule for any conjunction operator. At this point, it is important to remark that the last rule in Figure 2 (we assume that the connectives belonging to the product logic are the last ones defined into the lattice stored into ) can be highly simplified to the following shape: “c(X) <-(h(X)|e(X)) & y(X).”.
• We can also include Prolog clauses between “$$” symbols, for instance “$p(X):-!,var(X).$”, and moreover, it is possible too to insert pure Prolog code between “{}” symbols into the body of a fuzzy logic MALP rule, as occurs with “p([H|T]) < -{Y is H + 1} q(Y) & p(T).”
Once the application is loaded inside any standard Prolog interpreter (like SWI or Sicstus-which is our case, by using v3.12.5-), it shows the menu shown in Figure 3. The parser has been implemented by using the classical DCG’s ( Definite Clause Grammars) resource of the Prolog language, since it is a convenient notation for expressing grammar rules. Via the “parse” option, it is possible to load a “.fpl” file for which generates two different Prolog representations of the fuzzy code, as we will describe in sub-Sections 3.1 and 3.2. Such code will cohabit with the set of clauses introduced by the user (together the Prolog -based definition of the
Figure 2. MALP program P1 loaded into.
Figure 3. Running into any standard Prolog platform.
associated lattice that we will describe in sub-Section 3.3) via the “load” option for consulting pure Prolog files (“.pl”). The system is equipped too with choices for saving and listing such rules as well as the “clean” option for removing all clauses from the database.
The remaining menus are useful for executing goals and displaying evaluation trees, as well as for managing multi-adjoint lattices, as we are going to explain in what follows helped by the graphical interface recently developed for and shown in Figure 4, which allows the comfortable use of “projects” in order to manage files with the following different purposes:
• several “.fpl” files can contain the set of MALP rules implementing a single MALP program• the set of clauses modeling its (unique) associated multi-adjoint lattice must be included into a file with obvious extension “.pl”,
Figure 4. The graphical interface of.
• additional Prolog code (for representing linguistic modifiers/variables, etc) can be also attached in different “.pl” files and
• several “script” files could be useful for executing in one go more than one of the set of commands we are going to explain in this section, as illustrated in the following example:
ord: intro.
arg: c(X).
ord: ismode.
arg: s.
ord: tree.
ord: leaves.
ord: run.
3.1. Running Programs
In order to fully execute a goal, employs the high-level representation of the MALP program compiled via the “parse” option. The key point of this Prolog code is to extend each atom of the program with an extra argument, called truth variable, of the form TVi, which is intended to contain the truth degree obtained after the subsequent evaluation of the atom. In the case of a fact, the extra argument obviously contains its weight. For instance, “p(X) with 0.5” is simply translated into the Prolog fact “p(X, 0.5)”.
Fuzzy connectives are represented as predicates defined in the lattice associated to the program. For instance, the role of “&godel” is played by the Prolog predicate “and_godel”. Since the fuzzy connective “&godel” is a binary operation, then its associated predicate “and_godel” has arity three: two parameters plus the result, returned in the third argument TV.
When compiling MALP rules, the last atom called in the body of the translated clause is the adjoint conjunction, which is intended to combine the truth degree of the body and the weight of the rule, in order to propagate the final truth degree to the head. For instance, given a MALP rule like “p(X) < prod q(X,Y) & godel r(Y) with 0.8”, the resulting translated Prolog clause would look like “p(X,_TV0):- q(X,Y,_TV1), r(Y,_TV2), and_godel (_TV1,_TV2,_TV3), and_prod(0.8,_TV3,_TV0)”.
In order to execute a fuzzy program stored in a “.fpl” file, needs firstly to load and compile it by using the “parse” option. Internally, while analyzes the content of the file (following the DCG specification of the MALP syntax) it also generates two different Prolog representations of the fuzzy code: the high level representation coincides with a set of executable Prolog clauses as we have just described, while the low level representation allows to draw execution trees as we will see in the next subsection.
Here we have an example of using the “parse” option, where note that lists the content of any previously loaded “.pl” file (none in our case), the parsed MALP program and the generated Prolog code.
>> parse.
File to parse: ‘P1.fpl’.
No loaded files.
ORIGINAL FUZZY-PROLOG CODE:
y(peter) with 0.4.
y(mary) with 0.8.
h(peter) with 0.9.
h(mary) with 0.3.
e(peter) with 0.5.
e(mary) with 0.95.
c(X) < prod (h(X)|prod e(X)) &prod y(X) with 1.
GENERATED PROLOG CODE:
y(peter,0.4).
y(mary,0.8).
h(peter,0.9).
h(mary,0.3).
e(peter,0.5).
e(mary,0.95).
c(X,TV0):- h(X,_TV1), e(X,_TV2), lat:or_prod(_TV1,_TV2,_TV3)y(X,_TV4), lat: and_prod(_TV3,_TV4,_TV5)lat: and_prod(1,_TV5,TV0).
While parsing, creates a file tmp_fuzzy-prolog.pl to allocate the generated Prolog code, in order to allow the possibility of saving it afterwards into a new file by using the “save” option.
One important feature is that translated connectives (like “lat:and_prod/3”) are prefixed by “lat:”, which means that the Prolog interpreter will search their definitions in the “lat” module, a different name-space designed to avoid name collisions. The resulting Prolog code can be executed in any Prolog engine, with the only requirement that the associated lattice must be loaded in the corresponding module. This can be easily achieved with the following two goals:
?- lat:consult(lattice.pl).
?- consult(program.fpl).
Moreover, goals are introduced in by choosing the ‘intro” option and they suffer a very similar translation process to program rules. So, it is easy to see that a fuzzy goal like “y(X) &godel h(peter)”, is translated into the pure Prolog goal “y(X, _TV1), h(peter, _TV2), and_godel(_TV1, _TV2, Truth_degree)” (note that the last truth degree variable is not anonymous now) for which the Prolog interpreter returns the two desired fuzzy computed answers after selecting the “run” option (see Figure 4):
[Truth_degree = 0.4, X = peter]
[Truth_degree = 0.8, X = mary]
3.2. Execution Trees
Apart from the compilation method to Prolog code commented before, we have conceived a new low-level representation for the fuzzy code which is useful for building execution trees with any level of depth and offering too debugging (tracing) capabilities. For instance, after parsing the last rule of our program, we obtain the following expression (which is “asserted” into the database of the interpreter as a Prolog fact, but it is never executed directly, in contrast with the previous Prolog-based, high-level representation of the fuzzy code) whose components have obvious meanings:
rule(7head(atom(pred(c,1), [var('X')]))impl(prod)body(and(prod, 2, [or(prod, 2, [atom(pred(h,1),[var('X')])atom(pred(e,1),[var('X')])])atom(pred(y,1), [var('X')])]))td(1)).
is equipped with three options related with tracing tasks. Option “tree” draws the execution tree (which collects a different derivation from the root to each leaf) of a goal w.r.t. a program. Option “depth” fixes the maximum length allowed for their branches (initially 3). And, finally, option “ismode” fixes the detail level of the interpretive phase associated to each derivation in the tree.
So, let us consider again the MALP program of our running example. For goal “y(X) &godel h(peter)”, displays the tree showed in Figure 5. In this screen-shot, we find two representations of the same tree: the middle-up window shows the proper graphic which is easy to understand and manipulate (by moving nodes, showing only skeletons of trees, etc.), while the marked text in the middle-down window represents the same tree in plain text. In this last case, each line contains a state (composed by the corresponding goal and substitution) preceded by the number of the program rule used by the admissible step leading to it (root nodes and nodes obtained via are always labeled with the virtual, non existing rule R0), and nodes belonging to the same branch appear in different lines appropriately indented to help the readability of the tree (which only contain two different branches in our case). Generated trees can be saved in “.jpg”, “.txt” and “xml” formats.
Figure 5. drawing an execution tree.
Moreover, allows the user to choose the level of information given by the interpretive phase in the execution tree through option “ismode”. We can choose among the following three modes:
• large: This mode omits the entire interpretive phase, offering only the final leaf (if exists) of each branch.
• medium: Performs classical interpretive steps according Definition 2.5, in order to evaluate each expression of the goal till finding the final solution.
• small: This mode applies our improved notion of small interpretive step provided in Definition 2.9, which is very useful for visualizing the more or less complexity (distinguishing between connective calls and primitive operators evaluation) of connectives exploited during the interpretive phase. Figure 6 shows that the shorter the step is, the larger tree is generated.
To finish this block, we are going to illustrate now with a very simple example that the new options are crucial when the “run” choice fails: remember that this last option is based on the generation of pure logic SLDderivations which might fall in loop or directly fail when finding non defined atoms, in contrast with the traces (based on finite, non-failed, admissible/interpretive derivations) that the “tree” option displays. So, consider the following MALP program:
where the first and last rules indicate that a goal like “p(X)” admits two solutions, but the second rule would be responsible of introducing an infinite branch between the leaves associated to both fuzzy computed answers in the corresponding execution tree. Moreover, if we plan to run a more complex goal like “q(X) @aver p(X)” (where, obviously, the used connective refers to the average aggregator), we find a second problem related now with an undefined atom. In contrast with Prolog , in our fuzzy setting the evaluation of “q(X)” doesn’t fail, since
proceeds with an step according Definition 2.2, and hence, it is possible to find the two desired fuzzy computed answers for that goal, as shown in the execution tree of Figure 7. By choosing option “leaves”, the system displays the content of the two fully evaluated leaves “<0.4,{X/a}>” and “<0.3,{X/b}>”, as desired.
As we have seen, the generation of traces based on execution trees, contribute to increase the power of by providing debugging capabilities which allow us to discover solutions for queries even when the pure Prolog compilation-execution process becomes insufficient.
3.3. Managing Lattices
We have conceived a very easy way to model lattices of truth degrees for being included into the tool. All relevant components of each lattice can be encapsulated inside a Prolog file which must necessarily contain the definitions of a minimal set of predicates defining the set of valid elements (including special mentions to the “top” and “bottom” ones), the full or partial ordering established among them, as well as the repertoire of fuzzy connectives which can be used for their subsequent manipulation. In order to simplify our explanation, assume that file “bool.pl” refers to the simplest notion of (a binary) adjoint lattice, thus implementing the following set of predicates:
• member/1 which is satisfied when being called with a parameter representing a valid truth degree. In the case of finite lattices, it is also recommended to implement members/1 which returns in one go a list containing the whole set of truth degrees. For instance, in the Boolean case, both predicates can be simply modeled by the Prolog facts: member(0)., member(1). and members ([0,1]).
• bot/1 and top/1 obviously answer with the top and bottom element of the lattice, respectively. Both are implemented into “bool.pl” as bot(0). and top(1).
• leq/2 models the ordering relation among all the possible pairs of truth degrees, and obviously it is only satisfied when it is invoked with two elements verifying that the first parameter is equal or smaller than the second one. So, in our example it suffices with including into “bool.pl” the facts: leq(0,X). and leq(X, 1).
• Finally, given some fuzzy connectives of the form (conjunction), (disjunction) or (aggregation) with arities, and respectively, we must provide clauses defining the connective predicates “and_ label1/(n1 + 1)”, “or_ label2 /(n2 + 1)” and “agr_ label3/(n3 + 1)”, where the extra argument
Figure 6. Comparing different modes of performing the interpretive phase.
Figure 7. Tree with an infinite branch and a; step.
of each predicate is intended to contain the result achieved after the evaluation of the proper connective. For instance, in the Boolean case, the following two facts model in a very easy way the behaviour of the classical conjunction operation: and_bool(0,_,0). and_bool(1,X,X).
The reader can easily check that the use of lattice “bool.pl” when working with MALP programs whose rules have the form “”, being and typical atoms1, successfully mimics the behaviour of classical Prolog programs where clauses accomplish with the shape “”. As a novelty in the fuzzy setting, when evaluating goals according to the procedural semantics described in Section 2.1, each output will contain the corresponding substitution (i.e., the crisp notion of computed answer obtained by means of classical SLD-resolution in Prolog ) together with the maximum truth degree.
On the other hand and following the Prolog style regulated by the previous guidelines, in file “num.pl” we have included the clauses shown in Figure 8. Here, we have modeled the more flexible lattice (that we will mainly use in our examples, beyond the boolean case) which enables the possibility of working with truth degrees in the infinite space (note that this condition disables the implementation of the consulting predicate “members/1”) of real numbers between 0 and 1, allowing too the possibility of using conjunction and disjunction operators recasted from the three typical fuzzy logics described before (i.e., the ukasiewicz, Gödel and product logics), as well as a useful description for the hybrid aggregator.
Note also that we have included definitions for auxiliary predicates, whose names always begin with prefix “pri_”. All of them are intended to describe primitive/arithmetic operators (in our case and) in a Prolog style, for being appropriately called from the bodies of clauses defining predicates with higher levels of expressiveness (this is the case for instance, of the three kinds of fuzzy connectives we are considering: conjunctions, disjunctions and agreggations).
Since till now we have considered two classical, fully ordered lattices (with a finite and infinite number of elements, collected in files “bool.pl” and “num.pl”, respectively), we wish now to introduce a different case coping with a very simple lattice where not always any pair of truth degrees are comparable. So, consider the partially ordered multi-adjoint lattice in Figure 9 for which the conjunction and implication connectives based on the Gödel logic described in Section 2.1 conform an adjoint pair but with the particularity now that, in the general case, the Gödel’s conjunction must be expressed as, where it is important to note
Figure 8. Multi-adjoint lattice modeling truth degrees in the real interval [0,1] (“num.pl”).
Figure 9. Partially ordered lattice with four elements.
that we must replace the use of “min” by “inf” in the connective definition. To this end, observe in the Prolog code accompanying Figure 9 that we have introduced five clauses defining the new primitive operator “pri_inf/3” which is intended to return the infimum of two elements. Related with this fact, we must point out the following aspects:
• Note that since truth degrees and -or their corresponding representations as Prolog terms “alpha” and “beta” used for instance in the definition(s) of “members(s)/1”-are not comparable, any call to “leq (alpha,beta)” or “leq(beta,alpha)” will always fail.
• However, goals “pri_inf(alpha,beta,X)” and “pri_inf(beta,alpha,X)”, instead of failing, successfully produces the desired result “X = bottom”.
• Note anyway that the implementation of the “pri_inf/1” predicate is mandatory for coding the general definition of “and_godel/3”.
As a final example, we can also define the so called Borel algebra based on the union of intervals (where for instance is the union of intervals between 0 and 1 [8] [26] ) as a Prolog program for being used into as follows:
• A member of this algebra is a list of pairs representing disjoined intervals.
• The top element is the point 1 (interval from 1 to 1), and the bottom one is the point 0 (interval from 0 to 0).
• A union of intervals, , is less or equal than other union of intervals if for each, there exists another interval, such that.
member([i(X,Y)]):- number(X), number(Y), X =< Y.
member([i(X,Y), i(Z,T)|U]):- number(X), number(Y), number(Z)X =< Y, Y < Z, member ([i(Z,T)|U]).
bot([i(0,0)]). top ([i(1,1)]).
leq([X1, X2|X], Y):- existsGreater(X1,Y), leq([X2|X],Y).
leq([X1], Y) existsGreater (X1,Y).
existsGreater(i(Xb, Xt), [i(Yb,Yt)|Y]):- Yb =< Xb, Xt =< Yt,!.
existsGreater(X, [_|Y]):- existsGreater(X,Y).
3.4. Linguistic Modifiers and Linguistic Variables
Another interesting feature of is its ability for managing linguistic modifiers and linguistic variables in a very easy way. A linguistic modifier can be seen as an aggregator such that, when applied to a fuzzy expression, it alters its final truth degree. Some examples of well known modifiers are “very” and “roughly”, where the first one tends to return a lower truth degree, and the second one, a higher truth degree. Since the concept of modifier is dependent of a concrete lattice, its definition should appear inside the Prolog file containing the proper multi-adjoint lattice loaded into. For instance, in the typical lattice used in previous examples, we could define some modifiers by means of the following usual formulae (see Figure 10):
With these modifiers, now we could update the program of Figure 1 to increase the difficulty for obtaining a credit in crisis times. The only rule to be modified is the seventh one, whose new shape could look like:. Linguistic modifiers increase the expresiveness of the fuzzy language and as said before, they have to be defined as part of the lattice associated to the MALP program in the current project.
Figure 10. Linguistic modifiers.
On the other hand, linguistic variables allow us to represent linguistic symbols defined by means of fuzzy sets. A linguistic variable is characterized by a tuple, where is the name of the variable, the set of linguistic symbols or terms of, the universe where is defined, represents a syntactic rule to generate linguistic terms, and is a semantic rule for assigning to each linguistic symbol its fuzzy set. For instance, we can represent the linguistic variable distance, with values defined over the universe in kilometers, as shown in Figure 11. We can implement this variable into a Prolog file defining a fuzzy predicate for each symbol. The arguments are an input variable (D) giving the crisp distance, and an output variable (TV) returning the degree of membership of the input variable to the fuzzy set. Then, it is possible to load this Prolog program into the current project of , in order to use such definitions in the corresponding MALP program.
near(D,1):- D =< 100.
near(D,TV):- 100 < X, X =< 500, TV is (500-X)/400.
near(D,0):- 500D.
far_away(D,0):- D =< 100.
far_away(D,TV):- 100 < X, X =< 500, TV is (X-100)/400.
far_away(D,1):- 500 < D.
In the following example, we design a touristic application to compute the best destination for vacations. The database includes some cities and relevant information relating them (kind of weather, good sights, distance from our hometown). It is clear that some of this information has a very fuzzy taste, so the choice of a fuzzy language is desirable. We can fuzzify the crisp distance using the linguistic variable defined above as follows.
nice_weather(madrid) with 0.8.
nice_weather(istanbul) with 0.7.
nice_weather(moscow) with 0.2.
nice_weather(sydney) with 0.5.
many_sights(madrid) with 0.6.
many_sights(istanbul) with 0.7.
many_sights(moscow) with 0.2.
many_sights(sydney) with 0.6.
crisp_distance(madrid, 250).
crisp_distance(istanbul, 3700).
crisp_distance(moscow, 4200).
crisp_distance(sydney, 18000).
good_destination(X) <- @roughly(crisp_distance(X,D) & near(D))
@aver
@very(nice_weather(X) & many_sights(X)).
Note that the use too of linguistic modifiers in the last MALP rule means that we give little importance to the distance since we are more interested on weather and sights. Now, for goal good_destination(X), the execution
Figure 11. Linguistic variable “distance” with terms “near” and “far away”.
of the previous program into returns the following results (meaning that the best destination, according to our specification, is Madrid, followed by far by Istanbul and Sydney, while Moscow scores 0):
[Truth_degree = 0.0, X = moscow]
[Truth_degree = 0.005000000000000009, X = sydney]
[Truth_degree = 0.07999999999999996, X = istanbul]
[Truth_degree = 0.5245698525097306, X = madrid]
Note that, with the current definition of fuzzy predicates ‘near’ and ‘far_away’, no matter how we reduce the importance of distance since, if it is over 500 kilometers, it will always be near with 0 truth degree, and if it is under 100 kilometers, it will be far with 0 truth degree. If our perception of distance changes, these notions will become useless. To fix that, we can define them with non-linear rules like the following ones, which show that is flexible enough to deal with fuzzy predicates defined (in Prolog ) by means of non-linear arithmetic expressions (see Figure 12):
near(D,TV):- TV is 250/(D + 250).
far(D,TV):-TV is 1 - 250/(D + 250).
4. Extending Lattices and Declarative Traces
This section presents different methods to gain expressiveness when designing a MALP program by manipulating its associated lattice. The main technique consists on agglutinating several lattices in order to obtain the Cartesian product of them, which is also a multi-adjoint lattice [24] . Once this is done, a new functionality emerges for obtaining declarative traces (when evaluating goals) at a very low cost.
Theorem 4.1 If are a finite number of multi-adjoint lattices, then its Cartesian product is also a multi-adjoint lattice.
In order to simplify our explanation, but without lost of generality, we only consider two multi-adjoint lattices and, each one equipped with just a single adjoint pair. Then, has lattice structure with an ordering relation induced in the product from and as follows
Moreover, being, , and, we have that and which implies that the Cartesian product is a bounded lattice if both and are also bounded lattices. Analogously, is a complete lattice if and verify too the same property. Finally, from the adjoint pairs and in and, respectively, it is possible to define the following connectives in:
Figure 12. Linguistic variable “distance” with flexible versions of “near” and “far away”.
for which it is easy to justify that they conform an adjoint pair in (thus satisfying, in particular, the adjoint property). In a similar way, it is also possible to define new connectives (conjunctions, disjunctions and aggregators) in the Cartesian product from the corresponding pairs of operators defined in and.
is able to deal with Cartesian products of multi-adjoint lattices by acting on the “member/1” predicate, which accept as argument any object which belong to a lattice. Some examples of simple “member/1” definitions are:
• member(X):- number(X), X =< 1, X >= 0: [0,1] interval
• member([X|L]): lists
• member(info(X,Y)): pairs The very intuitive way to obtain Cartesian product of lattices is to use Prolog functions with arity 2 (indeed, the cartesian product of lattices can be represented using functions with arity). In order to implement a cartesian product of lattices in a Prolog file, we define “member/1” predicate whose parameter is a term headed with a function symbol, for instance: member(f(X,Y)):- check1(X), check2(Y). Of course, predicates “leq/2”, “top/1”, “bot/1” and connectives have to be defined following the same criterium in order to implement the concrete Cartesian product of lattices.
Before showing an example of Cartesian product modeled in , let us consider again the so called domain of weight values used in the QLP ( Qualified Logic Programming framework of [6] [7] [27] , whose elements are intended to represent proof costs, measured as the weighted depth of proof trees. As explained in Section 2, can be seen as lattice, where is the reverse of the usual numerical ordering (with for any) and thus, the bottom elements is and the top element is 0 (and not vice versa). Note that in this lattice the arithmetic operation “+” plays the role of a conjunction (it is easy to prove that in this setting such definition of verifies the properties required by t-norms [28] ). Moreover, we can obtain the residual implication of the “+” t-norm, defined as, which in this particular case acquires the following shape:
So, the reader can easily check that conforms an adjoint pair in, thus accomplishing with Definition 2.1 in Section 2, which implies that is in fact a multi-adjoint lattice. A valid implementation of lattice presents the following definitions:
member(X):- number(X). member(infty).
leq(infty,X). leq(X,Y):- X >= Y.
top(0). bot(infty). and_plus(X,infty,infty).
and_plus(infty, X, infty). and_plus(X,Y,Z):- Z is X + Y.
In order to associate the lattice to our program, we have to change the weights of each rule by valid truth degrees belonging to the new lattice. For instance, rule “” would be rewritten as “” (the underlying idea is that “the use of each program rule in a derivation implies the application of one admissible step”), resulting in a new program,. By using the “lat” option of, we can built a project which associates lattice to program and now, for goal “”, we can generate an admissible derivation similar to the one seen in Figure 1, but ending now with
. Since:, the final fuzzy computed answer or f.c.a. indicates that goal “” holds when is peter, as proved after applying 4 admissible steps.
On the other hand, since we have said that is the multi-adjoint lattice based on real numbers in the unit interval used along this paper (which is equipped with three adjoint pairs modeling implication and conjunction symbols collected from the ukasiewicz logic, Gödel intuitionistic logic and product logic) then, in the Cartesian product we will find the top and bottom elements and, respectively, as well as the following definitions of conjunction operations (among other connectives) whose names are mirroring to extensions of the product logic and ukasiewicz logic:
Moreover, we can also conceive a more powerful lattice expressed as the Cartesian product of (see Figure 8) and. Now, each element includes two components, coping with truth degrees and cost measures. In order to be loaded into, we must define in Prolog the new lattice, whose elements could be expressed as data terms of the form “info(Fuzzy_Truth_Degree, Cost_Number_Steps)”. Some of the required predicates are:
member(info(X,W)):- number(X), 0 =< X, X =< 1,(W = infty, !; number(W),1 =< W).
leq(info(X1,W1),info(X2,W2)):-X1 =< X2, (W1=infty,!; number(W2), W2 =< W1).
bot(info(0,infty)). top(info(1,1)).
and_prod(info(X,W1),info(Y,W2),info(Z,W3)):- pri_prod(X,Y,Z), pri_add(W1, W2, W3).
pri_add(infty,_,infty). pri_add(_,infty,infty).
pri_add(X,Y,Z):- number(X), number(Y), Z is X + Y.
Finally, if the weights assigned to the rules of our example are “info(0.4,1)” for, “info(0.8,1)” for, “info(0.9,1)” for and so on, then we would obtain the desired f.c.a. for goal “”, with the obvious meaning that we need 4 admissible steps to prove that the query is true at a 38% degree when is “peter”.
One step beyond, we will also see that if instead of the number of computational steps, we are interested in knowing more detailed data about the set of program rules and connective definitions evaluated for obtaining each solution then, instead of it will be mandatory to use a new lattice based on strings or labels (i.e., sequences of characters) for generating the Cartesian product. In [25] we show not only that is a complete multi-adjoint lattice, but also that the concatenation of strings, usually called “append” in many programming languages, plays the role of a conjunction connective in such lattice.
In order to be loaded into, we need to define again the new lattice as a Prolog program, whose elements will be terms of the form “info(Fuzzy_Truth_Degree, Label)” as shown in Figure 13 (we only list some representative clauses).
Here, we see that when implementing for instance the conjunction operator of the Product logic, in the second component of our extended notion of “truth degree”, we have appended the labels of its arguments with label ‘&PROD.’ (see clauses defining and_prod, pri_app and append). Of course, in the fuzzy program to be run, we must also take into account the use of labels associated to the program rules, as occurs with the following example:
p(X) < prod & godel(q(X), @aver2(r(X), s(X))) with info (0.9,'RULE1.').
q(a) with info (0.8,'RULE2.').
r(X) with info (0.7,'RULE3.').
s(X) with info (0.5,'RULE4.').
where we have used in the first rule aggregator “@aver2” (intended to compute the average between the results achieved by applying two different disjunction operations on the parameters) defined in Prolog as:
agr_aver2(X,Y,info(Za,Zb)):- or_godel(X,Y,Z1),or_luka(X,Y,Z2)agr_aver(Z1,Z2,info(Za,Zc))pri_app(Zc,'@AVER2.',Zb).
Figure 13. Multi-adjoint lattice modeling truth degrees with labels.
Now, the reader can easily test that, after executing goal “p(X)”, we obtain the following fuzzy computed answer which includes the desired declarative trace containing the sequence of program-rules and connectivecalls (mirroring and steps, according definitions 2.2 and 2.9, respectively) evaluated till finding the final solution:
>> run.
[Truth_degree = info(0.72, RULE1. RULE2.RULE3.RULE4.
@AVER2.|GODEL.|LUKA.
@AVER.& GODEL.&PROD.), X = a]
With a very little extra effort, we can extend the previous lattice to have into account also the exploited primitive operators during the interpretive phase, thus simulating steps (see again Definition 2.9). We simply need to include a label in the Prolog definition of each primitive operator in order to identify it (for instance, “#PROD” refers to the product primitive operator).
and_prod (info(X1,X2), info(Y1,Y2), info(Z1,Z2)):pri_prod (X1,Y1,Z1,DatPROD), pri_app(X2,Y2, Dat1)pri_app (Dat1, ‘&PROD.’, Dat2), pri_app(Dat2, DatPROD, Z2).
pri_prod (X, Y, Z, ‘#PROD.’):- Z is X * Y.
As shown in Figure 14, the result of executing again goal “p(X)” is:
>> run.
[Truth_degree=info(0.72, RULE1.RULE2.RULE3.RULE4.
@AVER2.|GODEL.#MAX.|LUKA.
#ADD.#MIN.@AVER.#ADD.#DIV.
&GODEL.#MIN.&PROD.#PROD.), X = a]
In this fuzzy computed answer we obtain both the truth value (0.72) and substitution associated to our goal, but also the sequence of program rules exploited when applying admissible steps as well as the proper fuzzy connectives evaluated during the interpretive phase, also detailing the set of primitive operators (of the form #label) they call.
Figure 14. Obtaining declarative traces on fuzzy computed answers.
To finish this section, we wish to mention the real-world application we have recently developed by using the tool, where the key point is the use again of a lattice based on the Cartesian product of two previous lattices, but whose second component, instead of strings, considers lists. In [29] -[31] , we present both an interpreter and a debugger for a fuzzy variant of the XPath language, which admits new commands with a fuzzy taste for flexibly accessing XML documents, automatically generating alternative queries to retrieve more information, etc. The application can be freely downloaded and even tested on-line (see Figure 15) through http://dectau.uclm.es/fuzzyXPath/. Moreover, in [32] [33] we present our last applications recently developed with which connect with the challenging fields of SAT/SMT and cloud computing, respectively.
5. Conclusion
In the recent past, several fuzzy extensions of the popular pure logic language Prolog have been designed in order to incorporate on its core new expressive resources for dealing with uncertainty in a natural way. However, real tools for putting in practice the power of such languages are not always available to a wide audience. To reduce this gap, the experience acquired in our research group regarding the design of techniques and methods based on fuzzy logic in close relationship with the so-called multi-adjoint logic programming approach, has motivated our interest for putting in practice all our developments around the design of the environment, which offers comfortable resources for programmers trained in declarative languages. In a first stage, we have showed that our tool is able to execute MALP programs via a “transparent compilation process” to standard Prolog code which, to the best of our knowledge, constitutes the first initiative to put in practice the integral development of this kind of fuzzy programs. Going on deeper, we have next proposed a second compilation way which produces a low-level representation of the fuzzy code, thus enabling the possibility of drawing “derivation trees” (which offer too debugging/tracing tasks) and opening the door to new program manipulation techniques such as fold/unfold-based program optimization, program specialization by partial evaluation, etc... in which we are working nowadays after being formally matured in our research group. Moreover, our tool offers the possibility of managing in a single pack, i.e. “project”, fuzzy programs with its associated multi-adjoint lattices modeled in Prolog, together with additional clauses and scripts helping to manage and increase the power of this programming tool. Our philosophy is to friendly connect this fuzzy
Figure 15. Screen-shot of an on-line work session with the XPath debugger.
framework with Prolog programmers since our system (which can be easily installed on top of many Prolog platforms) translates the fuzzy code to classical clauses, admits the definition of sophisticated lattices for modeling advanced notions of truth degrees collecting proof traces on fuzzy computed answers and simplifies the implementation of modern, real-world applications where fuzzy logic plays an important role. As an example, our system has recently served us for developing a real-world application devoted to the flexible management of XML documents by means of a fuzzy variant of the popular XPath language. We are nowadays introducing new thresholding techniques inspired by [34] [35] for addressing in our framework the well-known “top-k ranking problem” (i.e. determining the top k answers to a query without computing the-usually wider, possibly infinitewhole set of solutions [36] -[47] ).
Acknowledgements
This work was supported by the EU (FEDER), and the Spanish MINECO Ministry (Ministerio de Economía y Competitividad) under grant TIN2013-45732-C4-2-P.
References
- Lloyd, J. (1987) Foundations of Logic Programming. 2nd Edition, Springer-Verlag, Berlin.
- Lee, R. (1972) Fuzzy Logic and the Resolution Principle. Journal of the ACM, 19, 119-129. http://dx.doi.org/10.1145/321679.321688
- Ishizuka, M. and Kanai, N. (1985) Prolog-ELF Incorporating Fuzzy Logic. Proceedings of the 9th International Joint Conference on Artificial Intelligence, IJCAI’85, Los Angeles, 18-23 August 1985, 701-703.
- Li, D. and Liu, D. (1990) A Fuzzy Prolog Database System. John Wiley & Sons, Inc., Hoboken.
- Baldwin, J.F., Martin, T.P., and Pilsworth, B.W. (1995) Fril-Fuzzy and Evidential Reasoning in Artificial Intelligence. ohn Wiley & Sons, Inc., Hoboken.
- Rodrguez-Artalejo, M. and Romero-Daz, C. (2008) Quantitative Logic Programming Revisited. In: Garrigue, J. and Hermenegildo, M., Eds., Functional and Logic Programming (FLOPS’08), Springer, Berlin, 272-288.
- Caballero, R., Rodrguez, M., and Romero, C.A. (2010) A Transformation-Based Implementation for CLP with Qualification and Proximity. CoRR, abs/1009.1976.
- Munoz-Hernandez, S., Pablos-Ceruelo, V. and Strass, H. (2011) Rfuzzy: Syntax, Semantics and Implementation Details of a Simple and Expressive Fuzzy Tool over Prolog. Information Sciences, 181, 1951-1970. http://dx.doi.org/10.1016/j.ins.2010.07.033
- Medina, J., Ojeda-Aciego, M. and Vojtáš, P. (2004) Similarity-Based Unification: A Multi-Adjoint Approach. Fuzzy Sets and Systems, 146, 43-62. http://dx.doi.org/10.1016/j.fss.2003.11.005
- Medina, J., Ojeda-Aciego, M. and Vojtas, P. (2001) Multi-Adjoint Logic Programming with Continuous Semantics. Proceedings of Logic Programming and Non-Monotonic Reasoning, LPNMR’01. In: Lecture Notes in Computer Science, Vol. 2173, Springer-Verlag, Berlin, 351-364.
- Medina, J., Ojeda-Aciego, M. and Vojtas, P. (2001) A Procedural Semantics for Multi-Adjoint Logic Programing. Progress in Artificial Intelligence, EPIA’01. In: Lecture Notes in Computer Science, Vol. 2258, Springer-Verlag, Berlin, 290-297.
- Julián, P., Moreno, G. and Penabad, J. (2009) On the Declarative Semantics of Multi-Adjoint Logic Programs. Proceedings of 10th International Work-Conference on Artificial Neural Networks, IWANN’09. In: Lecture Notes in Computer Science, Vol. 5517, Springer-Verlag, Berlin, 253-260.
- Lassez, J.L., Maher, M.J. and Marriott, K. (1988) Unification Revisited. In: Minker, J., Ed., Foundations of Deductive Databases and Logic Programming, Morgan Kaufmann, Los Altos, 587-625.
- Julián, P., Moreno, G. and Penabad, J. (2006) Operational/Interpretive Unfolding of Multi-Adjoint Logic Programs. Journal of Universal Computer Science, 12, 1679-1699.
- Julián, P., Moreno, G. and Penabad, J. (2007) Measuring the Interpretive Cost in Fuzzy Logic Computations. Applications of Fuzzy Sets Theory, Proceedings of 7th International Workshop on Fuzzy Logic and Applications, WILF’07. In: Lecture Notes in Computer Science, Vol. 4578, Springer-Verlag, Berlin, 28-36.
- Morcillo, P. and Moreno, G. (2009) On Cost Estimations for Executing Fuzzy Logic Programs. Proceedings of the 2009 International Joint Conference on Artificial Intelligence, ICAI’09, Las Vegas, 13-16 July 2009, 217-223.
- Morcillo, P. and Moreno, G. (2009) Modeling Interpretive Steps in Fuzzy Logic Computations. Proceedings of the 8th International Workshop on Fuzzy Logic and Applications, WILF’09. In: Lecture Notes in Computer Science, Vol. 5571, Springer-Verlag, Berlin, 44-51.
- Julián, P., Moreno, G. and Penabad, J. (2005) On Fuzzy Unfolding. A Multi-Adjoint Approach. Fuzzy Sets and Systems, 154, 16-33. http://dx.doi.org/10.1016/j.fss.2005.03.013
- Guerrero, J. and Moreno, G. (2008) Optimizing Fuzzy Logic Programs by Unfolding, Aggregation and Folding. Electronic Notes in Theoretical Computer Science, 219, 19-34. http://dx.doi.org/10.1016/j.entcs.2008.10.032
- Morcillo, P. and Moreno, G. (2008) Programming with Fuzzy Logic Rules by using the FLOPER Tool. Proceedings of the 2nd Rule Representation, Interchange and Reasoning on the Web, International Symposium, RuleML’08. In: Lecture Notes in Computer Science, Vol. 3521, Springer-Verlag, Berlin, 119-126.
- Morcillo, P., Moreno, G., Penabad, J. and Vázquez, C. (2010) Modeling Interpretive Steps into the FLOPER Environment. Proceedings of the 2010 International Conference on Artificial Intelligence, ICAI’10, Las Vegas, 12-15 July 2010, 16-22.
- Morcillo, P., Moreno, G., Penabad, J. and Vázquez, C. (2010) A Practical Management of Fuzzy Truth Degrees Using FLOPER. Proceedings of 4th International Symposium on Rule Interchange and Applications, RuleML’10. In: Lecture Notes in Computer Science, Vol. 6403, Springer-Verlag, Berlin, 20-34.
- Morcillo, P., Moreno, G., Penabad, J. and Vázquez, C. (2011) Declarative Traces into Fuzzy Computed Answers. Proceedings of 5th International Symposium on Rules: Research Based, Industry Focused, RuleML’11. In: Lecture Notes in Computer Science, Vol. 6826, Springer-Verlag, Berlin, 170-185.
- Morcillo, P.J., Moreno, G., Penabad, J. and Vázquez, C. (2012) Dedekind-Macneille Completion and Cartesian Product of Multi-Adjoint Lattices. International Journal of Computer Mathematics, 89, 1742-1752. http://dx.doi.org/10.1080/00207160.2012.689826
- Morcillo, P., Moreno, G., Penabad, J. and Vázquez, C. (2012) String-Based Multi-Adjoint Lattices for Tracing Fuzzy Logic Computations. Electronic Communications of the EASST, 55, 17.
- Vaucheret, C., Guadarrama, S. and Muñoz, S. (2002) Fuzzy Prolog: A Simple General Implementation Using clp(r). Proceedings of Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2002. In: Lecture Notes in Computer Science, Vol. 2514, Springer-Verlag, Berlin, 450-463.
- Rodrguez, M. and Romero, C.A. (2010) A Declarative Semantics for CLP with Qualification and Proximity. Theory and Practice of Logic Programming, 10, 627-642. http://dx.doi.org/10.1017/S1471068410000323
- Nguyen, H. and Walker, E. (2000) A First Course in Fuzzy Logic. Chapman & Hall/CRC, Boca Ratón.
- Almendros-Jiménez, J., Luna, A. and Moreno, G. (2012) Fuzzy Logic Programming for Implementing a Flexible XPath-Based Query Language. Electronic Notes on Theoretical Computer Science, ENTCS, 282, 3-18. http://dx.doi.org/10.1016/j.entcs.2011.12.002
- Almendros-Jiménez, J., Luna, A. and Moreno, G. (2013) Annotating “Fuzzy Chance Degrees” When Debugging Xpath Queries. Advances in Computational Intelligence-Proceedings of the 12th International Work-Conference on Artificial Neural Networks, IWANN 2013 (Special Session on Fuzzy Logic and Soft Computing Application). In: Lecture Notes in Computer Science, Vol. 7903, Springer-Verlag, Berlin, 300-311.
- Almendros-Jiménez, J., Luna, A., Moreno, G. and Vázquez, C. (2013) Analyzing Fuzzy Logic Computations with Fuzzy XPath. Actas de las XIII Jornadas sobre Programación y Lenguajes, PROLE’13, Jornadas SISTEDES, Madrid, 18-20 September 2013, 136-150.
- Bofill, M., Moreno, G., Vázquez, C. and Villaret, M. (2013) Automatic Proving of Fuzzy Formulae with Fuzzy Logic Programming and SMT. Actas de las XIII Jornadas sobre Programación y Lenguajes, PROLE’13, Jornadas SISTEDES, Madrid, 18-20 September 2013, 151-165.
- Vázquez, C., Tomás, L., Moreno, G. and Tordsson, J. (2013) A Fuzzy Approach to Cloud Admission Control for Safe overbooking. Proceedings of 10th International Workshop on Fuzzy Logic and Applications, WILF 2013, Genoa, 7-10 November 2013, 212-225.
- Julián, P., Medina, J., Moreno, G. and Ojeda, M. (2010) Efficient Thresholded Tabulation for Fuzzy Query Answering. Studies in Fuzziness and Soft Computing (Foundations of Reasoning under Uncertainty), 249, 125-141. http://dx.doi.org/10.1007/978-3-642-10728-3_7
- Julián, P., Medina, J., Morcillo, P., Moreno, G. and Ojeda-Aciego, M. (2013) An Unfolding-Based Preprocess for Reinforcing Thresholds in Fuzzy Tabulation. In: I. Rojas, G. J. Caparrós, and J. Cabestany, Eds., IWANN (1). In: Lecture Notes in Computer Science, Vol. 7902, Springer, Berlin, 647-655.
- Bruno, N., Chaudhuri, S. and Gravano, L. (2002) Top-K Selection Queries over Relational Databases: Mapping Strategies and Performance Evaluation. ACM Transactions on Database Systems, 27, 153-187. http://dx.doi.org/10.1145/568518.568519
- Chang, K.C.C. and Hwang, S.W. (2002) Minimal Probing: Supporting Expensive Predicates for Top-K Queries. SIGMOD Proceedings of the 2002 ACM SIGMOD International Conference on Management of DataMadison, 3-6 June 2002, 346-357.
- Ilyas, I.F., Aref, W.G. and Elmagarmid, A.K. (2004) Supporting Top-K Join Queries in Relational Databases. The VLDB Journal, 13, 207-221. http://dx.doi.org/10.1007/s00778-004-0128-2
- Chaudhuri, S., Gravano, L. and Marian, A. (2004) Optimizing Top-K Selection Queries over Multimedia Repositories. IEEE Transactions on Knowledge and Data Engineering, 16, 992-1009. http://dx.doi.org/10.1109/TKDE.2004.30
- Marian, A., Bruno, N. and Gravano, L. (2004) Evaluating Top-K Queries over Web-Accessible Databases. ACM Transactions on Database Systems, 29, 319-362. http://dx.doi.org/10.1145/1005566.1005569
- Theobald, M., Schenkel, R. and Weikum, G. (2005) Efficient and Self-Tuning Incremental Query Expansion for Top-K Query Processing. Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Salvador, 15-19 August 2005, 242-249.
- Li, C., Chang, K.C.C., Ilyas, I.F. and Song, S. (2005) Ranksql: Query Algebra and Optimization for Relational Top-K Queries. SIGMOD Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, 13-17 June 2005, 131-142.
- Lukasiewicz, T. and Straccia, U. (2007) Top-K Retrieval in Description Logic Programs under Vagueness for the Semantic Web. In: Prade, H. and Subrahmanian, V.S., Eds., SUM, In: Lecture Notes in Computer Science, Vol. 4772. Springer, Berlin, 16-30.
- Re, C., Dalvi, N.N. and Suciu, D. (2007) Efficient Top-K Query Evaluation on Probabilistic Data. IEEE 23rd International Conference on Data Engineering, Istanbul, 15-20 April 2007, 886-895.
- Eckhardt, A., Horváth, T. and Vojtás, P. (2007) Learning Different User Profile Annotated Rules for Fuzzy Preference Top-K Querying. In: Prade, H. and Subrahmanian, V.S., Eds., SUM, In: Lecture Notes in Computer Science, Vol. 4772. Springer, Berlin, 116-130.
- Ilyas, I.F., Beskales, G. and Soliman, M.A. (2008) A Survey of Top-K Query Processing Techniques in Relational Database Systems. ACM Computing Surveys, 40, Article No. 11.
NOTES
1Here we also assume that several versions of the classical conjunction operation have been implemented with different arities.