Recursos de colección
Plato, Jan von
Gottwald, Siegfried
The last decade has seen an enormous development in infinite-valued
systems and in particular in such systems which have become known as
mathematical fuzzy logics.
¶
The paper discusses the mathematical background for the interest in
such systems of mathematical fuzzy logics, as well as the most
important ones of them. It concentrates on the propositional cases,
and mentions the first-order systems more superficially. The main
ideas, however, become clear already in this restricted setting.
Rubin, Sasha
A structure has a (finite-string) automatic presentation if the
elements of its domain can be named by finite strings in such a way
that the coded domain and the coded atomic operations are recognised
by synchronous multitape automata. Consequently, every structure with
an automatic presentation has a decidable first-order theory. The
problems surveyed here include the classification of classes of
structures with automatic presentations, the complexity of the
isomorphism problem, and the relationship between definability and
recognisability.
Bell, John L.
Viale, Matteo
Jaligot, Eric; Muranov, Alexey; Neman, Azadeh
In continuation of [JOH04, OH07],
we prove that existentially closed CSA-groups have
the independence property.
This is done by showing that there exist words having
the independence property relative to the class of
torsion-free hyperbolic groups.
Cholak, Peter A.; Downey, Rodney; Harrington, Leo A.
The goal of this paper is to announce there is a single orbit of the
c.e. sets with inclusion, ℰ, such that the question of
membership in this orbit is Σ^{1}_{1}-complete. This result and
proof have a number of nice corollaries: the Scott rank of ℰ is
ω_{1}^{CK}+1; not all orbits are elementarily definable; there is no
arithmetic description of all orbits of ℰ; for all finite α
≥ 9, there is a properly Δ^{0}_{α} orbit (from the
proof).
Bonnay, Denis
This paper deals with the problem of giving a principled characterization of the class
of logical constants. According to the so-called Tarski—Sher thesis, an operation is
logical iff it is invariant under permutation. In the model-theoretic tradition, this
criterion has been widely accepted as giving a necessary condition for an operation to
be logical. But it has been also widely criticized on the account that it counts too
many operations as logical, failing thus to provide a sufficient condition. Our aim is
to solve this problem of overgeneration by modifying the invariance criterion. We
introduce a general notion of invariance under a similarity relation and present the
connection...
Pratt-Hartmann, Ian
The numerically definite syllogistic is the fragment of English
obtained by extending the language of the classical syllogism with
numerical quantifiers. The numerically definite relational
syllogistic is the fragment of English obtained by extending the
numerically definite syllogistic with predicates involving transitive
verbs. This paper investigates the computational complexity of the
satisfiability problem for these fragments. We show that the
satisfiability problem (= finite satisfiability problem) for the
numerically definite syllogistic is strongly NP-complete, and that the
satisfiability problem (= finite satisfiability problem)
for the numerically definite relational syllogistic is
NEXPTIME-complete, but perhaps not strongly so. We discuss the related
problem of probabilistic (propositional) satisfiability, and thereby
demonstrate the incompleteness of some proof-systems...
Ito, Takayasu
de Queiroz, Ruy J. G. B.
Hjorth, Greg
Matet, Pierre