The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n6), is much lower than that announced for perfect graphs.

Pseudozeros are useful to describe how perturbations of polynomial coefficients affect its zeros. We compare two types of pseudozero sets: the complex and the real pseudozero sets. These sets differ with respect to the type of perturbations. The first set – complex perturbations of a complex polynomial – has been intensively studied while the second one – real perturbations of a real polynomial – seems to have received little attention. We present a computable formula for the real pseudozero set and a comparison between these two pseudozero sets. We conclude that the complex pseudozero sets have to be preferred except when the perturbed real polynomials admit non-real zeros. We also give some applications of pseudozero set in control theory.

We explicit the link between the computer arithmetic problem of providing correctly rounded algebraic functions and some diophantine approximation issues. This allows to get bounds on the accuracy with which intermediate calculations must be performed to correctly round these functions.

In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size d. In a shelf bin packing problem, we have to obtain a shelf packing such that the total size of items and shelf divisors in any bin is at most 1. A dual approximation scheme must obtain a shelf packing of all items into N bins, such that, the total size of all items and shelf divisors packed in any bin is at most 1 + ε for a given ε > 0 and N is the number of bins used in an optimum shelf bin packing problem. Shelf divisors are used to avoid contact between items of different classes and can hold a set of items until a maximum given weight. We also present a dual approximation scheme for the class constrained bin packing problem. In this problem, there is no use of shelf divisors, but each bin uses at most C different classes.

We combine a new data model, where the random classification is subjected to rather weakrestrictions which in turn are based on the Mammen−Tsybakov [E. Mammen and A.B. Tsybakov,Ann. Statis. 27 (1999) 1808–1829; A.B. Tsybakov,Ann. Statis. 32 (2004) 135–166.] small margin conditions,and the statistical query (SQ) model due to Kearns [M.J. Kearns, J. ACM45 (1998) 983–1006] to what we refer to as PAC + SQ model. We generalize the classconditional constant noise (CCCN) model introduced by Decatur [S.E. Decatur, inICML ’97: Proc. of the Fourteenth Int. Conf. on Machine Learn. MorganKaufmann Publishers Inc. San Francisco, CA, USA (1997) 83–91] to the noise modelorthogonal to a set of query functions. We show that every polynomial time PAC + SQ learning algorithm can beefficiently simulated provided that the random noise rate is orthogonal to the queryfunctions used by the algorithm given the target concept. Furthermore, we extend theconstant-partition classification noise (CPCN) model due to Decatur [S.E. Decatur, inICML ’97: Proc. of the Fourteenth Int. Conf. on Machine Learn. MorganKaufmann Publishers Inc. San Francisco, CA, USA (1997) 83–91] to what we call theconstant-partition piecewise orthogonal (CPPO) noise model. We show how statisticalqueries can be simulated in the CPPO scenario, given the partition is known to thelearner. We show how to practically use PAC +SQ simulators in the noise model orthogonal to the query space bypresenting two examples from bioinformatics and software engineering. This way, wedemonstrate that our new noise model is realistic.


 (1) Shepherdson proved that a discrete unitary commutative semi-ring A+ satisfies IE0 (induction scheme restricted to quantifier free formulas) iff A is integral part of a real closed field; and Berarducci asked about extensions of this criterion when exponentiation is added to the language of rings. Let T range over axiom systems for ordered fields with exponentiation; for three values of T we provide a theory $_{\llcorner} T _{\lrcorner}$ in the language of rings plus exponentiation such that the models (A, expA) of $_{\llcorner} T _{\lrcorner}$ are all integral parts A of models M of T with A+ closed under expM and expA = expM | A+. Namely T = EXP, the basic theory of real exponential fields; T = EXP+ the Rolle and the intermediate value properties for all 2x-polynomials; and T = Texp, the complete theory of the field of reals with exponentiation. (2)$_{\llcorner}$Texp$_{\lrcorner}$ is recursively axiomatizable iff Texp is decidable. $_{\llcorner}$Texp$_{\lrcorner}$ implies LE0(xy) (least element principle for open formulas in the language <,+,x,-1,xy) but the reciprocal is an open question. $_{\llcorner}$Texp$_{\lrcorner}$ satisfies “provable polytime witnessing”: if $_{\llcorner} $Texp$_{\lrcorner}$ proves ∀x∃y : |y| < |x|k)R(x,y) (where $|y|:=_{\llcorner}$log(y)$_{\lrcorner}$, k < ω and R is an NP relation), then it proves ∀x R(x,ƒ(x)) for some polynomial time function f. (3) We introduce “blunt” axioms for Arithmetics: axioms which do as if every real number was a fraction (or even a dyadic number). The falsity of such a contention in the standard model of the integers does not mean inconsistency; and bluntness has both a heuristic interest and a simplifying effect on many questions – in particular we prove that the blunt version of $_{\llcorner} $Texp$_{\lrcorner}$ is a conservative extension of $_{\llcorner} $Texp$_{\lrcorner}$ for sentences in ∀Δ0(xy) (universal quantifications of bounded formulas in the language of rings plus xy). Blunt Arithmetics – which can be extended to a much richer language – could become a useful tool in the non standard approach to discrete geometry, to modelization and to approximate computation with reals.


We prove that the Christofides algorithm gives a $\frac{4}{3}$ approximation ratio for the special case of traveling salesman problem (TSP) in which the maximum weight in the given graph is at most twice the minimum weight for the odd degree restricted graphs. A graph is odd degree restricted if the number of odd degree vertices in any minimum spanning tree of the given graph is less than $\frac{1}{4}$ times the number of vertices in the graph. We prove that the Christofides algorithm is more efficient (in terms of runtime) than the previous existing algorithms for this special case of the traveling salesman problem. Secondly, we apply the concept of stability of approximation to this special case of traveling salesman problem in order to partition the set of all instances of TSP into an infinite spectrum of classes according to their approximability.

The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.

Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1.

Given a finite alphabet Σ and a language L ⊆ ∑+, the centralizer of L is defined as the maximal language commuting with it. We prove that if the primitive root of the smallest word of L (with respect to a lexicographic order) is prefix distinguishable in L then the centralizer of L is as simple as possible, that is, the submonoid L*. This lets us obtain a simple proof of a known result concerning the centralizer of nonperiodic three-word languages.

A closed λ-term M is easy if, for anyother closed term N, the lambda theory generated byM = N is consistent. Recently, it has been introduceda general technique to prove the easiness of λ-terms through thesemantical notion of simple easiness. Simple easiness implies easiness and allows to proveconsistency results via construction of suitable filter models ofλ-calculus living in the category of complete partial orderings: givena simple easy term M and an arbitrary closed term N, itis possible to build (in a canonical way) a non-trivial filter model which equates theinterpretation of M and N. The question whether easinessimplies simple easiness constitutes Problem 19 in the TLCA list of open problems. In thispaper we negatively answer the question providing a non-empty co-r.e. (complement of arecursively enumerable) set of easy, but not simple easy, λ-terms.

The paper deals with some classes of two-dimensional recognizable languages of “high complexity”, in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by Matz, introducing a new complexity function. We solve an open question proposed by Matz, showing that all the known necessary conditions for recognizability of a language and its complement are not sufficient. The proof relies on a family of languages defined by functions.

We present a uniform and easy-to-use technique for deciding the equivalence problem for deterministic monadic linear recursive programs. The key idea is to reduce this problem to the well-known group-theoretic problems by revealing an algebraic nature of program computations. We show that the equivalence problem for monadic linear recursive programs over finite and fixed alphabets of basic functions and logical conditions is decidable in polynomial time for the semantics based on the free monoids and free commutative monoids.

The paper treats the question whether there always exists a minimal nondeterministic finite automaton of n states whose equivalent minimal deterministic finite automaton has α states for any integers n and α with n ≤ α ≤ 2n. Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of n and α. However, in order to give an explicit construction of the automata, we increase the input alphabet to exponential sizes. Then we prove that 2n letters would be sufficient but we describe the related automata only implicitly. In the last section, we investigate the above question for automata over binary and unary alphabets.

Various static analyses of functional programming languages that permit infinite data structures make use of set constants like Top, Inf, and Bot, denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. This paper proves decidability, in particular DEXPTIME-completeness, of inclusion of co-inductively defined sets by using algorithms and results from tree automata and set constraints. The test for set inclusion is required by certain strictness analysis algorithms in lazy functional programming languages and could also be the basis for further set-based analyses.

We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.

We present an abstract equational framework for the specification of systems having both observational and computational features. Our approach is based on a clear separation between the two categories of features, and uses algebra, respectively coalgebra to formalise them. This yields a coalgebraically-defined notion of observational indistinguishability, as well as an algebraically-defined notion of reachability under computations. The relationship between the computations yielding new system states and the observations that can be made about these states is specified using liftings of the coalgebraic structure of state spaces to a coalgebraic structure on computations over these state spaces. Also, correctness properties of system behaviour are formalised using equational sentences, with the associated notions of satisfaction abstracting away observationally indistinguishable, respectively unreachable states, and with the resulting proof techniques employing coinduction, respectively induction.

A Message Authentication Code (MAC) is a function that takes a message and a key asparameters and outputs an authentication of the message. MAC are used to guarantee thelegitimacy of messages exchanged through a network, since generating a correctauthentication requires the knowledge of the key defined secretly by trusted parties.However, an attacker with access to a sufficiently large number of message/authenticationpairs may use a brute force algorithm to infer the secret key: from a set containinginitially all possible key candidates, subsequently remove those that yield an incorrectauthentication, proceeding this way for each intercepted message/authentication pair untila single key remains. In this paper, we determine an exact formula for the expected numberof message/authentication pairs that must be used before such form of attack issuccessful, along with an asymptotical bound that is both simple and tight. We conclude byillustrating a modern application where this bound comes in handy, namely the estimationof security levels in reflection-based verification of software integrity.

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The second main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven parity-FBDD.