Search

Motivated by algorithmic information theory, the problem of program discovery can help find candidates of underlying generative mechanisms of natural and artificial phenomena. The uncomputability of such inverse problem, however, significantly restricts a wider application of exhaustive methods. Here we present a proof of concept of an approach based on IMP, a high-level imperative programming language. Its main advantage is that conceptually complex computational routines are more succinctly expressed, unlike lower-level models such as Turing machines or cellular automata. We investigate if a more expressive higher-level programming language can be more efficient at generating approximations to algorithmic complexity of recursive functions. • We explore an inverse problem for model discovery based on principles of algorithmic information. • The method can help find candidates of underlying generative mechanisms and first principles. • A proof of concept based on IMP, a high-level imperative programming language, is provided. • IMP expressions are succinct, unlike lower-level models such as formal automata. • We investigate if a more expressive higher-level programming language can be more efficient. [ABSTRACT FROM AUTHOR]

A thesis for interaction is proposed as a foundation for theory of interaction. It formulates the minimal content computability and the maximal channel computability of all models of interaction by fixing a minimal model and a maximal model. It is shown that the interactive extensions of the recursive function model, the Turing machine model and the λ -calculus model all fall within the realm of the thesis. A major technical contribution is the design of interpreters in the maximal model for the models that fit in the thesis. [ABSTRACT FROM AUTHOR]

The model of deterministic input-driven multi-counter automata is introduced and studied. On such devices, the input letters uniquely determine the operations on the underlying data structure that is consisting of multiple counters. We study the computational power of the resulting language families and compare them with known language families inside the Chomsky hierarchy. In addition, it is possible to prove a proper counter hierarchy depending on the alphabet size. This means that any input alphabet induces an upper bound which depends on the alphabet size only, such that k + 1 counters are more powerful than k counters as long as k is less than this bound. The hierarchy interestingly collapses at the level of the bound. Furthermore, we investigate the closure properties of the language families. For input-driven multi-counter automata with 0 or 1 counter, we discuss the computational complexity of their decidable problems. For k ≥ 2 counters, the decidability problems of emptiness, finiteness, universality, inclusion, equivalence, regularity, and context-freeness are shown to be non-semidecidable. Finally, we study descriptional complexity aspects of input-driven multi-counter automata. It is shown that a nondeterministic device can be determinized and that 2 n − 1 is a necessary and sufficient blow-up in the number of states for the determinization. For the operational state complexity of deterministic input-driven multi-counter automata under Boolean operations, tight bounds on the number of states are established. Finally, it turns out that the size trade-offs between deterministic input-driven multi-counter automata with k + 1 and k counters are non-recursive, that is, they are not bounded by any recursive function. [ABSTRACT FROM AUTHOR]

We systematically investigate into the online content of finitely generated structures. The online content of a potentially infinite algebraic or combinatorial structure is perhaps best reflected by its PR-degrees (to be defined). We confirm a natural conjecture by showing that the PR-degrees of a finitely generated structure must be dense. Remarkably, we show that PR-degrees of an f.g. structure do not have to be upwards dense. As an application of our techniques, we refute a natural conjecture about honestly generated structures (to be stated). [ABSTRACT FROM AUTHOR]

We focus on total functions in the theory of reversible computational models. We define a class of recursive permutations, dubbed Reversible Primitive Permutations (RPP) which are computable invertible total endo-functions on integers, so a subset of total reversible computations. RPP is generated from five basic functions (identity, sign-change, successor, predecessor, swap), two notions of composition (sequential and parallel), one functional iteration and one functional selection. RPP is closed by inversion and it is expressive enough to encode Cantor pairing and the whole class of Primitive Recursive Functions. [ABSTRACT FROM AUTHOR]

The Kolmogorov complexity of a string x is defined as the length of a shortest program p of x for some appropriate universal machine U , that is, U (p) = x and p is a shortest string with this property. Neither the plain nor the prefix-free version of Kolmogorov complexity are recursive but for both versions it is well-known that there are recursive exact Solovay functions, that is, recursive upper bounds for Kolmogorov complexity that are infinitely often tight. Let a coding function for a machine M be a function f such that f (x) is always a program of x for M. From the existence of exact Solovay functions it follows easily that for every universal machine there is a recursive coding function that maps infinitely many strings to a shortest program. Extending a recent line of research, in what follows it is investigated in which situations there is a coding function for some universal machine that maps infinitely many strings to the length-lexicographically least program. The main results which hold in the plain as well as in the prefix-free setting are the following. For every universal machine there is a recursive coding function that maps infinitely many strings to their least programs. There is a partial recursive coding function (defined in the natural way) for some universal machine that for every set maps infinitely many prefixes of the set to their least programs. Exactly for every set that is Bennett shallow (not deep), there is a recursive coding function for some universal machine that maps all prefixes of the set to their least programs. Differences between the plain and the prefix-free frameworks are obtained by considering effective sequences I 1 , I 2 , ... of mutually disjoint finite sets and asking for a recursive coding function for some universal machine that maps at least one string in each set I n to its least code. Such coding functions do not exist in the prefix-free setting but exist in the plain setting in case the sets I n are not too small. [ABSTRACT FROM AUTHOR]

Abstract An algebra for a functor H is called completely iterative (cia, for short) if every flat recursive equation in it has a unique solution. Every cia is corecursive, i.e., it admits a unique coalgebra-to-algebra morphism from every coalgebra. If the converse also holds, H is called a cia functor. We prove that whenever the base category is hyper-extensive (i.e. countable coproducts are 'well-behaved') and H preserves countable coproducts, then H is a cia functor. Surprisingly few cia functors exist among standard finitary set functors: in fact, the only ones are those preserving coproducts; they are given by X ↦ W × (−) + Y for some sets W and Y. [ABSTRACT FROM AUTHOR]

Abstract W.O. Krawec (2012) [17] introduced a method of analyzing multi-player impartial games, and derived a recursive function capable of determining which of the n players has a winning strategy. The present paper is devoted to "Multi-player End-Nim games", abbreviated by ENim(N , n), assuming that the standard alliance matrix is adopted. The game values of ENim(N , n) are completely determined for three cases n > N + 1 , n = N + 1 and n = N. For the case n < N , by letting d = N − n ≥ 1 , the game values of ENim(n + d , n) are completely determined if n ≥ d + 4. The case 3 ≤ n ≤ d + 3 is more complicated, we present the game values for d = 1. [ABSTRACT FROM AUTHOR]

Abstract We study safety verification for multithreaded programs with recursive parallelism (i.e. unbounded thread creation and recursion) as well as unbounded integer variables. Since the threads in each program configuration are structured in a hierarchical fashion, our model is state-extended ground-tree rewrite systems equipped with shared unbounded integer counters that can be incremented, decremented, and compared against an integer constant. Since the model is Turing-complete, we propose a decidable underapproximation. First, using a restriction similar to context-bounding, we underapproximate the global control by a weak global control (i.e. DAGs possibly with self-loops), thereby limiting the number of synchronisations between different threads. Second, we bound the number of reversals between non-decrementing and non-incrementing modes of the counters. Under this restriction, we show that reachability becomes NP-complete. In fact, it is poly-time reducible to satisfaction over existential Presburger formulas, which allows one to tap into highly optimised SMT solvers. Our decidable approximation strictly generalises known decidable models including (i) weakly-synchronised ground-tree rewrite systems, and (ii) synchronisation/reversal-bounded concurrent pushdown systems with counters. Finally, we show that, when equipped with reversal-bounded counters, relaxing the weak control restriction by the notion of senescence results in undecidability. [ABSTRACT FROM AUTHOR]

We consider parsers of deterministic context-free languages and study the sizes of their syntax checking components. More precisely, we allow the input processing from left to right or, alternatively, from right to left, whatever is best for the given language. As practical examples, we establish an infinite sequence of deterministic context-free languages L k , for k ≥ 1 , such that there is an exponential size trade-off between a deterministic pushdown automaton that reads its input from right to left and another one that reads its input from left to right. Concerning the constructibility of such a parser out of a given deterministic context-free language, it is shown that it is undecidable whether the reversal of a given deterministic context-free language is again deterministic context free. Related to decidability questions, it turns out that the size trade-offs between deterministic pushdown automata that represent the reversals of their accepted languages and deterministic pushdown automata that represent their accepted languages are non-recursive. That is, one can choose an arbitrarily large recursive function ϱ , but the gain in economy of description eventually exceeds ϱ when changing from the former system to the latter. Furthermore, we study the expressive capacity of the family of languages whose reversals are deterministic context free. Finally, we turn to the family of deterministic context-free languages whose reversals are also deterministic context free and collect several of their closure properties. [ABSTRACT FROM AUTHOR]

We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph G into regions of at most r vertices each, for some parameter r < n . The vertex set of the DDG is the set of Θ ( n r − 1 / 2 ) vertices of G that belong to more than one region (boundary vertices). The DDG has Θ ( n ) arcs, such that distances in the DDG are equal to the distances in G . Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra ) runs in O ( n log ⁡ ( n ) r − 1 / 2 log ⁡ r ) time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the log ⁡ n dependency in the running time of the shortest-path algorithm at the price of an additional log ⁡ r factor, making it O ( n r − 1 / 2 log 2 ⁡ r ) . This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems in planar graphs such as minimum-cut, maximum-flow, and shortest paths with negative arc lengths. As immediate applications, we show how to compute maximum flow in directed weighted planar graphs in O ( n log ⁡ p ) time, and minimum st -cut in undirected weighted planar graphs in O ( n log ⁡ log ⁡ p ) time, where p is the minimum number of edges on any path from the source to the sink. We also show how to compute any part of the DDG that corresponds to a region with r vertices and k boundary vertices in O ( r log ⁡ k ) time, which is faster than has been previously known for small values of k . [ABSTRACT FROM AUTHOR]

Among the unsolvable terms of the lambda calculus, the mute ones are those having the highest degree of undefinedness. In this paper, we define for each natural number n , an infinite and recursive set M n of mute terms, and show that it is graph-easy : for any closed term t of the lambda calculus there exists a graph model equating all the terms of M n to t . Alongside, we provide a brief survey of the notion of undefinedness in the lambda calculus. [ABSTRACT FROM AUTHOR]

In this paper we investigate the dependence of recursively enumerable structures on the equality relation which is fixed to a specific r.e. equivalence relation. We compare r.e. equivalence relations on the natural numbers with respect to the amount of structures they permit to represent from a given class of structures such as algebras, permutations and linear orders. In particular, we show that for various types of structures represented, there are minimal and maximal elements. [ABSTRACT FROM AUTHOR]

Coalgebraic games have been recently introduced as a generalization of Conway games and other notions of games arising in different contexts. Using coalgebraic methods, games can be viewed as elements of a final coalgebra for a suitable functor, and operations on games can be analyzed in terms of (generalized) coiteration schemata . Coalgebraic games are sequential in nature, i.e. , at each step either the Left (L) or the Right (R) player moves ( global polarization ); moreover, only a single move can be performed at each step. Recently, in the context of Game Semantics, concurrent games have been introduced, where global polarization is abandoned, and multiple moves are allowed. In this paper, we introduce coalgebraic multigames , which are situated half-way between traditional sequential games and concurrent games: global polarization is still present, however multiple moves are possible at each step, i.e. , a team of L/R players moves in parallel. Coalgebraic operations, such as sum and negation, can be naturally defined on multigames. Interestingly, sum on coalgebraic multigames turns out to be related to Conway's selective sum on games, rather than the usual (sequential) disjoint sum . Selective sum has a parallel nature, in that at each step the current player performs a move in at least one component of the sum game, while on disjoint sum the current player performs a move in exactly one component at each step. A presentation of strategies on coalgebraic games is given via a final coalgebra of a pair of mutually recursive functors, and a suitable notion of simulation. A monoidal closed category of coalgebraic multigames in the vein of a Joyal category of Conway games is then built. The relationship between coalgebraic multigames and games is then formalized via an equivalence of the multigame category and a monoidal closed category of coalgebraic games where tensor is selective sum. [ABSTRACT FROM AUTHOR]

Using denotational semantics tools, Colson and others studied primitive recursive (p.r.) algorithms, proving the “ultimate obstinacy” property, which has as a consequence that many computations cannot be efficiently implemented in a language that faithfully expresses the classical definition of p.r. functions. As shown by Ritchie and Meyer, the class of p.r. functions can also be characterised by the programming language Loop. Our purpose is to show that the informal, but precise, operational description of Loop (and its variants) is sufficient to prove non-trivial time lower bounds of p.r. algorithms. In particular, we present a simple proof of a property which is similar to ultimate obstinacy, namely that every p.r. program that implements a non-trivial function must execute x i + c times the body of some loop instruction, where x i is the initial contents of some fixed input register, and c does not depend on the input values. This and other lower bounds were obtained without using the lambda calculus or systems with functional parameters (such as Gödel system T). If the conditional break and the decrement instructions are included in the Loop language, the ultimate obstinacy property does not hold. In this case, we use another approach for obtaining lower bounds. The unconditional break instruction does not avoid the obstinacy property; it is equivalent (in function and efficiency) to the conditional instruction if-then-else . The efficient implementation of other functions like step ( x ) ( step ( 0 ) = 0 ; step ( x ) = 1 for x ≥ 1 ) and min ⁡ ( x , y ) is also studied. [ABSTRACT FROM AUTHOR]

In 1993, Fernandes and Kanevsky proposed an important structure for interconnection networks, WKR Pyramid Networks ( WKP ( d , t , L ) , for short). These are constructed by taking difference size WK-recursive network ( WK ( d , t n ) , for short) as difference layers. That study discussed the orders, sizes and connectivity of WKP ( d , t , L ) for any integers d ≥ 1 , t ≥ 1 and L ≥ 1 . The basic WK-recursive pyramid, denoted by WKP ( d , L ) , is a basic version of WKP ( d , t , L ) such that t = 1 . In WKP ( d , L ) , each vertex has exactly d children and the n th layer is isomorphic to a WK ( d , n ) . In this paper, we show that WKP ( d , L ) is Hamiltonian-connected for any two integers, d ≥ 3 and L ≥ 1 , and it is also ( d − 2 ) -node Hamiltonian for any two integers, d ≥ 2 and L ≥ 1 . [ABSTRACT FROM AUTHOR]

This paper establishes an upper bound on the size of a concept class with given recursive teaching dimension (RTD, a teaching complexity parameter). The upper bound coincides with Sauer's well-known bound on classes with a fixed VC-dimension. Our result thus supports the recently emerging conjecture that the combinatorics of VC-dimension and those of teaching complexity are intrinsically interlinked. We further introduce and study RTD-maximum classes (whose size meets the upper bound) and RTD-maximal classes (whose RTD increases if a concept is added to them), showing similarities but also differences to the corresponding notions for VC-dimension. Another contribution is a set of new results on maximal classes of a given VC-dimension. Methodologically, our contribution is the successful application of algebraic techniques, which we use to obtain a purely algebraic characterization of teaching sets (sample sets that uniquely identify a concept in a given concept class) and to prove our analog of Sauer's bound for RTD. Such techniques have been used before to prove results relevant to computational learning theory, e.g., by Smolensky [13] , but are not standard in the field. [ABSTRACT FROM AUTHOR]

Partial learning is a criterion where the learner infinitely often outputs one correct conjecture while every other hypothesis is issued only finitely often. This paper addresses two variants of partial learning in the setting of inductive inference of functions: first, confident partial learning requires that the learner also on those functions which it does not learn, singles out exactly one hypothesis which is output infinitely often; second, essentially class-consistent partial learning is partial learning with the additional constraint that on the functions to be learnt, almost all hypotheses issued are consistent with all the data seen so far. The results of the present work are that confident partial learning is more general than explanatory learning, incomparable with behaviourally correct learning and closed under union; essentially class-consistent partial learning is more general than behaviourally correct learning and incomparable with confident partial learning. Furthermore, it is investigated which oracles permit to learn all recursive functions under these criteria: for confident partial learning, some non-high oracles are omniscient; for essentially class-consistent partial learning, all PA-complete and all oracles of hyperimmune Turing degree are omniscient. [ABSTRACT FROM AUTHOR]