Decidability questions for some dynamic properties of Petri nets [Abstract of thesis]
Decidable Theories of Preordered Fields.
Deciding inclusion of set constants over infinite non-strict data structures
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...
Deciding whether a relation defined in Presburger logic can be defined in weaker logics
We consider logics on and which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on and which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.
Decision problems among the main subfamilies of rational relations
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...
Decision Theory Based on Non-Additive Measures
Declarative and procedural semantics of fuzzy similarity based unification
In this paper we argue that for fuzzy unification we need a procedural and declarative semantics (as opposed to the two valued case, where declarative semantics is hidden in the requirement that unified terms are syntactically – letter by letter – identical). We present an extension of the syntactic model of unification to allow near matches, defined using a similarity relation. We work in Hájek’s fuzzy logic in narrow sense. We base our semantics on a formal model of fuzzy logic programming extended...
Decomposable cardinals.
Decomposing Baire class 1 functions into continuous functions
It is shown to be consistent that every function of first Baire class can be decomposed into continuous functions yet the least cardinal of a dominating family in is . The model used in the one obtained by adding Miller reals to a model of the Continuum Hypothesis.
Decomposing Borel functions using the Shore-Slaman join theorem
Jayne and Rogers proved that every function from an analytic space into a separable metrizable space is decomposable into countably many continuous functions with closed domains if and only if the preimage of each set under that function is again . Many researchers conjectured that the Jayne-Rogers theorem can be generalized to all finite levels of Borel functions. In this paper, by using the Shore-Slaman join theorem on the Turing degrees, we show the following variant of the Jayne-Rogers theorem...
Decomposition into special cubes and its applications to quasi-subanalytic geometry
The main purpose of this paper is to present a natural method of decomposition into special cubes and to demonstrate how it makes it possible to efficiently achieve many well-known fundamental results from quasianalytic geometry as, for instance, Gabrielov's complement theorem, o-minimality or quasianalytic cell decomposition.
Décompositions d'un intervalle réel et des ensembles de Cantor
Decompositions of a -algebra.
Decompositions of saturated models of stable theories
We characterize the stable theories T for which the saturated models of T admit decompositions. In particular, we show that countable, shallow, stable theories with NDOP have this property.
Decompositions of the plane and the size of the continuum
We consider a triple ⟨E₀,E₁,E₂⟩ of equivalence relations on ℝ² and investigate the possibility of decomposing the plane into three sets ℝ² = S₀ ∪ S₁ ∪ S₂ in such a way that each intersects each -class in finitely many points. Many results in the literature, starting with a famous theorem of Sierpiński, show that for certain triples the existence of such a decomposition is equivalent to the continuum hypothesis. We give a characterization in ZFC of the triples for which the decomposition exists....
Dedekind-Endlichkeit und Wohlordenbarkeit.
Deduction in many-valued logics: a survey.
Deduction over graphs under constraints : a soundness and completeness theorem
Deductive systems of BCK-algebras
In this paper we shall give some results on irreducible deductive systems in BCK-algebras and we shall prove that the set of all deductive systems of a BCK-algebra is a Heyting algebra. As a consequence of this result we shall show that the annihilator of a deductive system is the the pseudocomplement of . These results are more general than that the similar results given by M. Kondo in [7].
Definability and forcing in E-recursion.