Complétude en théorie sur graphes orientés
Complexité de la famille des ensembles de synthèse d'un groupe abélien localement compact
On montre que si G est un groupe abélien localment compact non diskret à base dénombrable d'ouverts, alors la famille des fermés de synthèse pour l'algèbre de Fourier A(G) est une partie coanalytique non borélienne de ℱ(G), l'ensemble des fermés de G muni de la structure borélienne d'Effros. On généralise ainsi un résultat connu dans le cas du groupe 𝕋.
Complexité de la réduction en logique combinatoire
Complexité de l'arboricité linéaire d'un graphe
Complexité des boréliens à coupes dénombrables
Nous donnons, pour chaque niveau de complexité Γ, une caractérisation du type "test d'Hurewicz" des boréliens d'un produit de deux espaces polonais ayant toutes leurs coupes dénombrables ne pouvant pas être rendus Γ par changement des deux topologies polonaises.
Complexity bound of absolute factoring of parametric polynomials.
Complexity of curves
We show that each of the classes of hereditarily locally connected, finitely Suslinian, and Suslinian continua is Π₁¹-complete, while the class of regular continua is Π₀⁴-complete.
Complexity of some natural problems in automatic structures.
Complexity of some natural problems on the class of computable -algebras.
Complexity of the axioms of the alternative set theory
If T is a complete theory stronger than ZF such that axiom of extensionality for classes + T + is consistent for 1 (each alone), where are normal formulae then we show AST + + scheme of choice is consistent. As a consequence we get: there is no proper -formula in AST + scheme of choice. Moreover the complexity of the axioms of AST is studied, e.gẇe show axiom of extensionality is -formula, but not -formula and furthermore prolongation axiom, axioms of choice and cardinalities are -formulae,...
Complexity of the class of Peano functions
We evaluate the descriptive set theoretic complexity of the space of continuous surjections from to .
Complexity of the decidability of one class of formulas in quantifier-free set theory with a set-union operator.
Complexity of the decidability of the unquantified set theory with a rank operator.
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.
Complicated BE-algebras and characterizations of ideals
In this paper, using the notion of upper sets, we introduced the notions of complicated BE-Algebras and gave some related properties on complicated, self-distributive and commutative BE-algebras. In a self-distributive and complicated BE-algebra, characterizations of ideals are obtained.
Composition of axial functions of products of finite sets
We show that every function f: A × B → A × B, where |A| ≤ 3 and |B| < ω, can be represented as a composition f₁ ∘ f₂ ∘ f₃ ∘ f₄ of four axial functions, where f₁ is a vertical function. We also prove that for every finite set A of cardinality at least 3, there exist a finite set B and a function f: A × B → A × B such that f ≠ f₁ ∘ f₂ ∘ f₃ ∘ f₄ for any axial functions f₁, f₂, f₃, f₄, whenever f₁ is a horizontal function.
Composition of shape generators
Compositions of ternary relations
In this paper, we introduce six basic types of composition of ternary relations, four of which are associative. These compositions are based on two types of composition of a ternary relation with a binary relation recently introduced by Zedam et al. We study the properties of these compositions, in particular the link with the usual composition of binary relations through the use of the operations of projection and cylindrical extension.