Authors:Carlos Ansótegui; Maria Luisa Bonet; Jesús Giráldez-Cru; Jordi Levy Pages: 27 - 39 Abstract: Publication date: September 2017 Source:Journal of Applied Logic, Volume 23 Author(s): Carlos Ansótegui, Maria Luisa Bonet, Jesús Giráldez-Cru, Jordi Levy The success of portfolio approaches in SAT solving relies on the observation that different SAT solvers may dramatically change their performance depending on the class of SAT instances they are trying to solve. In these approaches, a set of features of the problem is used to build a prediction model, which classifies instances into classes, and computes the fastest algorithm to solve each of them. Therefore, the set of features used to build these classifiers plays a crucial role. Traditionally, portfolio SAT solvers include features about the structure of the problem and its hardness. Recently, there have been some attempts to better characterize the structure of industrial SAT instances. In this paper, we use some structure features of industrial SAT instances to build some classifiers of industrial SAT families of instances. Namely, they are the scale-free structure, the community structure and the self-similar structure. First, we measure the effectiveness of these classifiers by comparing them to other sets of SAT features commonly used in portfolio SAT solving approaches. Then, we evaluate the performance of this set of structure features when used in a real portfolio SAT solver. Finally, we analyze the relevance of these features on the analyzed classifiers.
Authors:Jordi Montserrat-Adell; Núria Agell; Mónica Sánchez; Francesc Prats; Francisco Javier Ruiz Pages: 40 - 50 Abstract: Publication date: September 2017 Source:Journal of Applied Logic, Volume 23 Author(s): Jordi Montserrat-Adell, Núria Agell, Mónica Sánchez, Francesc Prats, Francisco Javier Ruiz Hesitant linguistic term sets have been introduced to capture the human way of reasoning using linguistic expressions involving different levels of precision. In this paper, a lattice structure is provided to the set of hesitant fuzzy linguistic term sets by means of the operations intersection and connected union. In addition, in a group decision making framework, hesitant fuzzy linguistic descriptions are defined to manage situations in which decision makers are assessing different alternatives by means of hesitant fuzzy linguistic term sets. Based on the introduced lattice structure, two distances between hesitant fuzzy linguistic descriptions are defined. These metric structures allow distances between decision makers to be computed. A centroid of the decision making group is proposed for each distance to model group representatives in the considered group decision making framework.
Authors:Eva Armengol; Josep Puyol-Gruart Pages: 51 - 69 Abstract: Publication date: September 2017 Source:Journal of Applied Logic, Volume 23 Author(s): Eva Armengol, Josep Puyol-Gruart Most of reasoning for decision making in daily life is based on preferences. As other kinds of reasoning processes, there are many formalisms trying to capture preferences, however none of them is able to capture all the subtleties of the human reasoning. In this paper we analyze how to formalize the preferences expressed by humans and how to reason with them to produce rankings. Particularly, we show that qualitative preferences are best represented with a combination of reward logics and conditional logics. We propose a new algorithm based on ideas of similarity between objects commonly used in case-based reasoning. We see that the new approach produces rankings close to the ones expressed by users.
Authors:Alvin Chiang; Esther David; Yuh-Jye Lee; Guy Leshem; Yi-Ren Yeh Pages: 1 - 13 Abstract: Publication date: May 2017 Source:Journal of Applied Logic, Volume 21 Author(s): Alvin Chiang, Esther David, Yuh-Jye Lee, Guy Leshem, Yi-Ren Yeh An anomaly, or outlier, is an object exhibiting differences that suggest it belongs to an as-yet undefined class or category. Early detection of anomalies often proves of great importance because they may correspond to events such as fraud, spam, or device malfunctions. By automating the creation of a ranking or list of deviations, we can save time and decrease the cognitive overload of the individuals or groups responsible for responding to such events. Over the years many anomaly and outlier metrics have been developed. In this paper we propose a clustering-based score ensembling method for outlier detection. Using benchmark datasets we evaluate quantitatively the robustness and accuracy of different ensemble strategies. We find that ensembling strategies offer only limited value for increasing overall performance, but provide robustness by negating the influence of severely underperforming models.
Authors:Nissim Francez Pages: 14 - 23 Abstract: Publication date: May 2017 Source:Journal of Applied Logic, Volume 21 Author(s): Nissim Francez The paper exposes the relevance of permuting conversions (in natural-deduction systems) to the role of such systems in the theory of meaning known as proof-theoretic semantics, by relating permuting conversion to harmony, hitherto related to normalisation only. This is achieved by showing the connection of permuting conversion to the general notion of canonicity, once applied to arbitrary derivations from open assumption. In the course of exposing the relationship of permuting conversions to harmony, a general definition of the former is proposed, generalising the specific cases of disjunction and existential quantifiers considered in the literature.
Authors:Torra Abstract: Publication date: September 2017 Source:Journal of Applied Logic, Volume 23 Author(s): Vicenç Torra Microaggregation has been proven to be an effective method for data protection in the areas of Privacy Preserving Data Mining (PPDM) and Statistical Disclosure Control (SDC). This method consists of applying a clustering method to the data set to be protected, and then replacing each of the data by the cluster representative. In this paper we propose a new method for microaggregation based on fuzzy clustering. This new approach has been defined with the main goal of being nondeterministic on the assignment of cluster centers to the original data, and at the same time being simple in its definition. Being nondeterministic permits us to overcome some of the attacks standard microaggregation suffers.
Authors:Sergio Mota Abstract: Publication date: Available online 14 March 2017 Source:Journal of Applied Logic Author(s): Sergio Mota This paper is devoted to three main aims: (I) to present the conceptual relations between recursion, on the one hand, and inductive definitions and mathematical induction, on the other; as well as among recursion and self-involvement. In order to receive the original and primary use of recursion in cognitive science, it is important to bear in mind the conceptual relations and distinctions between them. (II) To analyze the interpretation of recursion from two different approaches. The first one, mainly represented by Chomsky, emphasizes the origin of recursion in the formal sciences, and applies it to characterize the mechanical procedure which underlies the language faculty. On this view, recursion is a property of the mind/brain. The second one disregards this conception of recursion and redefines it in terms of either the processing of self-embedded structures (e.g. [20]) or the ability to represent multiple hierarchical levels using the same rule (e.g. [45]); or as follows: recursion refers to the ability to embed structures within structures of the same kind (e.g. [48]). (III) To discuss whether or not this change in the meaning of recursion is more suitable than the original one for empirical research.
Authors:Khaza Anuarul Hoque; Otmane Ait Mohamed; Yvon Savaria Abstract: Publication date: Available online 4 March 2017 Source:Journal of Applied Logic Author(s): Khaza Anuarul Hoque, Otmane Ait Mohamed, Yvon Savaria SRAM-based FPGAs are increasingly popular in the aerospace industry due to their field programmability and low cost. However, they suffer from cosmic radiation induced Single Event Upsets (SEUs). In safety-critical applications, the dependability of the design is a prime concern since failures may have catastrophic consequences. An early analysis of the relationship between dependability metrics, performability-area trade-off, and different mitigation techniques for such applications can reduce the design effort while increasing the design confidence. This paper introduces a novel methodology based on probabilistic model checking, for the analysis of the reliability, availability, safety and performance-area tradeoffs of safety-critical systems for early design decisions. Starting from the high-level description of a system, a Markov reward model is constructed from the Control Data Flow Graph (CDFG) and a component characterization library targeting FPGAs. The proposed model and exhaustive analysis capture all the failure states (based on the fault detection coverage) and repairs possible in the system. We present quantitative results based on an FIR filter circuit to illustrate the applicability of the proposed approach and to demonstrate that a wide range of useful dependability and performability properties can be analyzed using the proposed methodology. The modeling results show the relationship between different mitigation techniques and fault detection coverage, exposing their direct impact on the design for early decisions.
Authors:Xin Sun; Livio Robaldo Abstract: Publication date: Available online 4 March 2017 Source:Journal of Applied Logic Author(s): Xin Sun, Livio Robaldo Input/output logic is a formalism in deontic logic and normative reasoning. Unlike deontic logical frameworks based on possible-world semantics, input/output logic adopts norm-based semantics in the sense of [13], specifically operational semantics. It is well-known in theoretical computer science that complexity is an indispensable component of every logic. So far, previous literature in input/output systems focuses on proof theory and semantics, while neglects complexity. This paper adds the missing component by giving the complexity results of main decision problems in input/output logic. Our results show that input/output logic is coNP hard and in the 2nd level of the polynomial hierarchy.
Authors:John C. McCabe-Dansted; Mark Reynolds Abstract: Publication date: Available online 23 December 2016 Source:Journal of Applied Logic Author(s): John C. MCabe-Dansted, Mark Reynolds A number of procedures for checking the satisfiability of formulas in the important branching time temporal logic CTL* have recently been proposed. In this paper we develop techniques to support such reasoning based on rewrite rules. We consider how to automatically generate and quickly validate such rewrites. The techniques are based on use of so-called non-local and bundled variants of computation tree logics. We show that such rules can quickly simplify CTL* formulas. These simplified formulas are shorter and easier to reason with using existing decision procedures for CTL*, as demonstrated by significant speed-ups across a wide range of benchmark formulas. In this paper we provide both an Associative Commutative sound, confluent and terminating term rewrite system as well as a simple greedy rewrite system. We test them on a useful set of benchmarks. There are practical applications for theorem-proving and model-checking.
Authors:Hans van Ditmarsch; Jan van Eijck; Pere Pardo; Rahim Ramezanian; François Schwarzentruber Abstract: Publication date: Available online 5 December 2016 Source:Journal of Applied Logic Author(s): Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber A gossip protocol is a procedure for spreading secrets among a group of agents, using a connection graph. In each call between a pair of connected agents, the two agents share all the secrets they have learnt. In dynamic gossip problems, dynamic connection graphs are enabled by permitting agents to spread as well the telephone numbers of other agents they know. This paper characterizes different distributed epistemic protocols in terms of the (largest) class of graphs where each protocol is successful, i.e. where the protocol necessarily ends up with all agents knowing all secrets.
Authors:Grigory K. Olkhovikov Abstract: Publication date: Available online 24 November 2016 Source:Journal of Applied Logic Author(s): Grigory K. Olkhovikov The modal characterization theorem by J. van Benthem characterizes classical modal logic as the bisimulation invariant fragment of first-order logic. In this paper, we prove a similar characterization theorem for intuitionistic modal logic. For this purpose we introduce the notion of modal asimulation as an analogue of bisimulations. The paper treats four different fragments of first-order logic induced by their respective versions of Kripke-style semantics for modal intuitionistic logic. It is shown further that this characterization can be easily carried over to arbitrary first-order definable subclasses of classical first-order models.
Authors:Pavel Naumov; Jia Tao Abstract: Publication date: Available online 24 November 2016 Source:Journal of Applied Logic Author(s): Pavel Naumov, Jia Tao The article proposes a logical framework for reasoning about agents' ability to protect their privacy by hiding certain information from a privacy intruder. It is assumed that the knowledge of the intruder is derived from the observation of pieces of evidence and that there is a cost associated with the elimination of the evidence. The logical framework contains a modal operator labeled by a group of agents and a total budget available to this group. The key contribution of this work is the proposed incorporation of the cost factor into privacy protection reasoning within the standard modal logic framework. The main technical result are the soundness and completeness theorems for the introduced logical system with respect to a formally defined semantics.
Authors:Gabriele Kern-Isberner; Daniela Huvermann Abstract: Publication date: Available online 21 November 2016 Source:Journal of Applied Logic Author(s): G. Kern-Isberner, D. Huvermann Multiple iterated revision requires advanced belief revision techniques that are able to integrate several pieces of new information into epistemic states. A crucial feature of this kind of revision is that the multiple pieces of information should be dealt with separately. Previous works have proposed several independence postulates which should ensure this. In this paper, we argue, first, that these postulates are too strong as they may enforce beliefs without justification, and second, that they are not necessary to ensure the principal aim of multiple revision. Instead, principles of conditional preservation guarantee a suitable handling of sets of sentences under revision. We formalize such a principle for multiple propositional revision for ranking functions, and we propose some novel postulates for multiple iterated revision that are in line with AGM and the Darwiche & Pearl postulates. We show that just a few fundamental postulates are enough to cover major approaches to (multiple) iterated belief revision, and that independence in the sense of Thielscher, Jin, and Delgrande is optional. As a proof of concept, we present propositional c-revisions of ranking functions.
Authors:Jean-Christophe Magnan; Pierre-Henri Wuillemin Abstract: Publication date: Available online 17 November 2016 Source:Journal of Applied Logic Author(s): Jean-Christophe Magnan, Pierre-Henri Wuillemin In the domain of decision theoretic planning, the factored framework (Factored Markov Decision Process, fmdp) has produced optimized algorithms using structured representations such as Decision Trees (Structured Value Iteration (svi), Structured Policy Iteration (spi)) or Algebraic Decision Diagrams (Stochastic Planning Using Decision Diagrams (spudd)). Since it may be difficult to elaborate the factored models used by these algorithms, the architecture sdyna, which combines learning and planning algorithms using structured representations, was introduced. However, the state-of-the-art algorithms for incremental learning, for structured decision theoretic planning or for reinforcement learning require the problem to be specified only with binary variables and/or use data structures that can be improved in term of compactness. In this paper, we propose to use Multi-Valued Decision Diagrams (mdds) as a more efficient data structure for the sdyna architecture and describe a planning algorithm and an incremental learning algorithm dedicated to this new structured representation. For both planning and learning algorithms, we experimentally show that they allow significant improvements in time, in compactness of the computed policy and of the learned model. We then analyzed the combination of these two algorithms in an efficient sdyna instance for simultaneous learning and planning using mdds.
Authors:Pavel Naumov; Jia Tao Abstract: Publication date: Available online 16 November 2016 Source:Journal of Applied Logic Author(s): Pavel Naumov, Jia Tao The article proposes a way to add marketing into the standard threshold model of social networks. Within this framework, the article studies logical properties of the influence relation between sets of agents in social networks. Two different forms of this relation are considered: one for promotional marketing and the other for preventive marketing. In each case a sound and complete logical system describing properties of the influence relation is proposed. Both systems could be viewed as extensions of Armstrong's axioms of functional dependency from the database theory.
Authors:Angelika Kimmig; Guy Van den Broeck; Luc De Raedt Abstract: Publication date: Available online 15 November 2016 Source:Journal of Applied Logic Author(s): Angelika Kimmig, Guy Van den Broeck, Luc De Raedt Weighted model counting (WMC) is a well-known inference task on knowledge bases, and the basis for some of the most efficient techniques for probabilistic inference in graphical models. We introduce algebraic model counting (AMC), a generalization of WMC to a semiring structure that provides a unified view on a range of tasks and existing results. We show that AMC generalizes many well-known tasks in a variety of domains such as probabilistic inference, soft constraints and network and database analysis. Furthermore, we investigate AMC from a knowledge compilation perspective and show that all AMC tasks can be evaluated using sd-DNNF circuits, which are strictly more succinct, and thus more efficient to evaluate, than direct representations of sets of models. We identify further characteristics of AMC instances that allow for evaluation on even more succinct circuits.
Authors:Liessman Sturlaugson; Logan Perreault; John W. Sheppard Abstract: Publication date: Available online 15 November 2016 Source:Journal of Applied Logic Author(s): Liessman Sturlaugson, Logan Perreault, John W. Sheppard The continuous time Bayesian network (CTBN) is a probabilistic graphical model that enables reasoning about complex, interdependent, and continuous-time subsystems. The model uses nodes to denote subsystems and arcs to denote conditional dependence. This dependence manifests in how the dynamics of a subsystem changes based on the current states of its parents in the network. While the original CTBN definition allows users to specify the dynamics of how the system evolves, users might also want to place value expressions over the dynamics of the model in the form of performance functions. We formalize these performance functions for the CTBN and show how they can be factored in the same way as the network, allowing what we argue is a more intuitive and explicit representation. For cases in which a performance function must involve multiple nodes, we show how to augment the structure of the CTBN to account for the performance interaction while maintaining the factorization of a single performance function for each node. We introduce the notion of optimization for CTBNs, and show how a family of performance functions can be used as the evaluation criteria for a multi-objective optimization procedure.
Authors:Xiaoyuan Zhu; Changhe Yuan Abstract: Publication date: Available online 15 November 2016 Source:Journal of Applied Logic Author(s): Xiaoyuan Zhu, Changhe Yuan Most Relevant Explanation (MRE) is an inference problem in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence. It has been shown in recent literature that it addresses the overspecification problem of existing methods, such as MPE and MAP. In this paper, we propose a novel hierarchical beam search algorithm for solving MRE. The main idea is to use a second-level beam to limit the number of successors generated by the same parent so as to limit the similarity between the solutions in the first-level beam and result in a more diversified population. Three pruning criteria are also introduced to achieve further diversity. Empirical results show that the new algorithm outperforms local search and regular beam search.
Authors:Paul Snow Abstract: Publication date: Available online 15 November 2016 Source:Journal of Applied Logic Author(s): Paul Snow De Finetti's 1949 ordinal probability conjecture sparked enduring interest in intuitively meaningful necessary and sufficient conditions for orderings of finite propositional domains to agree with probability distributions. This paper motivates probabilistic ordering from subjective estimates of credibility contrasts revealed when ordered propositions are not monotonically related (e.g., A or B > C or D, but D > B ) and when a portfolio of prospects is accepted as preferable to alternatives despite not dominating them. The estimated contrast primitive offers a gambling-free, psychologically grounded foundation for treating individual instances and multisets of propositions as credally interchangeable with disjunctions and multisets of their constituent atomic propositions.
Authors:Souhila Kaci; Robert Mercer; Matthias Thimm Abstract: Publication date: Available online 14 November 2016 Source:Journal of Applied Logic Author(s): Souhila Kaci, Robert Mercer, Matthias Thimm
Authors:Vicent Costa; Pilar Dellunde Abstract: Publication date: Available online 10 November 2016 Source:Journal of Applied Logic Author(s): Vicent Costa, Pilar Dellunde This paper is a contribution to the study of the universal Horn fragment of predicate fuzzy logics, focusing on some relevant notions in logic programming. We introduce the notion of term structure associated to a set of formulas in the fuzzy context and we show the existence of free models in fuzzy universal Horn classes. We prove that every equality-free consistent universal Horn fuzzy theory has a Herbrand model.
Authors:D. Boixader; J. Recasens Abstract: Publication date: Available online 9 November 2016 Source:Journal of Applied Logic Author(s): D. Boixader, J. Recasens A T-indistinguishability operator (or fuzzy similarity relation) E is called unidimensional when it may be obtained from one single fuzzy subset (or fuzzy criterion). In this paper, we study when a T-indistinguishability operator that has been obtained as an average of many unidimensional ones is unidimensional too. In this case, the single fuzzy subset used to generate E is explicitly obtained as the quasi-arithmetic mean of all the fuzzy criteria primarily involved in the construction of E.
Authors:Eva Armengol; Dionís Boixader; Francisco Grimaldo Abstract: Publication date: Available online 9 November 2016 Source:Journal of Applied Logic Author(s): Eva Armengol, Dionís Boixader, Francisco Grimaldo
Subscription journal
[3043 journals]
