83 research outputs found
Computability Theory (Dagstuhl Seminar 17081)
No full textComputability is one of the fundamental notions of mathematics and computer science, trying to capture the effective content of mathematics and its applications. Computability Theory explores the frontiers and limits of effectiveness and algorithmic methods. It has its origins in Gödel's Incompleteness Theorems and the formalization of computability by Turing and others, which later led to the emergence of computer science as we know it today. Computability Theory is strongly connected to other areas of mathematics and theoretical computer science. The core of this theory is the analysis of relative computability and the induced degrees of unsolvability; its applications are mainly to Kolmogorov complexity and randomness as well as mathematical logic, analysis and algebra. Current research in computability theory stresses these applications and focuses on algorithmic randomness, computable analysis, computable model theory, and reverse mathematics (proof theory). Recent advances in these research directions have revealed some deep interactions not only among these areas but also with the core parts of computability theory. The goal of this Dagstuhl Seminar is to bring together researchers from all parts of computability theory and related areas in order to discuss advances in the individual areas and the interactions among those
On the computability-theoretic complexity of trivial, strongly minimal models
No full textWe show the existence of a trivial, strongly minimal ( and thus uncountably categorical) theory for which the prime model is computable and each of the other countable models computes 0". This result shows that the result of Goncharov/ Harizanov/ Laskowski/ Lempp/ McCoy ( 2003) is best possible for trivial strongly minimal theories in terms of computable model theory. We conclude with some remarks about axiomatizability
On the complexity of the successivity relation in computable linear orderings
No full textAbstract. In this paper, we solve a long-standing open ques-tion (see, e.g., Downey [6, §7] and Downey and Moses [11]), about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering L has in-finitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing ∆03-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of independent interest. It would seem to promise many further applications
ON THE COMPLEXITY OF THE SUCCESSIVITY RELATION IN COMPUTABLE LINEAR ORDERINGS
No full text In this paper, we solve a long-standing open question (see, e.g. Downey [6, Sec. 7] and Downey and Moses [11]), about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of independent interest. It would seem to promise many further applications. </jats:p
Recommended from our members
Berechenbarkeitstheorie (Computability Theory)
No full text[no abstract available
ON THE COMPUTABILITY-THEORETIC COMPLEXITY OF TRIVIAL, STRONGLY MINIMAL MODELS
No full textAbstract. We show the existence of a trivial, strongly minimal (and thus uncountably categorical) theory for which the prime model is computable and each of the other countable models computes 0 ′ ′. This result shows that the result of Goncharov/Harizanov/Laskowski/Lempp/McCoy [GHLLM03] is best possible for trivial strongly minimal theories in terms of computable model theory. We conclude with some remarks about axiomatizability. Both vector spaces and algebraically closed fields have the property that the uncountable structures in these classes are determined up to isomorphism by their cardinality. Model theory provides a general framework in which to study this behavior. A first order theory T is called κ-categorical (for an infinite cardinal κ) if A ∼ = B whenever A, B | = T and |A | = |B | = κ. Morley [Mo65] proved that if T is categorical in some uncountably cardinality, then it is categorical in all uncountable cardinalities. (We assume here and for the rest of this paper that the language is countable.) Therefore, any ω1-categorical theory has a unique model of each uncountable cardinality
Computability Theory
No full textComputability is one of the fundamental notions of mathematics, trying to capture the effective content of mathematics. Starting from Gödel’s Incompleteness Theorem, it has now blossomed into a rich area with strong connections with other areas of mathematical logic as well as algebra and theoretical computer science
Recommended from our members
Computability Theory
No full textComputability is one of the fundamental notions of mathematics, trying to capture the effective content of mathematics. Starting from Gödel’s Incompleteness Theorem, it has now blossomed into a rich area with strong connections with other areas of mathematical logic as well as algebra and theoretical computer science
Recommended from our members
Computability Theory
No full textComputability and computable enumerability are two of the fundamental notions of mathematics. Interest in effectiveness is already apparent in the famous Hilbert problems, in particular the second and tenth, and in early 20th century work of Dehn, initiating the study of word problems in group theory. The last decade has seen both completely new subareas develop as well as remarkable growth in two-way interactions between classical computability theory and areas of applications. There is also a great deal of work on algorithmic randomness, reverse mathematics, computable analysis, and in computable structure theory/computable model theory. The goal of this workshop is to bring together researchers representing different aspects of computability theory to discuss recent advances, and to stimulate future work
A software implementation and case study application of Lempp’s propositional model of conflict resolution
No full text
Purpose
The starting point of this paper is the propositional model of conflict resolution which was presented and critically discussed in Lempp (2016). Based on this model, a software implementation, called ProCON, is introduced and applied to three scenarios. The purpose of the paper is to demonstrate how ProCON can be used by negotiators and to evaluate ProCON’s practical usefulness as an automated negotiation support system.
Design/methodology/approach
The propositional model is implemented as a computer program. The implementation consists of an input module to enter data about a negotiation situation, an output module to generate outputs (e.g. a list of all incompatible goal pairs or a graph displaying the compatibility relations between goals) and a queries module to run queries on particular aspects of a negotiation situation.
Findings
The author demonstrates how ProCON can be used to capture a simple two-party, non-iterative prisoner’s dilemma, applies ProCON to a contract negotiation between a supplier and a purchaser of goods, and uses it to model the negotiations between the Iranian and six Western governments over Iran’s nuclear enrichment and stockpiling capacities.
Research limitations/implications
A limitation of the current version of ProCON arises from the fact that the computational complexity of the underlying algorithm is EXPTIME (i.e. the computing time required to process information in ProCON grows exponentially with respect to the number of issues fed into the program). This means that computing time can be quite long for even relatively small negotiation scenarios.
Practical implications
The three case studies demonstrate how ProCON can provide support for negotiators in a wide range of multi-party, multi-issue negotiations. In particular, ProCON can be used to visualise the compatibility relations between parties’ goals, generate possible outcomes and solutions and evaluate solutions regarding the extent to which they satisfy the parties’ goals.
Originality/value
In contrast to standard game-theoretic models of negotiation, ProCON does not require users to provide data about their preferences across their goals. Consequently, it can operate in situations where no information about the parties’ goal preferences is available. Compared to game-theoretical models, ProCON represents a more general approach of looking at possible outcomes in the context of negotiations.
</jats:sec
- …
