Recursos de colección
Plato, Jan von
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.
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.
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 Σ11-complete. This result and proof have a number of nice corollaries: the Scott rank of ℰ is ω1CK+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).
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...
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...
de Queiroz, Ruy J. G. B.