Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc Thesis (...) ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)

The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.

The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive recursive structures, (...) exponential-time structures and structures with honest witnesses. (shrink)

A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable equivalence relation is computably isomorphic to (...) a p-time equivalence relation with standard universe. (shrink)

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective (...) degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring. (shrink)

We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...) example, we give conditions are given under which two isomorphic LOGSPACE structures will have a linear space isomorphism. (shrink)