CiteULike: AbnerCYH's logic

Finite Model Theory and Its Applications (Texts in Theoretical Computer Science. An EATCS Series)

Erich Grädel — 2007-10-09T18:32:12-00:00

(11 June 2007)

This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary logics to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science.

Fixed-Parameter Tractability, Definability, and Model-Checking

Jörg Flum — 2008-03-26T09:20:01-00:00

SIAM Journal on Computing, Vol. 31, No. 1. (2001), pp. 113-145.

Pages 113-145,

The modular decomposition of countable graphs. Definition and construction in monadic second-order logic

Bruno Courcelle — 2008-03-10T16:21:27-00:00

Theoretical Computer Science, Vol. 394, No. 1-2. (31 March 2008), pp. 1-38.

We consider the notion of modular decomposition for countable graphs. The modular decomposition of a graph given with an enumeration of its set of vertices can be defined by formulas of monadic second-order logic. Another result is the definition of a representation of modular decompositions by low degree relational structures. Such relational structures can also be defined in the considered graph by monadic second-order formulas.

Minimization of decision trees is hard to approximate

Detlef Sieling — 2008-01-22T14:43:43-00:00

Journal of Computer and System Sciences, Vol. 74, No. 3. (May 2008), pp. 394-403.

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown to be even hard to approximate up to any constant factor under the assumption P[not equal to]NP.

Kolmogorov complexities Kmax, Kmin on computable partially ordered sets

Marie Ferbus-Zanda — 2008-01-04T12:39:00-00:00

(2 Jan 2008)

We introduce a machine free mathematical framework to get a natural formalization of some general notions of infinite computation in the context of Kolmogorov complexity. Namely, the classes Max^X\to D_PR and Max^X\to D_Rec of functions X \to D which are pointwise maximum of partial or total computable sequences of functions where D = (D,<) is some computable partially ordered set. The enumeration theorem and the invariance theorem always hold for Max^X\to D_PR, leading to a variant KD;max of Kolmogorov complexity. We characterize the orders D such that the enumeration theorem (resp. the invariance theorem) also holds for Max^X\to D_Rec . It turns out that Max^X\to D_Rec may satisfy the invariance theorem but not the enumeration theorem. Also, when Max^X\to D_Rec satisfies the invariance theorem then the Kolmogorov complexities associated to Max^X\to D_Rec and Max^X\to D_PR are equal (up to a constant). Letting K^D_min = K^D^rev_max, where D^rev is the reverse order, we prove that either K^D_min =_ct K^D_max =_ct K^D (=_ct is equality up to a constant) or K^D_min, K^D_max are <=_ct incomparable and <_ct K^D and >_ct K^0',D. We characterize the orders leading to each case. We also show that K^D_min, K^D_max cannot be both much smaller than K^D at any point. These results are proved in a more general setting with two orders on D, one extending the other.

Is Randomness "Native" to Computer Science?

Marie Ferbus-Zanda — 2008-01-04T12:36:14-00:00

(1 Jan 2008)

We survey the Kolmogorov's approach to the notion of randomness through the Kolmogorov complexity theory. The original motivation of Kolmogorov was to give up a quantitative definition of information. In this theory, an object is randomness in the sense that it has a large information content. Afterwards, we present parts of the work of Martin-Lof, Schnorr, Chaitin and Levin which supply a mathematical notion of randomness throughout diverse theories from the the 60' up to recently.

Symbolic Graphs: Linear Solutions to Connectivity Related Problems

Raffaella Gentilini — 2007-12-16T16:17:05-00:00

Algorithmica, Vol. 50, No. 1. (15 January 2008), pp. 120-158.

Abstract The importance of symbolic data structures such as Ordered Binary Decision Diagrams (OBDD) is rapidly growing in many areas of Computer Science where the large dimensions of the input models is a challenging feature: OBDD based graph representations allowed to define truly new standards in the achievable dimensions for the Model Checking verification technique. However, OBDD representations pose strict constraints in the algorithm design issue. For example, Depth-First Search (DFS) is not feasible in a symbolic framework and, consequently, many state-of-the-art DFS based algorithms (e.g., connectivity procedures) cannot be easily rearranged to work on symbolically represented graphs. We devise here a symbolic algorithmic strategy, based on the new notion of spine-set, that is general enough to be the engine of linear symbolic step algorithms for both strongly connected components and biconnected components. Our procedures improve on previously designed connectivity symbolic algorithms. Moreover, by an application to the so-called “bad cycle detection problem”, our technique can be used to efficiently solve the emptiness problem for various kinds of ω-automata.

Complexity measures and decision tree complexity: a survey

Harry Buhrman — 2007-11-08T18:39:59-00:00

Theoretical Computer Science, Vol. 288, No. 1. (9 October 2002), pp. 21-43.

We discuss several complexity measures for Boolean functions: certificate complexity, sensitivity, block sensitivity, and the degree of a representing or approximating polynomial. We survey the relations and biggest gaps known between these measures, and show how they give bounds for the decision tree complexity of Boolean functions on deterministic, randomized, and quantum computers.

Boolean Delay Equations: A simple way of looking at complex systems

Michael Ghil — 2007-10-26T09:16:51-00:00

(24 Oct 2007)

Boolean Delay Equations (BDEs) are semi-discrete dynamical models with Boolean-valued variables that evolve in continuous time. Systems of BDEs can be classified into conservative or dissipative, in a manner that parallels the classification of ordinary or partial differential equations. Solutions to certain conservative BDEs exhibit growth of complexity in time. They represent therewith metaphors for biological evolution or human history. Dissipative BDEs are structurally stable and exhibit multiple equilibria and limit cycles, as well as more complex, fractal solution sets, such as Devil's staircases and “fractal sunbursts“. All known solutions of dissipative BDEs have stationary variance. BDE systems of this type, both free and forced, have been used as highly idealized models of climate change on interannual, interdecadal and paleoclimatic time scales. BDEs are also being used as flexible, highly efficient models of colliding cascades in earthquake modeling and prediction, as well as in genetics. In this paper we review the theory of systems of BDEs and illustrate their applications to climatic and solid earth problems. The former have used small systems of BDEs, while the latter have used large networks of BDEs. We moreover introduce BDEs with an infinite number of variables distributed in space (“partial BDEs“) and discuss connections with other types of dynamical systems, including cellular automata and Boolean networks. This research-and-review paper concludes with a set of open questions.

Size-depth trade-offs for threshold circuits

Russell Impagliazzo — 2007-10-23T09:11:07-00:00

(1993), pp. 541-550.

Computational model theory: An overview

M Vardi — 2006-11-24T09:19:49-00:00

(1998)

The computational complexity of a problem is the amount of resources, such as time or space, required by a machine that solves the problem. The descriptive complexity of problems is the complexity of describing problems in some logical formalism over finite structures. One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational and descriptive complexity. It is this connection between complexity theory and finite-model theory that...

Logic, Graphs, and Algorithms

Martin Grohe — 2007-09-25T16:09:42-00:00

(2007)

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic can be decided in linear time on graphs of bounded tree width. This article is an introduction into the theory underlying such meta theorems and a survey of the most important results in this area.

Classes of Recursively Enumerable Sets and Their Decision Problems

HG Rice — 2007-09-21T08:56:02-00:00

Transactions of the American Mathematical Society, Vol. 74, No. 2. (1953), pp. 358-366.

The parameterized complexity of database queries

Martin Grohe — 2007-08-23T11:12:55-00:00

(2001), pp. 82-92.

Parameterized circuit complexity and the W hierarchy

Rodney Downey — 2007-08-23T05:24:25-00:00

Theoretical Computer Science, Vol. 191, No. 1-2. (30 January 1998), pp. 97-115.

A parameterized problem <L, k> belongs to W[t] if there exists k' computed from k such that <L, k> reduces to the weight-k' satisfiability problem for weft-t circuits. We relate the fundamental question of whether the W[t] hierarchy is proper to parameterized problems for constant-depth circuits. We define classes G[t] as the analogues of AC0 depth-t for parameterized problems, and N[t] by weight-k' existential quantification on G[t], by analogy with NP = [there exists] [middle dot] P. We prove that for each t, W[t] equals the closure under fixed-parameter reductions of N[t]. Then we prove, using Sipser's results on the AC0 depth-t hierarchy, that both the G[t] and the N[t] hierarchies are proper. If this separation holds up under parameterized reductions, then the W[t] hierarchy is proper. We also investigate the hierarchy H[t] defined by alternating quantification over G[t]. By trading weft for quantifiers we show that H[t] coincides with H[1]. We also consider the complexity of unique solutions, and show a randomized reduction from W[t] to Unique W[t].

The classical decision problem

Egon Börger — 2007-07-28T14:27:32-00:00

(1997)

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

B Courcelle — 2007-07-25T09:38:01-00:00

Theory of Computing Systems, Vol. 33, No. 2. (4 March 2000), pp. 125-150.

Monadic Second-Order Evaluations on Tree-Decomposable Graphs.

Bruno Courcelle — 2007-07-25T07:49:36-00:00

Theor. Comput. Sci., Vol. 109, No. 1&2. (1993), pp. 49-82.

Every graph generated by a hyperedge replacement graph-grammar can be represented by a tree, namely the derivation tree of the derivation sequence that produced it. Certain functions on graphs can be computed recursively on the derivation trees of these graphs. By using monadic second-order logic and semiring homomorphisms, we describe in a single formalism a large class of such functions. Polynomial and even linear algorithms can be constructed for some of these functions. We unify similar results obtained by Takamizawa (1982), Bern (1987), Arnborg (1991) and Habel (1989).