| 1. |
- Ansotegui, Carlos, et al.
(författare)
-
Structure features for SAT instances classification
- 2017
-
Ingår i: Journal of Applied Logic. - : Elsevier. - 1570-8683 .- 1570-8691. ; 23, s. 27-39
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 2. |
- Eppe, Manfred, et al.
(författare)
-
A history based approximate epistemic action theory for efficient postdictive reasoning
- 2015
-
Ingår i: Journal of Applied Logic. - : Elsevier. - 1570-8683 .- 1570-8691. ; 13:4, s. 720-769
-
Tidskriftsartikel (refereegranskat)abstract
- We propose an approximation of the possible worlds semantics (PWS) of knowledge with support for postdiction - a fundamental inference pattern for diagnostic reasoning and explanation tasks in a wide range of real-world applications such as cognitive robotics, visual perception for cognitive vision, ambient intelligence and smart environments. We present the formal framework, an operational semantics, and an analysis of soundness and completeness results therefrom.The advantage of our approach is that only a linear number of state-variables are required to represent an agent's knowledge state. This is achieved by modeling knowledge as the history of a single approximate state, instead of using an exponential number of possible worlds like in Kripke semantics. That is, we add a temporal dimension to the knowledge representation which facilitates efficient postdiction. Since we consider knowledge histories, we call our theory h-approximation (HPX).Due to the linear number of state variables, HPX features a comparably low computational complexity. Specifically, we show that HPX can solve the projection problem in polynomial (tractable) time. It can solve planning problems in NP, while e.g. for the action language A(k) [48] this is Sigma(P)(2)-complete. In addition to the temporal dimension of knowledge, our theory supports concurrent acting and sensing, and is in this sense more expressive than existing approximations.
|
|
| 3. |
- Eppe, Manfred, et al.
(författare)
-
Approximate postdictive reasoning with answer set programming
- 2015
-
Ingår i: Journal of Applied Logic. - : Elsevier. - 1570-8683 .- 1570-8691. ; 13:4, s. 676-719
-
Tidskriftsartikel (refereegranskat)abstract
- We present an answer set programming realization of the h-approximation (HPX) theory [8] as an efficient and provably sound reasoning method for epistemic planning and projection problems that involve postdictive reasoning. The efficiency of HPX stems from an approximate knowledge state representation that involves only a linear number of state variables, as compared to an exponential number for theories that utilize a possible-worlds based semantics. This causes a relatively low computational complexity, i.e, the planning problem is in NP under reasonable restrictions, at the cost that HPX is incomplete. In this paper, we use the implementation of HPX to investigate the incompleteness issue and present an empirical evaluation of the solvable fragment and its performance. We find that the solvable fragment of HPX is indeed reasonable and fairly large: in average about 85% of the considered projection problem instances can be solved, compared to a PWS-based approach with exponential complexity as baseline. In addition to the empirical results, we demonstrate the manner in which HPX can be applied in a real robotic control task within a smart home, where our scenario illustrates the usefulness of postdictive reasoning to achieve error-tolerance by abnormality detection in a high-level decision-making task.
|
|
| 4. |
- Kimmig, Angelika, et al.
(författare)
-
Algebraic Model Counting
- 2017
-
Ingår i: Journal of Applied Logic. - : Elsevier. - 1570-8683 .- 1570-8691. ; 22, s. 46-62
-
Tidskriftsartikel (refereegranskat)abstract
- Weighted model counting (WMC) is a well-known inference task onknowledge bases, used for probabilistic inference in graphical models. Weintroduce algebraic model counting (AMC), a generalization of WMC toa semiring structure. We show that AMC generalizes many well-knowntasks in a variety of domains such as probabilistic inference, soft con-straints and network and database analysis. Furthermore, we investigateAMC from a knowledge compilation perspective and show that all AMCtasks can be evaluated usingsd-DNNFcircuits. We identify further char-acteristics of AMC instances that allow for the use of even more succinct circuits.
|
|
| 5. |
- Torra, Vicenç
(författare)
-
Fuzzy microaggregation for the transparency principle
- 2017
-
Ingår i: Journal of Applied Logic. - : Elsevier. - 1570-8683 .- 1570-8691. ; 23, s. 70-80
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 6. |
- Christoff, Zoé, et al.
(författare)
-
A logic for diffusion in social networks
- 2015
-
Ingår i: Journal of Applied Logic. - : Elsevier BV. - 1570-8683. ; 13:1, s. 48-77
-
Tidskriftsartikel (refereegranskat)abstract
- This paper introduces a general logical framework for reasoning about diffusion processes within social networks. The new “Logic for Diffusion in Social Networks” is a dynamic extension of standard hybrid logic, allowing to model complex phenomena involving several properties of agents. We provide a complete axiomatization and a terminating and complete tableau system for this logic and show how to apply the framework to diffusion phenomena documented in social networks analysis.
|
|
| 7. |
- Jacot, Justine, et al.
(författare)
-
From reasonable preferences, via argumentation, to logic
- 2016
-
Ingår i: Journal of Applied Logic. - : Elsevier BV. - 1570-8683. ; 18, s. 105-128
-
Tidskriftsartikel (refereegranskat)abstract
- This article demonstrates that typical restrictions which are imposed in dialogical logic in order to recover first-order logical consequence from a fragment of natural language argumentation are also forthcoming from preference profiles of boundedly rational players, provided that these players instantiate a specific player type and compute partial strategies. We present two structural rules, which are formulated similarly to closure rules for tableaux proofs that restrict players' strategies to a mapping between games in extensive forms (i.e., game trees) and proof trees. Both rules are motivated from players' preferences and limitations; they can therefore be viewed as being player-self-imposable. First-order logical consequence is thus shown to result from playing a specific type of argumentation game. The alignment of such games with the normative model of the Pragma-dialectical theory of argumentation is positively evaluated. But explicit rules to guarantee that the argumentation game instantiates first-order logical consequence have now become gratuitous, since their normative content arises directly from players' preferences and limitations. A similar naturalization for non-classical logics is discussed.
|
|
