Clasificación por Disciplina
Nomenclatura Unesco > (11) Lógica > (1103) Lógica general
Nomenclatura Unesco > (11) Lógica > (1103) Lógica general
Fernando Ferreira
Abstract. We study, within the framework of intuitionistic logic, two well-known general results of (classical logic) bounded arithmetic. Firstly, Parikh’s theorem on the existence of bounding terms for the provably total functions. Secondly, the result which states that adding the scheme of bounded collection to (suitable) bounded theories does not yield new Π2 consequences.
Myla Archer; Constance Heitmeyer
Assuring the correctness of specifications of realtime systems can involve significant human effort. The use of a mechanical theorem prover to encode such specifications and to verify their properties could significantly reduce this effort. A barrier to routinely encoding and mechanically verifying specifications has been the need first to master the specification language and logic of a general theorem proving system. Our approach to overcoming this barrier is to provide mechanical support for producing specifications and verifying proofs, specialized for particular mathematical models and proof techniques. We are currently developing a mechanical verification system called TAME (Timed Automata Modeling Environment)...
We introduce a framework for studying and solving a class of CSP formulations. The framework allows constraints to be expressed as linear and nonlinear equations, then compiles them into SAT instances via Boolean logic circuits. While in general reduction to SAT may lead to the loss of structure, we specifically detect several types of structure in high-level input and use them in compilation. Linearity is preserved by the use of pseudo-Boolean (PB) constraints in conjunction with a 0-1 ILP solver that extends common SAT-solving techniques. Symmetries are detected in high-level constraints by solving the graph automorphism problem on parse trees....
Yarden Katz
A drawback of traditional default logic is that there is no general mechanism for preferring one default rule over another. To remedy this problem, numerous default logics augmented with priority relations have been introduced. In this paper, we show how trust values, derived from web-based social networks, can be used to prioritize defaults. We provide a coupling between the method for computing trust values in social networks given in (Golbeck 2005) and the prioritized Reiter defaults of (Baader & Hollunder 1995), where specificity of terminological concepts is used to prioritize defaults. We compare our approach with specificity-based prioritization, and discuss...
Fahiem Bacchus
We present a mechanism for constructing graphical models, speci cally Bayesian networks, from a knowledge base of general probabilistic information. The unique feature of our approach is that it uses a powerful first-order probabilistic logic for expressing the general knowledge base. This logic allows for the representation of a wide range of logical and probabilistic information. The model construction procedure we propose uses notions from direct inference to identify pieces of local statistical information from the knowledge base that are most appropriate to the particular event wewant toreason about. These pieces are composed to generate a joint probability distribution specified...
Ádám Darvas, et al.
Most attempts at analysing secure information flow in programs are based on domain-specific logics. Though computationally feasible, these approaches suffer from the need for abstraction and the high cost of building dedicated tools for real programming languages. We recast the information flow problem in a general program logic rather than a problem-specific one. We investigate the feasibility of this approach by showing how a general purpose tool for software verification can be used to perform information flow analyses. We are able to handle phenomena like method calls, loops, and object types for the target language Java Card. We are also...
Marco A. Casanova; Ramiro Guerreiro; Andrea Silva
The foundations of a class of logic programming systems with the expressive power of full first-order logic and a non-monotonic component is addressed. The underlying refutation method is an extended version of weak model elimination. The first question addressed is how to compute answers with weak model elimination when queries and programs are sets of arbitrary clauses, which is completely settled by a soundness and completeness result. The question of computing only definite answers is also settled. Then, the problem of computing answers is rediscussed when the logic programs also include a finite set of defaults. 1.
We present a general logic of explicit knowledge represented as finite sets of logical formulae which can evolve by nondeterministic reasoning and communication. It is partly based on Alternating-time Temporal Logic, which allows the expression of properties of cooperation. Properties of an agent’s reasoning mechanism such as “the agent knows modus ponens ” can be expressed. Instead of a common closure condition such as “if the agent knows both p and p → q, he must also know q”, the following holds: “if the agent knows p, p → q and modus ponens, he has a strategy to get to...
Joeri Engelfriet; Jan Treur
ABSTRACT. Two levels of description of nonmonotonic reasoning are distinguished. For these levels semantical formalizations are given. The first level is defined semantically by the notion of belief state frame, the second level by the notion of reasoning frame. We introduce two specification languages to describe nonmonotonic reasoning at each of the levels: (1) a specification language for level 1, with formal semantics based on belief state frames, (2) a fragment of infinitary temporal logic as a general specification language for level 2, with formal semantics based on reasoning frames. In our framework every level 2 description can be abstracted...
Ramon P. Otero
Abstract. Induction of the effects of actions considered here consists in learning an action description of a dynamic system from evidence on its behavior. General logic-based induction methods can deal with this problem but, unfortunately, most of the solutions provided have the frame problem. To cope with the frame problem induction under suitable nonmonotonic formalisms has to be used, though this kind of induction is not well understood yet. We propose an alternative method that relies on the identification of a monotonic induction problem whose solutions correspond one-to-one to those of the original problem without the frame problem. From this...
Michal Walicki
Abstract. Syntactic structures based on standard syntactic assignments model knowledge directly rather than as truth in all possible worlds as in modal epistemic logic, by assigning arbitrary truth values to atomic epistemic formulae. This approach to epistemic logic is very general and is used in several logical frameworks modeling multi-agent systems, but has no interesting logical properties — partly because the standard logical language is too weak to express properties of such structures. In this paper we extend the logical language with a new operator used to represent the proposition that an agent “knows at most ” a given finite...
Markus Krötzsch; Sebastian Rudolph
Abstract. EL ++ is a rather expressive description logic (DL) that still admits polynomial time inferencing for many reasoning tasks. Conjunctive queries are an important means for expressive querying of DL knowledge bases. In this paper, we address the problem of computing conjunctive query entailment forEL ++ knowledge bases. As it turns out, querying unrestrictedEL ++ is actually undecidable, but we identify restrictions under which query answering becomes decidable and even tractable. To the best of our knowledge, the presented algorithm is the first to answer conjunctive queries in a description logic that admits general role inclusion axioms. 1
Chitta Baral; Vladik Kreinovich; Raúl A. Trejo
In the last decade, there has been several studies on the computational complexity of planning. These studies normally assume that the goal of planning is to make a certain fluent true after the sequence of actions. In many real-life planning problems, the goal is represented in a much more complicated temporal form: e.g., in addition to having a desired fluent true at the end, we may want to keep certain fluents true at all times. In this paper, we study the complexity of planning for such temporal goals. We show that for goals expressible in Linear Temporal Logic, planning has...
Rob Gerth; Den Dolech; Doron Peled; Moshe Y. Vardi; Pierre Wolper; Universite De Liege
We present a tableau-based construction for obtaining an automaton from a temporal logic formula in an "on-the-fly" fashion. That is, the automaton can be constructed simultaneously with, and guided by, the generation of the model. In particular, it is possible to detect that a property does not hold by only constructing part of the model and of the automaton. The algorithm can also be used to check the validity of a temporal logic assertion. Although the general problem is PSPACE-complete, experiments show that our algorithm performs quite well on the temporal formulas typically encountered in verification. While basing linear-time temporal...
Murali Kudlugi; Russell Tessier
With the advent of system-on-a-chip design, many ASICs now require multiple design clocks that operate asynchronously to each other. This design characteristic presents a significant challenge when these ASIC designs are mapped to parallel verification hardware such as parallel cycle-based simulators and logic emulators. In general, these systems require all computation and communication to be synchronized to a global system clock. As a result, the undefined relationship between design clocks can make it difficult to determine hold times for synchronous storage elements and causality relationships along reconvergent communication paths. This paper presents new scheduling and synchronization techniques to support accurate...
Luc Dehaspe; Hannu Toivonen; Sǎso Dˇzeroski; Nada Lavrač
Discovery of frequent patterns has been studied in a variety of data mining settings. In its simplest form, known from association rule mining, the task is to discover all frequent itemsets, i.e., all combinations of items that are found in a sufficient number of examples. The fundamental task of association rule and frequent set discovery has been extended in various directions, allowing more useful patterns to be discovered with special purpose algorithms. We present Warmr, a general purpose inductive logic programming algorithm that addresses frequent query discovery: a very general Datalog formulation of the frequent pattern discovery problem.
Narciso Marti-Oliet; José Meseguer
Rewriting logic [40] is proposed as a logical framework in which other logics can be represented, and as a semantic framework for the specification of languages and systems. Using concepts from the theory of general logics [39], representations of an object logic L in a framework logic F are understood as mappings L ! F that translate one logic into the other in a conservative way. The ease with which such maps can be defined is discussed in detail for the cases of linear logic, logics with quantifiers, and any sequent calculus presentation of a logic for a very general...
Wm. S. Cooperaitao Chen
ABSTRACT The experiments described here are part of a researchprogram whose objective is to develop a full-text The full-text retrieval design problem is largely a problem in the combination of statistical evidence. With this as its premise, the Berkeley group has concentrated on the challenge of finding a statistical methodology for combining retrieval clues in as powerful a way as possible, consistent with reasonable analytic and computational simplicity. Thus our research focus has been on the general logic of how to combine clues, with no attempt made at this stage to exploit as many clues as possible. We feel that...
Gerhard Lakemeyer
The idea of only-knowing a collection of sentences has been previously shown to have a close connection with autoepistemic logic. Here we propose a more general account of only-knowing that captures not only autoepistemic logic but default logic as well. This allows us not only to study the properties of default logic in terms of an underlying model of belief, but also the relationship among different forms of nonmonotonic reasoning, all within a classical monotonic logic characterized semantically in terms of possible worlds.
A. Pettorossi; M. Proietti
We address the problem of proving the total correctness of transformations of definite logic programs. We consider a general transformation rule, called clause replacement, which consists in transforming a program P into a new program Q by replacing a set Γ1 of clauses occurring in P by a new set Γ2 of clauses, provided that Γ1 and Γ2 are equivalent in the least Herbrand model M(P) of the program P. We propose a general method for proving that transformations based on clause replacement are totally correct, that is, M(P) = M(Q). Our method consists in showing that the transformation of...