Complément à l'étude des suites de Thue-Morse généralisées
Complete characterization of context-sensitive languages
Complete presentations of Coxeter groups.
Complete subgraphs of bipartite graphs and applications to trace languages
Complexité algébrique
Complexité de l'arboricité linéaire d'un graphe II
Complexité de problèmes liés aux graphes sans circuit
Complexité et automates cellulaires linéaires
Complexité et automates cellulaires linéaires
The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in , and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.
Complexity arguments in algebraic language theory
Complexity aspects of the Helly property: graphs and hypergraphs.
Complexity classes between and
Complexity classes for membrane systems
We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes PSPACE, EXP, and EXPSPACE.
Complexity of boundary graph languages
Complexity of E0L structural equivalence
Complexity of partial inverse assignment problem and partial inverse cut problem
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
Complexity of Stratifications of Semi-Pfaffian Sets.
Complexity of the decidability of the unquantified set theory with a rank operator.
Complexity of -term reductions