Abstracts of some papers

Abstract :
Let L be the first-order language with identity whose set of specific symbols consists of the binary predicate symbols R_1, ..., R_q. Let A be an L-sentence and let us denote by Gen(A) (generalized spectrum of A) the set of all finite models of A. We say that A represents gen(A). The spectrum S(A) of sentence A is the set of cardinalities of domains of elements of Gen(A) and A is also called a representation of S(A). Let A be some L-sentence and P be a polynomial of degree k of Z[X] asymtotically greater than or equal to identity function on N. We produce a sentence P(A) representing P(S(A)), i.e. S(P(A))=P(S(A)). The algorithm producing P(A) depends only on P and L and effectively one-to-one maps elements of Gen(A) onto elements of Gen(P(A)). This sentence P(A) is formalized in a binary language L* of cardinality 2q+k if k<3 and q+k if k>=3.

Abstract :
The spectrum of a first-order sentence is the set of cardinalities of its finite models. Let S be the set of all spectra. Let RUD be the set of unary rudimentary relations, i.e. defined by a $Delta_0$-formula. It is known that RUD is included in S, but it is unknown whether it is strict. In this paper, we prove that there are one-to-one functions with rudimentary graphs providing representations of various sets of spectra in RUD. These results are obtained by an arithmetical coding of finite structures and by transforming first-order sentences into unary rudimentary formulas describing the same semantical properties. Also, we provide rudimentary definitions of several classic spectra.

Abstract :
The problem SAT of CNF-Satisfiability is the prototype of NP-complete problems. In this problem the question is whether there exists a truth assignment such that each clause contains at least one true literal. Conversely, the problem 1-At-Most-SAT, in which the question is whether there exists a truth assignment so that each clause contains at most one true literal, is polynomial-time decidable. We define an infinite class of problems SAT(L1,... , Lp), parametrized by symmetric polynomial-time decidable languages and generalizing usual satisfiability problems. For instance, the two problems previously considered are respectively parametrized by the languages corresponding to the regular expressions 0*1(0+1)* and 0*+0*10*. We prove a dichotomy theorem for these satisfiability problems with symmetric polynomial clauses : SAT(L1,... , Lp) is either polynomial or NP-complete. We also show a dichotomy result for the corresponding counting problems: #SAT(L1,... , Lp) is either in FP or #P-complete. Besides, we provide a normal form characterization of the symmetric regular languages L leading to a polynomial-time decidable problem SAT(L). This characterization induces an algorithm to decide whether a given problem SAT(L1,... , Lp) is polynomial-time decidable, provided that the languages L1,... , Lp are symmetric and regular.

Abstract :
The aim of this paper is to point out the equivalence between three notions respectively issued from recursivity theory, computational complexity and finite model theory. One the one hand, the rudimentary languages are known to be characterized by the Linear Time Hierarchy. On the other hand, this complexity class can be proved to correspond to monadic second-order logic with addition. Our viewpoint sheds some new light on the close connection between these domains : we bring together the two extremal notions by providing a direct logical characterization of rudimentary languages, and a representation result of second-order logic into these languages. We use natural arithmetical tools, and our proofs contain no ingredient from computational complexity.

Abstract :
Rudimentary relations are those relations over natural integers that are defined by a first-order arithmetical formula, in which all quantifications are bounded by some variables. The question of whether a given primitive recursive relation is rudimentary is in some cases difficult and related to several well-known open questions in theoretical computer science. In this paper, we present systematic tools to study this question, and various applications. One of them provides a sufficient condition of collapsing of the small classes of Grzegorczyk's hierarchy.

Abstract :
We consider the class of regular symmetric languages. When the language is given by a deterministic finite automaton, deciding whether a regular language is symmetric is polynomial. On the opposite, we prove that this question becomes PSPACE-complete when the language is given by a non-deterministic finite automaton or a regular expression. Besides, the complexity of satisfiability problems with symmetric regular clauses has been completely established (P or NP-complete). In this dichotomy result, two classes of symmetric regular languages naturally appear when characterizing the polynomial case: affine and bijunctive languages. A language L is affine (resp. bijunctive) if for all k the set of words of length k of L is exactly the set of solutions (resp. the set of models) of some linear system over GF(2) (resp of some 2CNF formula). We prove that, if the language is given by a deterministic finite automaton, deciding whether a symmetric regular language is affine or bijunctive, that is whether the corresponding satisfiability problem is in P, is polynomial. In addition, we prove that deciding whether a regular language is affine or bijunctive is PSPACE-complete when the language is given by a non-deterministic finite automaton or a regular expression.

Abstract :
In this paper, we investigate several extensions of the Linear Time Hierarchy (denoted by LTH). We first prove that the widespread agreement on LTH machines, which requires that the oracle tape is erased between two successive oracle calls, is useless. We also define a natural counting extension of LTH and show that it corresponds to a robust notion of counting bounded arithmetic predicates. Finally, we show that majority is equivalent to exact counting in both frameworks.

Abstract :
The counting ability of weak formalisms is of interest as a measure of their expressive power. The question was investigated in several papers in complexity theory and in weak arithmetic. In each case, the considered formalism (AC^0-circuits, first-order logic, $\Delta_0$, respectively) was shown to be able to count precisely up to a polylogarithmic number. An essential part of each of the proofs is the construction of a 1-1 mapping from a small subset of $\{0,\ldots,N-1\}$ into a small initial segment. In each case the expressibility of such a mapping depends on some strong argument (group theoretic device or prime number theorem) or intricate construction. We present a coding device based on a collision-free hashing technique, leading to a completely elementary proof for the polylog counting capability of first-order logic (with built-in arithmetic), AC^0-circuits, rudimentary arithmetic, the Linear Time Hierarchy, and monadic-second order logic with addition.

Abstract :
We study the computational complexity of widely used problems of 2D digital topology. We prove that most of the considered problems (including reachability in 2D binary images, connectivity, lower homotopy and tree-homotopy) are in LogSpace. We prove that reachability in 2D binary images is NC^1-hard, and that reachability in permutation graphs is also NC^1-hard. Finaly, we prove that most of the considered problems are not in AC^0.

Back to the list of publications

Back to my homepage