ﻻ يوجد ملخص باللغة العربية
Classification problems have been introduced by M. Ziegler as a generalization of promise problems. In this paper we are concerned with solvability and unsolvability questions with respect to a given set or language family, especially with cores of unsolvability. We generalize the results about unsolvability cores in promise problems to classification problems. Our main results are a characterization of unsolvability cores via cohesiveness and existence theorems for such cores in unsolvable classification problems. In contrast to promise problems we have to strengthen the conditions to assert the existence of such cores. In general unsolvable classification problems with more than two components exist, which possess no cores, even if the set family under consideration satisfies the assumptions which are necessary to prove the existence of cores in unsolvable promise problems. But, if one of the components is fixed we can use the results on unsolvability cores in promise problems, to assert the existence of such cores in general. In this case we speak of conditional classification problems and conditional cores. The existence of conditional cores can be related to complexity cores. Using this connection we can prove for language families, that conditional cores with recursive components exist, provided that this family admits an uniform solution for the word problem.
A notable feature of the TTE approach to computability is the representation of the argument values and the corresponding function values by means of infinitistic names. Two ways to eliminate the using of such names in certain cases are indicated in
In this paper we collect some open set-theoretic problems that appear in the large-scale topology (called also Asymptology). In particular we ask problems about critical cardinalities of some special (large, indiscrete, inseparated) coarse structures
We study the links between the topological complexity of an omega context free language and its degree of ambiguity. In particular, using known facts from classical descriptive set theory, we prove that non Borel omega context free languages which ar
Existing formalisms for the algebraic specification and representation of networks of reversible agents suffer some shortcomings. Despite multiple attempts, reversible declensions of the Calculus of Communicating Systems (CCS) do not offer satisfacto
Escalation in games is when agents keep playing forever. Based on formal proofs we claim that if agents assume that resource are infinite, escalation is rational.