Catálogo de publicaciones - libros

We introduce the notion of a , a natural way of generalizing the notions of computable model theory to uncountable structures by presenting the finitely generated substructures of effectively. Our discussion emphasizes definitions and examples, but does prove two significant results. First, our notion of -extensional local computability of ensures that the -theory of will be for all  ≤  + 1. Second, our notion of perfect local computability is equivalent (for countable structures) to the classic definition of computable presentability.

I will give a brief account of how I came to introduce the term Hybrid System and to encourage it as a subject of study. I will also discuss what one should understand to pursue the subject fully, and also discuss the lines of development of my joint research with Wolf Kohn in this area. This is an area at the interface of mathematics, computer science, and control engineering, which has been pursued by many in all three areas since its inception. It can be thought of as the subject which deals with the interaction of discrete and continuous processes. This paper is intended to be legible to those without advanced analysis or differential geometry in their background. We concentrate on control, not on logics of hybrid systems, and aim at an audience unfamiliar with control. I make no apologies for not being technical. This is not a survey of the field. For a year 2000 survey see [1]. A survey made now would be very large.

Ballester has shown that the problem of deciding whether a Nash stable partition exists in a hedonic game with arbitrary preferences is NP-complete. In this paper we will prove that the problem remains NP-complete even when restricting to additively separable hedonic games.

Bogomolnaia and Jackson have shown that a Nash stable partition exists in every additively separable hedonic game with preferences. We show that Nash stable partitions is hard in games with symmetric preferences. To be more specific we show that the problem of deciding whether a Nash stable partition exists in an additively separable hedonic game with and preferences is NP-complete. The corresponding problem concerning individual stability is also NP-complete since individually stable partitions are Nash stable and vice versa in such games.

In the information theoretic world, entropy is both the measure of randomness in a source and a lower bound for the compression achievable for that source by any encoding scheme. But when we must restrict ourselves to efficient schemes, entropy no longer captures these notions well. For example, there are distributions with very low entropy that nonetheless look random for polynomial-bound algorithms.

Different notions of computational entropy have been proposed to take the role of entropy in such settings. Results in [GS91] and [Wee04]) suggest that when time bounds are introduced, the entropy of a distribution no longer coincides with the most effective compression for that source.

This paper analyses three measures that try to capture the compressibility of a source, establishing relations and separations between them and analysing the two special cases of the uniform and the universal distribution over binary strings of a fixed size. It is shown that for the uniform distribution the three measures are equivalent and that for there is a clear separation between metric type entropy, and thus pseudo-entropy, and the maximum compressibility of a source.

The common formulation of the Church-Turing thesis runs as follows:

Where by partial function I mean a function from a subset of natural numbers to natural numbers. As most textbooks relate, the thesis makes a connection between an intuitive notion (computable function) and a formal one (Turing machine). The claim is that the definition of a Turing machine captures the pre-analytic intuition that underlies the concept computation. Formulated in this way the Church-Turing thesis cannot be proved in the same sense that a mathematical proposition is provable. However, it can be refuted by an example of a function which is not Turing computable, but is nevertheless calculable by some procedure that is intuitively acceptable.

How do ordinals gauge the strength and computational power of theories and what kind of information can be extracted from this correlation? This will be the guiding question of this talk. The connection between ordinal representation systems and theories is established in ordinal analysis, a central area of proof theory. The origins of proof theory can be traced back to the second problem on Hilbert’s famous list of problems, which called for a proof of consistency of the arithmetical axioms of the reals.

In this paper we introduce computable and time bounded Riemann surfaces, based on the classical abstract definition by charts. Building upon this definition we discuss computable versions of several classical results, such as the existence of complete continuations of holomorphic functions, universal coverings and the uniformization theorem (for some cases).

Though we state most of our results for computable surfaces, many of them can also be transformed to a uniform version, i.e. based on representations of the class of Riemann surfaces (modulo conformal equivalence).

We consider the Sherali-Adams (SA) operator as a proof system for integer linear programming and prove linear lower bounds on the SA rank required to prove both the pigeon hole and least number principles. We also define the size of a SA proof and show that that while the pigeon hole principle requires linear rank, it only requires at most polynomial size.

We present a hierarchy of families between the and levels of the arithmetic hierarchy. The structure of the top five levels of this hierarchy is in some sense similar to the structure of the Chomsky hierarchy, while the bottom levels are reminiscent of the bounded oracle query hierarchy.

Natural computing refers to computation taking place in nature and to humandesigned computation inspired by nature. When complex phenomena going on in nature are viewed as computational processes, our understanding of these phenomena and of the essence of computation is enhanced. On the other hand human-designed computing inspired by nature has had already a big impact on the development of computer science (think, e.g., about neural computing, evolutionary computing, molecular computing and quantum computing).