The monadic second-order logic of graphs V: on closing the gap between definability and recognizability

Context-free graph-grammars are considered such that, in every generated graph G, a derivation tree of G can be constructed by means of monadic second-order formulas that specify its nodes, its labels, the successors of a node etc. A subset of the set of graphs generated by such a grammar is recognizable iff it is definable in monadic second-order logic, whereas, in general, only the “if” direction holds.     

The Monadic Quantifier Alternation Hierarchy over Grids and Graphs

The monadic second-order quantifier alternation hierarchy over the class of finite graphs is shown to be strict. The proof is based on automata theoretic ideas and starts from a restricted class of graph-like structures, namely finite two-dimensional grids. Considering grids where the width is a function of the height, we prove that the difference between the levels k+1 and k of the monadic hierarchy is witnessed by a set of grids where this function is (k+1)-fold exponential. We then transfer the hierarchy result to the class of directed (or undirected) graphs, using an encoding technique called strong reduction. It is notable that one can obtain sets of graphs which occur arbitrarily high in the monadic hierarchy but are already definable in the first-order closure of existential monadic second-order logic. We also verify that these graph properties even belong to the complexity class NLOG, which indicates a profound difference between the monadic hierarchy and the polynomial hierarchy.     

A note on the combinatorial structure of the visibility graph in simple polygons

Combinatorial structure of visibility is probably one of the most fascinating and interesting areas of engineering and computer science. The usefulness of visibility graphs in computational geometry and robotic navigation problems like motion planning, unknown-terrain learning, shortest-path planning, etc., cannot be overstressed. The visibility graph, apart from being an important data structure for storing and updating geometric information, is a valuable mathematical tool in probing and understanding the nature of shapes of polygonal and polyhedral objects. In this research we wish to initially focus our attention on a fundamental class of geometric objects. These geometric objects may be looked upon as building blocks for more complex geometric objects, and which offer an ideal balance between complexity and simplicity, namely simple polygons.

A major theme of the proposed paper is the investigation of the combinatorial structure of the visibility graph. More importantly, the goals of this paper are:

1. (i) To characterize the visibility graphs of simple polygons by obtaining necessary and sufficient conditions a graph must satisfy to qualify for the visibility graph of a simple polygon

2. (ii) To obtain hierarchical relationships between visibility graphs of simple polygons of a given number of vertices by treating them as representing simple polygons that are deformations of one another.

3. (iii) To exploit the potential of complete graphs to be natural coordinate systems for addressing the problem of reconstructing a simple polygon from visibility graph.

We intend to achieve this by defining appropriate “betweenness” relationships on points with respect to the edges of the complete graphs.     

The monadic second-order logic of graphs,II: Infinite graphs of bounded width

A countable graph can be considered as the value of a certain infinite expression, represented itself by an infinite tree. We establish that the set of finite or infinite (expression) trees constructed with a finite number of operators, the value of which is a graph satisfying a property expressed in monadic second-order logic, is itself definable in monadic second-order logic. From Rabin's theorem, the emptiness of this set of (expression) trees is decidable. It follows that the monadic second-order theory of an equational graph, or of the set of countable graphs of width less than an integerm, is decidable. This work has been supported by the “Programme de Recherches Coordonnées: Mathématiques et Informatique.” Reprints can be requested by electronic mail at mcvax!inria!geocub!courcell (on UUCP network) or courcell@geocub.greco-prog.fr. Unité de Recherche associée au C.N.R.S. no. 726.     

Dot-depth, monadic quantifier alternation, and first-order closure over grids and pictures

This paper presents results from two different areas. The first area is monadic second-order logic (MSO) over finite structures, in particular over the so-called grids. These are structures whose elements can be arranged as a matrix and which have two binary relations corresponding to vertical and horizontal successors. For this logic, we study the expressive power of the alternation of existential and universal monadic second-order quantifiers, i.e., set quantifiers. In Matz et al. (Information and Computation, LICS’ 97, 1999, to appear) it had been shown that these alternations cannot be limited to a fixed number without loss of expressiveness. In this paper, we strengthen this result in several ways. Firstly, we show that there are MSO formulas that have a very restricted form of k+1 set quantifiers but are not equivalent to a formula with k quantifiers. Secondly, we show that if we fix the number of such alternations, the expressive power of formulas that start with a block of universal quantifiers differs from the power of those that start with an existential one—this was previously known only for coloured grids. Thirdly, we investigate how an additional prefix of first-order (i.e., element) quantifiers influences the expressive power of MSO formulas. The second area that this paper is concerned with is two-dimensional formal language theory. We study how the alternation of (first- and monadic second-order) quantifications, on the one hand, relates to the dot-depth measure of two-dimensional (i.e., picture) languages, on the other hand. That measure is the two-dimensional version of the classical notion of dot-depth for (one-dimensional) starfree word languages. We show that the hierarchy induced by this dot-depth cuts through the hierarchy given by monadic second-order quantifications. In particular, beyond each level of the monadic second-order alternation hierarchy, there is a starfree picture language.     

An optimal gas-fired heating system

Utilizing a prescribed system configuration, this paper discusses the mathematical models of the system components used and formulates a method for controlling a domestic heating system in accordance to a prescribed criterion. The optimal problem treated is one of reducing the room temperature deviation from a prescribed reference value to zero, while at the same time minimizing the value of some predetermined performance or cost functional J. The development proceeds in essentially five steps.

1. (a) The development of the mathematical models for each of the elements of the heating system;

2. (b) Combining the mathematical models into a form which is suitable for the application of optimization techniques;

3. (c) Defining an optimization criterion which incorporates the main objective for minimizing room temperature variations with respect to a prescribed reference temperature;

4. (d) Choosing the optimization technique best suited for the problem;

5. (e) Constructing an optimal control system employing the optimization technique developed.

A numerical example compares the performance of the optimal system with a system of the conventional type which can be found in many American homes.     

Investigations on the Dual Calculus

The Dual Calculus, proposed recently by Wadler, is the outcome of two distinct lines of research in theoretical computer science:

(A) Efforts to extend the Curry–Howard isomorphism, established between the simply-typed lambda calculus and intuitionistic logic, to classical logic.

(B) Efforts to establish the tacit conjecture that call-by-value (CBV) reduction in lambda calculus is dual to call-by-name (CBN) reduction.

This paper initially investigates relations of the Dual Calculus to other calculi, namely the simply-typed lambda calculus and the Symmetric lambda calculus. Moreover, Church–Rosser and Strong Normalization properties are proven for the calculus’ CBV reduction relation. Finally, extensions of the calculus to second-order types are briefly introduced.

Discrete warehouse problem

A discrete warehouse is a collection of two-dimensional unit-square objects (robot and obstacles), which are allowed to move horizontally and vertically along grid lines. In this paper, we consider motion planning problems in a discrete warehouse with movable obstacles. In such a setup one is allowed to move some of the obstacles in order to:

1. (1) navigate the robot between an initial and a final position of the warehouse, and

2. (2) construct a clearing (path) between two specified points.

The final positions of the obstacles are unimportant for our problems.

We consider two forms of obstacle manipulations:

1. (a) remote, when the obstacles are moved by a remote mechanism, and

2. (b) contact, when the obstacles are moved only by direct contact of the robot.

We present necessary and sufficient conditions for the existence of a motion in both cases, and propose efficient algorithms for constructing feasible motions.     

A global parametrization of asymptotically stable linear systems

In this paper we construct a homeomorphism from the set of p × m transfer functions of McMillan degree n onto the open subspace of asymptotically stable linear systems. This homeomorphism yields a one-to-one correspondence between

1. (i) canonical forms for state space equivalence of minimal systems and

2. (ii) canonical forms for state space equivalence of asymptotically stable minimal systems.

Implications for the topology of various sets of asymptotically stable systems are given.     

Fuzzy multiple attributes and multiple hierarchical decision making

A procedure is proposed to solve the multiple attributes and multiple hierarchical system under fuzzy environment. The approach is based on:

1. (1) fuzzy representation;

2. (2) hierarchical performance evaluation structure,

3. (3) gradient eigenvector method for rating the fuzzy criteria weighting, and

4. (4) using the max-min paired elimination method for aggregation.

To illustrate the approach, an example on the evaluation of teaching performance in higher education is solved.     

Finite element programs based on general programming systems

This article describes the advantages and inconveniences with a finite element programming system, i.e. blocks of routines already thoroughly tested, which has to be built together by a programmer to a finite element program. This program may be a tailor-made program to fit a special problem or a general purpose finite element program.

The programming system used as an example in this article consists of

1. *NORSAM—finite element programming system

2. *DASA — pre- and postprocessors

3. *ELLIB—element library

Together they form a complete set of subroutines from datageneration through the necessary routines for matrix manipulation to presentation of results, including the multilevel superelement technique.

Reference to finite element programs applying the programming system concept, is given at the end of the article. Among others, programs for buckling, elasto-plastic analysis of 3-dimensional membranes and solids, nonlinear pipeline problems, acoustic field problems and transient heat conduction in solids are developed. The multilevel superelement technique has been applied in several of these application programs.

The concept of the programming system gives undoubtedly a large saving of time and resources and has proved to be more reliable than conventional methods when developing finite element programs.     

On extended P4-reducible and extended P4-sparse graphs

A graph G was defined in [16] as P₄-reducible, if no vertex in G belongs to more than one chordless path on four vertices or P₄. A graph G is defined in [15] as P₄-sparse if no set of five vertices induces more than one P₄, in G. P₄-sparse graphs generalize both P₄-reducible and the well known class of p₄-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P₄-sparse and extended P₄-sparse graphs.

In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of P₄-sparse and a unique tree representation of P₄-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16–19]. The tree representation of an n-vertex P₄-sparse or a P₄-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP-complete on general graphs.

Finally, by relaxing the restriction concerning the exclusion of the C₅ cycles from P₄-sparse and P₄-reducible graphs, we introduce the class of the extended P4-sparse and the class of the extendedP₄-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs.     

A Monadic Second-Order Definition of the Structure of Convex Hypergraphs

We consider finite hypergraphs with hyperedges defined as sets of vertices of unbounded cardinality. Each such hypergraph has a unique modular decomposition, which is a tree, the nodes of which correspond to certain subhypergraphs (induced by certain sets of vertices called strong modules) of the considered hypergraph. One can define this decomposition by monadic second-order (MS) logical formulas. Such a hypergraph is convex if the vertices are linearly ordered in such a way that the hyperedges form intervals. Our main result says that the unique linear order witnessing the convexity of a prime hypergraph (i.e., of one, the modular decomposition of which is trivial) can be defined in MS logic. As a consequence, we obtain that if a set of bipartite graphs that correspond (in the usual way) to convex hypergraphs has a decidable monadic second-order theory (which means that one can decide whether a given MS formula is satisfied in some graph of the set) then it has bounded clique-width. This yields a new case of validity of a conjecture which is still open.     

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two 1

In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.     

An analysis of research topics in software engineering – 2006

This paper is the first in a new annual series whose goal is to answer the following question: what are the active research focuses within the field of software engineering? We considered 7 top journals and 7 top international conferences in software engineering and examined all the 691 papers published in these journals or presented at these conferences in 2006. Consequently, we have a number of findings.

(1) Seventy-three percent of journal papers focus on 20% of subject indexes in software engineering, including Testing and Debugging (D.2.5), Management (D.2.9), and Software/Program Verification (D.2.4).

(2) Eighty-nine percent of conference papers focus on 20% of subject indexes in software engineering, including Software/Program Verification (D.2.4), Testing and Debugging (D.2.5), and Design Tools and Techniques (D.2.2).

(3) Seventy-seven percent of journal/conference papers focus on 20% of subject indexes in software engineering, including Testing and Debugging (D.2.5), Software/Program Verification (D.2.4), and Management (D.2.9).

(4) The average number of references cited by a journal paper is about 33, whereas this number becomes around 24 for a conference paper.

Two minimum spanning forest algorithms on fixed-size hypercube computers

Two parallel algorithms for finding minimum spanning forest (MSF) of a weighted undirected graph on hypercube computers, consisting of a fixed number of processors, are presented. One algorithm is suited for sparse graphs, the other for dense graphs. Our design strategy is based on successive elimination of non-MSF edges. The input graph is partitioned equally among different processors, which then repeatedly eliminate non-MSF edges and merge results to gradually construct the desired MSF of the entire graph. Low communication overhead is achieved by restricting the message-flow to between the neighboring processors in the hypercube topology. The correctness of our approach is due to a theorem which states that with total-ordered edges, if an edge of an arbitrary subgraph does not belong to its MSF, then it does not belong to the MSF of the entire graph. For a graph of n vertices and m edges, our first algorithm finds an MSF in O(m log m)/p) time using p processors for p ≤ (mlog m)/n(1+log(m/n)). The second algorithm, efficient for dense graphs, requires O(n²/p) time for p≤n/log n.     

Verification in loosely synchronous queue-connected discrete timed automata

We look at a model of a queue system that consists of the following components:

1. Two discrete timed automata W (the “writer”) and R (“the reader”).

2. One unrestricted queue that can be used to send messages from W to R. There is no bound on the length of the queue.

W and R do not share a global clock and operate in a loosely synchronous way. That is, the absolute value of the difference between the local time of W and the local time of R is always bounded by a positive constant. We show that the binary reachability for these systems is effectively computable, and this result is generalized to the case when there are two queues (one from W to R and the other from R to W) that operate in half-duplex. We then present some properties (e.g., safety, invariance, etc.) that can be verified for loosely synchronous queue-connected discrete timed automata and give an example of a system composed of a sensor and a controller that is verifiable using our results.     

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

Hierarchical decompositions of graphs are interesting for algorithmic purposes. There are several types of hierarchical decompositions. Tree decompositions are the best known ones. On graphs of tree-width at most k , i.e., that have tree decompositions of width at most k , where k is fixed, every decision or optimization problem expressible in monadic second-order logic has a linear algorithm. We prove that this is also the case for graphs of clique-width at most k , where this complexity measure is associated with hierarchical decompositions of another type, and where logical formulas are no longer allowed to use edge set quantifications. We develop applications to several classes of graphs that include cographs and are, like cographs, defined by forbidding subgraphs with ``too many' induced paths with four vertices. Received April 13, 1998, and in revised form June 22, 1999, and in final form August 20, 1999.