Complexity of -term reductions
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Complexity theoretical results on nondeterministic graph-driven read-once branching programs
Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model is the test whether a given BP is really a BP of model . Here it is proved that the consistency test...
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
Branching programs are a well-established computation model for boolean functions, especially read-once branching programs (BP1s) have been studied intensively. Recently two restricted nondeterministic (parity) BP1 models, called nondeterministic (parity) graph-driven BP1s and well-structured nondeterministic (parity) graph-driven BP1s, have been investigated. The consistency test for a BP-model M is the test whether a given BP is really a BP of model M. Here it is proved that the consistency...
Component composition validation
Many approaches such as component technologies have been invented in order to support software reuse. Based on these technologies a large variety of techniques have been introduced to connect components. However, there is little experience concerning the validation of component systems. We know how to plug components together, but we do need ways to check whether that works. In this paper we introduce an approach to validating component compositions and showing how such a process can be supported...
Composantes préconservatives minimales d'un réseau de Petri : étude structurelle
Composed figures of pixels and inverse monoid. (Figures composées de pixels et monoïde inversif.)
Compositional characterization of observable program properties
Compositional models, Bayesian models and recursive factorization models
Compositional models are used to construct probability distributions from lower-order probability distributions. On the other hand, Bayesian models are used to represent probability distributions that factorize according to acyclic digraphs. We introduce a class of models, called recursive factorization models, to represent probability distributions that recursively factorize according to sequences of sets of variables, and prove that they have the same representation power as both compositional...
Compositional representation of rational functions
Composition/décomposition de réseaux de Pétri et de leurs graphes de couverture
Composition-representative subsets.
Compositions de fonctions de commutation partielle
Compression of satellite data.
In this paper, we present the simple and double compression algorithms with an error control for compressing satellite data corresponding to several revolutions. The compressions are performed by means of approximations in the norm L∞ by finite series of Chebyshev polynomials, with their known properties of fast evaluation, uniform distribution of the error, and validity over large intervals of time. By using the error control here introduced, the number of terms of the series is given automatically...
Computability and Complexity of Ray Tracing.
Computation in Coxeter groups. I: Multiplication.
Computation of centralizers in Braid groups and Garside groups.
We give a new method to compute the centralizer of an element in Artin braid groups and, more generally, in Garside groups. This method, together with the solution of the conjugacy problem given by the authors in [9], are two main steps for solving conjugacy systems, thus breaking recently discovered cryptosystems based in braid groups [2]. We also present the result of our computations, where we notice that our algorithm yields surprisingly small generating sets for the centralizers.
Computation of Period Matrices of Real Algebraic Curves*
Computation of rigidity of order for one simple matrix
We shall compute the exact value of rigidity of the triangular matrix with entries 0 and 1.