Computability

We introduce and study several notions of computability-theoretic reducibility between subsets of ω that are “robust” in the sense that if only partial information is available about the oracle, then partial information can be recovered about the output. These notions are motivated by reductions between Π 2 1 principles in the context of reverse mathematics, where some of our results have already been applied, e.g., by Hirschfeldt and Jockusch [to appear]. Our work also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp [J. Lond. Math. Soc. (2) 85(2) (2012), 472–490].

An α-automaton (for α some ordinal) is an automaton similar to a Muller automaton that processes words of length α. A structure is called α-automatic if it can be presented by α-automata (completely analogous to the notion of automatic structures which can be presented by the well-known finite automata). We call a structure ordinal-automatic if it is α-automatic for some ordinal α. We continue the study of ordinal-automatic structures initiated by Schlicht and Stephan as well as by Finkel and Todorčević. We develop a pumping lemma for α-automata (processing finite α-words, i.e., words of length α that have one fixed letter at all but finitely many positions). Using this pumping, we provide counterparts for the class of ordinal-automatic structures to several results on automatic structures:

∙ Every finite word α-automatic structure has an injective finite word α-automatic presentation for all α < ω 1 + ω ω . This bound is sharp.

∙ We classify completely the finite word ω n -automatic Boolean algebras. Moreover, we show that the countable atomless Boolean algebra does not have an injective finite-word ordinal-automatic presentation.

∙ We separate the class of finite-word ordinal-automatic structures from that of tree-automatic structures by showing that free term algebras with at least 2 generators (and one binary function) are not ordinal-automatic while the free term algebra with countable infinitely many generators is known to be tree-automatic.

∙ For every ordinal α < ω 1 + ω ω , we provide a sharp bound on the height of the finite word α-automatic well-founded order forests.

∙ For every ordinal α < ω 1 + ω ω , we provide a structure F α that is complete for the class of finite-word α-automatic structures with respect to first-order interpretations.

∙ As a byproduct, we also lift Schlicht and Stephans’s characterisation of the injectively finite-word α-automatic ordinals to the noninjective setting.

We provide an automata-theoretic approach to analyzing an abstract channel modeled by a transducer and to characterizing its lossy rates. In particular, we look at related decision problems and show the boundaries between the decidable and undecidable cases. We conduct experiments on several channels and use Lempel–Ziv algorithms to estimate lossy rates of these channels.

We characterize the possibility space of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal combinatorial auctions in a model with two players and two nonidentical items. Our model has multidimensional types, private values, quasilinear preferences for the players with one relaxation – one of the players is subject to a publicly-known budget constraint. We show that the space includes two types of mechanisms: VCG and dictatorial mechanisms. Furthermore when it is publicly known that the budgeted player is not constrained by his budget, VCG uniquely fulfills the basic properties of deterministic, dominant-strategy incentive compatible, individually rational, and Pareto-optimal. When it is publicly known that the budgeted player is constrained on all bundles then only a dictatorial solution will fulfill the above properties. Moreover when it is publicly known that the budgeted player is constrained on the largest bundle there are preferences under which the VCG mechanism uniquely fulfills these properties.