Search

Dynamic graph theory is a novel, growing area that deals with graphs that change over time and is of great utility in modeling modern wireless, mobile and dynamic environments. As a graph evolves, possibly arbitrarily, it is challenging to identify the graph properties that can be preserved over time and understand their respective computability. In this paper we are concerned with the treewidth of dynamic graphs. We focus on metatheorems , which allow the generation of a series of results based on general properties of classes of structures. In graph theory two major metatheorems on treewidth provide complexity classifications by employing structural graph measures and finite model theory. Courcelle's Theorem gives a general tractability result for problems expressible in monadic second order logic on graphs of bounded treewidth, and Frick and Grohe demonstrate a similar result for first order logic and graphs of bounded local treewidth. We extend these theorems by showing that dynamic graphs of bounded (local) treewidth where the length of time over which the graph evolves and is observed is finite and bounded can be modeled in such a way that the (local) treewidth of the underlying graph is maintained. We show the application of these results to problems in dynamic graph theory and dynamic extensions to static problems. In addition we demonstrate that certain widely used dynamic graph classes have bounded local treewidth. [ABSTRACT FROM AUTHOR]

This paper presents a practical decision procedure for Propositional Projection Temporal Logic with infinite models. First, a set Prop l of labels l i , 0 ⩽ i ⩽ n ∈ N 0 , is used to mark nodes of an LNFG of a formula, and a node with l i is treated as an accepting state as in an automaton. Further, the generalized Büchi accepting condition for automata is employed to identify a path (resulting a word) in an LNFG as a model of the formula. In addition, the implementation details of the decision procedure and relevant algorithms including pre-processing, LNFG, circle finding algorithms are presented; as a matter of fact, all algorithms are implemented by C++ programs. [ABSTRACT FROM AUTHOR]

The problem of automated theorem finding is one of the 33 basic research problems in automated reasoning which was originally proposed by Wos in 1988, and it is still an open problem. To solve the problem, an approach of forward deduction based on the strong relevant logics was proposed. Following the approach, this paper presents a systematic methodology for automated theorem finding. To show the effectiveness of our methodology, the paper presents two case studies, one is automated theorem finding in NBG set theory and the other is automated theorem finding in Peano's arithmetic. Some known theorems have been found in our case studies. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to obtain a theoretical foundation of inconsistency-tolerant (or paraconsistent) reasoning by presenting a comprehensive study of the structural proof-theory of David Nelson’s paraconsistent logic. Inconsistency handling has a growing importance in Computer Science since inconsistencies may frequently occur in knowledge-based and intelligent information systems. Paraconsistent, inconsistency-tolerant logics have been studied to cope with such inconsistencies. In this paper, proof systems for Nelson’s paraconsistent logic N4 are comprehensively studied. The logic N4 is a fundamental system and known to be a common basis for various extended and useful paraconsistent logics. Some basic theorems including cut-elimination, normalization and completeness are uniformly proved using various embedding theorems. A variety of sequent calculi and natural deduction systems for N4 and some closely related systems are presented and compared. [Copyright &y& Elsevier]

Abstract: Eilenberg, Elgot and Shepherdson showed in 1969, [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by -tape automata, Journal of Algebra 13 (1969) 447–464], that a relation on finite words over a finite, non-unary alphabet with letters is definable in first order logic with predicates for the relations equal length, prefix and last letter is (for each letter ) if and only if it can be recognized by a finite multitape synchronous automaton, i.e., one whose read heads move simultaneously. They left open the characterization in the case of infinite alphabets, and proposed some conjectures concerning them. We solve all problems and sharpen the main theorem of [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by -tape automata, Journal of Algebra 13 (1969) 447–464]. [Copyright &y& Elsevier]

Abstract: This is a survey of results about versions of fine hierarchies and many-one reducibilities that appear in different parts of theoretical computer science. These notions and related techniques play a crucial role in understanding complexity of finite and infinite computations. We try not only to present the corresponding notions and facts from the particular fields but also to identify the unifying notions, techniques and ideas. [Copyright &y& Elsevier]

Abstract: We develop possible worlds (Kripke) semantics at the categorical abstract model theoretic level provided by the so-called ‘institutions’. Our general abstract modal logic framework provides a method for systematic Kripke semantics extensions of logical systems from computing science and logic. We also extend the institution-independent method of ultraproducts of [R. Diaconescu, Institution-independent ultraproducts, Fundamenta Informaticæ 55 (3–4) (2003) 321–348] to possible worlds semantics and prove a fundamental preservation result for abstract modal satisfaction. As a consequence we develop a generic compactness result for possible worlds semantics. [Copyright &y& Elsevier]

Abstract: We define a weighted monadic second order logic for trees where the weights are taken from a commutative semiring. We prove that a restricted version of this logic characterizes the class of formal tree series which are accepted by weighted bottom-up finite state tree automata. The restriction on the logic can be dropped if additionally the semiring is locally finite. This generalizes corresponding classical results of Thatcher, Wright, and Doner for tree languages and it extends recent results of Droste and Gastin [Weighted automata and weighted logics, in: Automata, Languages and Programming—32nd International Colloquium, ICALP 2005, Lisbon, Portugal, 2005, Proceedings, Lecture Notes in Computer Science, Vol. 3580, Springer, Berlin, 2005, pp. 513–525, full version in Theoretical Computer Science, to appear.] from formal power series on words to formal tree series. [Copyright &y& Elsevier]

Abstract: The recent interest for specification on resources yields so-called spatial logics, that is specification languages offering new forms of reasoning: the local reasoning through the separation of the resource space into two disjoint subspaces, and the contextual reasoning through hypothetical extension of the resource space. We consider two resource models and their related logics:[] The static ambient model, proposed as an abstraction of semistructured data (Proc. ESOP’01, Lecture Notes in Computer Science, vol. 2028, Springer, Berlin, 2001, pp. 1–22 (invited paper)) with the static ambient logic (SAL) that was proposed as a request language, both obtained by restricting the mobile ambient calculus (Proc. FOSSACS’98, Lecture Notes in Computer Science, vol. 1378, Springer, Berlin, 1998, pp. 140–155) and logic (Proc. POPL’00, ACM Press, New York, 2000, pp. 365–377) to their purely static aspects. [] The memory model and the assertion language of separation logic, both defined in Reynolds (Proc. LICS’02, 2002) for the purpose of the axiomatic semantic of imperative programs manipulating pointers. We raise the questions of the expressiveness and the minimality of these logics. Our main contribution is a minimalisation technique we may apply for these two logics. We moreover show some restrictions of this technique for the extension with universal quantification, and we establish the minimality of the adjunct-free fragment (). [Copyright &y& Elsevier]