Inverse entailment (IE) is a fundamental approach for hypothesis finding in explanatory induction. Some IE systems can find any hypothesis in full-clausal theories, but need several non-deterministic operators that tr...
详细信息
A framework for unfold/fold transformation of (constraint) co-logic programs has been proposed recently, which can be used to prove properties of co-logic programs, thereby allowing us to reason about infinite sequenc...
详细信息
First-order temporal logics are notorious for their bad computational behaviour. It is known that even the two-variable monadic fragment is highly undecidable over various timelines. However, following the introductio...
详细信息
Current approaches to analyzing dynamic systems are mostly grounded in propositional (temporal) logics. As a consequence, they often lack expressivity for modelling rich data structures and reasoning about them in the...
详细信息
ISBN:
(数字)9783642405372
ISBN:
(纸本)9783642405365
Current approaches to analyzing dynamic systems are mostly grounded in propositional (temporal) logics. As a consequence, they often lack expressivity for modelling rich data structures and reasoning about them in the course of a computation. To address this problem, we propose a rich modelling framework based on first-order logic over background theories (arithmetics, lists, records, etc) and state transition systems over corresponding interpretations. On the reasoning side, we introduce a tableau calculus for bounded model checking of properties expressed in a certain fragment of CTL* over that first-order logic. We also describe a k-induction scheme on top of that calculus for proving safety properties, and we report on first experiments with a prototypical implementation.
Discovering relational structure between input features in sequence labeling models has shown to improve their accuracies in several problem settings. The problem of learning relational structure for sequence labeling...
详细信息
The proceedings contain 41 papers. The topics discussed include: Res Publica: the universal model of computation;means and limits of decision;from determinism, non-determinism and alternation to recursion schemes for ...
ISBN:
(纸本)9783939897606
The proceedings contain 41 papers. The topics discussed include: Res Publica: the universal model of computation;means and limits of decision;from determinism, non-determinism and alternation to recursion schemes for P, NP and Pspace;descriptive complexity of approximate counting CSPs;team building in dependence;unambiguity and uniformization problems on infinite trees;bounds for the quantifier depth in finite-variable logics: alternation hierarchy;annotation-free sequent calculi for full intuitionistic linear logic;infinite-state games with finitary conditions;innocent game semantics via intersection type assignment systems;deciding the weak definability of Büchi definable tree languages;and what is decidable about partially observable Markov decision processes with omega-regular objectives.
Interval temporal logics are quite expressive temporal logics, which turn out to be difficult to deal with in many respects. Even finite satisfiability of simple interval temporal logics presents non-trivial technical...
详细信息
ISBN:
(数字)9783642405372
ISBN:
(纸本)9783642405365
Interval temporal logics are quite expressive temporal logics, which turn out to be difficult to deal with in many respects. Even finite satisfiability of simple interval temporal logics presents non-trivial technical issues when it comes to the implementation of efficient tableau-based decision procedures. We focus our attention on the logic of Allen's relation meets, a.k.a. Right Propositional Neighborhood logic (RPNL), interpreted over finite linear orders. Starting from a high-level description of a tableau system, we developed a first working implementation of a decision procedure for RPNL, and we made it accessible from the web. We report and analyze the outcomes of some initial tests.
In a recent article, Lauri Hella and co-authors identify a canonical connection between modal logic and deterministic distributed constant-time algorithms. The paper reports a variety of highly natural logical charact...
详细信息
A growing set of on-line applications are generating data that can be viewed as very large collections of small, dense social graphs - these range from sets of social groups, events, or collaboration projects to the v...
详细信息
ISBN:
(纸本)9781450320351
A growing set of on-line applications are generating data that can be viewed as very large collections of small, dense social graphs - these range from sets of social groups, events, or collaboration projects to the vast collection of graph neighborhoods in large social networks. A natural question is how to usefully define a domain-independent 'coordinate system' for such a collection of graphs, so that the set of possible structures can be compactly represented and understood within a common space. In this work, we draw on the theory of graph homomorphisms to formulate and analyze such a representation, based on computing the frequencies of small induced subgraphs within each graph. We find that the space of subgraph frequencies is governed both by its combinatorial properties-based on extremal results that constrain all graphs - as well as by its empirical properties - manifested in the way that real social graphs appear to lie near a simple one-dimensional curve through this space. We develop flexible frameworks for studying each of these aspects. For capturing empirical properties, we characterize a simple stochastic generative model, a single-parameter extension of Erdo″s- Rényi random graphs, whose stationary distribution over subgraphs closely tracks the one-dimensional concentration of the real social graph families. For the extremal properties, we develop a tractable linear program for bounding the feasible space of subgraph frequencies by harnessing a toolkit of known extremal graph theory. Together, these two complementary frameworks shed light on a fundamental question pertaining to social graphs: what properties of social graphs are 'social' properties and what properties are 'graph' properties? We conclude with a brief demonstration of how the coordinate system we examine can also be used to perform classification tasks, distinguishing between structures arising from different types of social graphs. Copyright is held by the international World Wide W
The paper presents a tableau calculus with several refinements for reasoning in the description logic SHOI. The calculus uses non-standard rules for dealing with TBox statements. Whereas in existing tableau approaches...
详细信息
ISBN:
(数字)9783642405372
ISBN:
(纸本)9783642405365
The paper presents a tableau calculus with several refinements for reasoning in the description logic SHOI. The calculus uses non-standard rules for dealing with TBox statements. Whereas in existing tableau approaches a fixed rule is used for dealing with TBox statements, we use a dynamically generated set of refined rules. This approach has become practical because reasoners with flexible sets of rules can be generated with the tableau prover generation prototype MetTeL. We also define and investigate variations of the unrestricted blocking mechanism in which equality reasoning is realised by ordered rewriting and the application of the blocking rule is controlled by excluding its application to a fixed, finite set of individual terms. Reasoning with the unique name assumption and excluding ABox individuals from the application of blocking can be seen as two separate instances of the latter. Experiments show the refinements lead to fewer rule applications and improved performance.
暂无评论