Abstract In this work, we present polyhedral semantics as a means to tractably approximate Łukasiewicz infinitely-valued logic (Ł∞). As Ł∞ is an expressive multivalued propositional logic whose decision problem is NP-complete, we show how to to obtain an approximation for this problem providing a family of multivalued logics over the same language as Ł∞. Each element of the family is associated to a polynomial-time linear program, thus providing a tractable way of deciding each intermediate step. We also investigate properties of the logic system derived from polyhedral semantics and the details of an algorithm for the approximation process.

Abstract A Nash equilibrium is a strategy profile of a game in which none of the players involved has any gain by changing alone his/her own strategy. Given a two-player game, we show a codification of all of its Nash equilibria into Łukasiewicz infinitely-valued logic, that is, we derive a propositional theory in this logic whose models codify all the Nash equilibria. Based on such propositional theory, we derive a polynomial reduction from the problem of computing a Nash equilibrium to the problem of satisfiability of (sets of) formulas of Łukasiewicz infinitely-valued logic. These applications of logic to game theory lead to new methods for computing Nash equilibria.

Abstract The recent progress of deep learning techniques has produced models capable of achieving high scores on traditional Natural Language Inference (NLI) datasets. To understand the generalization limits of these powerful models, an increasing number of adversarial evaluation schemes have appeared. These works use a similar evaluation method: they construct a new NLI test set based on sentences with known logic and semantic properties (the adversarial set), train a model on a benchmark NLI dataset, and evaluate it in the new set. Poor performance on the adversarial set is identified as a model limitation. The problem with this evaluation procedure is that it may only indicate a sampling problem. A machine learning model can perform poorly on a new test set because the text patterns presented in the adversarial set are not well represented in the training sample. To address this problem, we present a new evaluation method, the Invariance under Equivalence test (IE test). The IE test trains a model with sufficient adversarial examples and checks the model’s performance on two equivalent datasets. As a case study, we apply the IE test to the state-of-the-art NLI models using synonym substitution as the form of adversarial examples. The experiment shows that, despite their high predictive power, these models usually produce different inference outputs for equivalent inputs, and, more importantly, this deficiency cannot be solved by adding adversarial observations in the training data.

Abstract This work concerns the representation of a class of continuous functions into Logic, so that one may automatically reason about properties of these functions using logical tools. Rational McNaughton functions may be implicitly represented by logical formulas in Łukasiewicz Infinitely-valued Logic by constraining the set of allowed valuations; such a restriction contemplates only those valuations that satisfy specific formulas. This work investigates two approaches to such depiction, called representation modulo satisfiability. Furthermore, a polynomial-time algorithm that builds this representation is presented, producing a pair of formulas consisting of the representative formula and the constraining one, given as input a rational McNaughton function in a suitable encoding. An implementation of the algorithm is discussed.

In this work, we propose several techniques to address data scarceness in ComParE 2021 COVID-19 identification tasks for the application of deep models such as Convolutional Neural Networks.Data is initially preprocessed into spectrogram or MFCC-gram formats.After preprocessing, we combine three different data augmentation techniques to be applied in model training.Then we employ transfer learning techniques from pretrained audio neural networks.Those techniques are applied to several distinct neural architectures.For COVID-19 identification in speech segments, we obtained competitive results.On the other hand, in the identification task based on cough data, we succeeded in producing a noticeable improvement on existing baselines, reaching 75.9% unweighted average recall (UAR).

We study algorithms for fragments of first order logic ex- tended with counting quantifiers, which are known to be highly complex in general. We propose a fragment over unary predicates that is NP-complete and for which there is a nor- mal form where Counting Quantification sentences have a single Unary predicate, thus call it the CQU fragment. We provide an algebraic formulation of the CQU satisfiability problem in terms of Integer Linear Programming based on which two algorithms are proposed, a direct reduction to SAT instances and an Integer Linear Programming version extended with a column generation mechanism. The latter is shown to lead to a viable implementation and experiments shows this algorithm presents a phase transition behavior.

Abstract This work presents a method for predicting resource availability in opportunistic grids by means of use pattern analysis (UPA), a technique based on non‐supervised learning methods. This prediction method is based on the assumption of the existence of several classes of computational resource use patterns, which can be used to predict the resource availability. Trace‐driven simulations validate this basic assumptions, which also provide the parameter settings for the accurate learning of resource use patterns. Experiments made with an implementation of the UPA method show the feasibility of its use in the scheduling of grid tasks with very little overhead. The experiments also demonstrate the method's superiority over other predictive and non‐predictive methods. An adaptative prediction method is suggested to deal with the lack of training data at initialization. Further adaptative behaviour is motivated by experiments which show that, in some special environments, reliable resource use patterns may not always be detected. Copyright © 2009 John Wiley & Sons, Ltd.

The logic of proofs (lp) was proposed as Gödel's missed link between Intuitionistic and S4-proofs, but so far the tableau-based methods proposed for lp have not explored this closeness with S4 and contain rules whose analycity is not immediately evident. We study possible formulations of analytic tableau proof methods for lp that preserve the subformula property. Two sound and complete tableau decision methods of increasing degree of analycity are proposed, KELP and preKELP. The latter is particularly inspired on S4-proofs. The crucial role of proof constants in the structure of lp-proofs methods is analysed. In particular, a method for the abduction of proof constant specifications in strongly analytic preKELP proofs is presented; abduction heuristics and the complexity of the method are discussed.

In this article we present ⁠, a family of logics that is useful to disprove propositional formulas by means of an anytime approximation process. The systems follows the paradigm of a parameterized family of logics established by Schaerf's and Cadoli's system S1. We show that inherits several of the nice properties of S1, while presenting several attractive new properties. The family deals with the full propositional language, has a complete tableau proof system which provides for incremental approximations; furthermore, it constitutes a full approximation of classical logic from above, with an approximation process with better relevance and locality properties than S1. When applied to clausal inference, provides a strong simplification method. An application of to model-based diagnosis is presented, demonstrating how the solution to this problem can benefit from the use of approximations.

Abstract Grid computing technology improves the computing experiences at organizations by effectively integrating distributed computing resources. However, just a small fraction of currently available Grid infrastructures focuses on reutilization of existing commodity computing resources. This paper introducesInteGrade, a novel object‐oriented middleware Grid infrastructure that focuses on leveraging the idle computing power of shared desktop machines. Its features include support for a wide range of parallel applications and mechanisms to assure that the owners of shared resources do not perceive any loss in the quality of service. A prototype implementation is under construction and the current version is available for download. Copyright © 2004 John Wiley & Sons, Ltd.

Real agents (natural or artificial) are limited in their reasoning capabilities. In this paper, we present a general framework for modelling limited reasoning based on approximate reasoning and discuss its properties. We start from Cadoli and Schaerf's approximate entailment. We first extend their system to deal with the full language of propositional logic. A tableau inference system is proposed for the extended system together with a subclassical semantics; it is shown that this new approximate reasoning system is sound and complete with respect to this semantics. We show how this system can be incrementally used to move from one approximation to the next until the reasoning limitation is reached. We also present a sound and complete axiomatization of the extended system. We note that although the extension is more expressive than the original system, it offers less control over the approximation process. We then propose a more general system and show that it keeps the increased expressivity and recovers the control. A sound and complete formulation for this new system is given and its expressivity and control advantages are formally proved.

Journal Article A logical reconstruction of temporal databases Get access M Finger M Finger Departamento de Ciência da Computação, Instituto de Matemática e Estatística, Universidade de São Paulo, Sao Paulo, Brazil E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 10, Issue 6, December 2000, Pages 847–876, https://doi.org/10.1093/logcom/10.6.847 Published: 01 December 2000