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]

Abstract: In this paper, we are interested in computability aspects of subshifts and in particular Turing degrees of two-dimensional subshifts of finite type (SFTs) (i.e., tilings). To be more precise, we prove that, given any class of , there is an SFT such that is recursively homeomorphic to , where is a computable set of points. As a consequence, if contains a computable member, and have the exact same set of Turing degrees. On the other hand, we prove that, if contains only non-computable members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs. [Copyright &y& Elsevier]

Abstract: A Catalan pair is a pair of binary relations satisfying some axioms. These pairs are enumerated by the well-known Catalan numbers, and have been introduced in Disanto et al. (2010) [2] with the aim of giving a common language to many structures counted by Catalan numbers. Here, a simple method is given to pass from the recursive definition of a generic Catalan structure to the recursive definition of the Catalan pair on the same structure, thus giving an automatic way of interpreting Catalan structures in terms of Catalan pairs. Our method is applied to several well-known Catalan structures, focusing on the combinatorial meaning of the relations and in each case considered. [Copyright &y& Elsevier]

Abstract: We study aspects of computability concerning random events and variables in a computable probability space which fulfills certain computability axioms. To this end, we introduce two multirepresentations of random events and random variables respectively, employing the Fréchet–Nikodym metric and the Ky Fan metric. They are shown to be recursively complete in guaranteeing computability of basic operations on random events and random variables. Some natural variations of the multirepresentation of random variables are defined for the integrable variables to explore computability of integration. [Copyright &y& Elsevier]

Abstract: We study the derivational complexities of string rewriting systems. We discuss the following fundamental question: which functions can be derivational complexities of terminating finite string rewriting systems? They are recursive, but for any recursive function, there is a derivational complexity larger than it. We relate them to the time functions of Turing machines. In particular, we show that the functions and for a real number are equivalent to the derivational complexity of some finite string rewriting systems if the computational complexity of is relatively low (for example, is rational, algebraic, or ). On the other hand, they cannot be equivalent to any derivational complexities if the complexity of is high. [Copyright &y& Elsevier]

Abstract: We prove several decidability and undecidability results for -PN, an extension of P/T nets with pure name creation and name management. We give a simple proof of undecidability of reachability, by reducing reachability in nets with inhibitor arcs to it. Thus, the expressive power of -PN strictly surpasses that of P/T nets. We encode -PN into Petri Data Nets, so that coverability, termination and boundedness are decidable. Moreover, we obtain Ackermann-hardness results for all our decidable decision problems. Then we consider two properties, width-boundedness and depth-boundedness, that factorize boundedness. Width-boundedness has already been proven to be decidable. Here we prove that its complexity is also non-primitive recursive. Then we prove undecidability of depth-boundedness. Finally, we prove that the corresponding “place version” of all the boundedness problems is undecidable for -PN. These results carry over to Petri Data Nets. [Copyright &y& Elsevier]

Abstract: We consider the rewrite system with as its single rewrite rule, where the signature consists of the variable binding operator commonly denoted by , first-order symbols, which in this paper are restricted to a binary function symbol , and possibly some constant symbols. This kernel system denoting recursively defined objects occurs in several contexts, e.g. it is the framework of recursive types, with as the function type constructor. For general signatures, this rewriting system is widely used to represent and manipulate infinite regular trees. The main concern of this paper is the convertibility relation for -terms as given by the -rule, in particular, its decidability. This relation is sometimes called weak -equality, in contrast with strong -equality, which is given by the equality of the possibly infinite tree unwinding of -terms. While strong equality has received much attention, the opposite is the case for weak -equality. We present three alternative proofs for decidability of weak -equality. The first two proofs build upon an ingenious proof method of Cardone and Coppo. Prior to that, we prepare the way by an analysis of -conversion. We then give a decidability proof in an ‘-free’ manner, essentially treating -terms as first-order terms, and next, a proof in higher-order style, employing -equivalence classes and viewing as a higher-order rewriting system. The third decidability proof is also derived in an -free manner, exploiting the regular nature of the set of -reducts, enabling an appeal to the theory of tree automata. We conclude with additional results concerning decidability of reachability, and upward-joinability of -reduction, and of convertibility by -free -reduction. [Copyright &y& Elsevier]

Abstract: A widely accepted method to specify (possibly infinite) behaviour is to define it as the solution, in some process algebra, of a recursive specification, i.e., a system of recursive equations over the fundamental operations of the process algebra. The method only works if the recursive specification has a unique solution in the process algebra; it is well-known that guardedness is a sufficient requirement on a recursive specification to guarantee a unique solution in any of the standard process algebras. In this paper we investigate to what extent guardedness is also a necessary requirement to ensure unique solutions. We prove a theorem to the effect that all unguarded recursive specifications over have infinitely many solutions in the standard models for . In contrast, we observe that there exist recursive specifications over , necessarily involving parallel composition, that have a unique solution, or finitely many solutions in the standard models for . [Copyright &y& Elsevier]

Abstract: We propose a formal definition of Wolfram’s notion of computational processes based on iterated transducers together with a weak observer, a model of computation that captures some aspects of physics-like computation. These processes admit a natural classification into decidable, intermediate and complete, where intermediate processes correspond to recursively enumerable sets of intermediate degree in the classical setting. It is shown that a standard finite injury priority argument will not suffice to establish the existence of an intermediate computational process. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider insertion–deletion P systems with priority of deletion over insertion. We show that such systems with one-symbol context-free insertion and deletion rules are able to generate Parikh sets of all recursively enumerable languages (). If a one-symbol one-sided context is added to the insertion or deletion rules, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important, and in its absence the corresponding class of P systems is strictly included in the family of matrix languages (). [ABSTRACT FROM AUTHOR]

Abstract: Multi-head finite automata were introduced and first investigated by Rabin and Scott in 1964 and Rosenberg in 1966. Since that time, a vast literature on computational and descriptional complexity issues on multi-head finite automata documenting the importance of these devices has been developed. Although multi-head finite automata are a simple concept, their computational behavior can be already very complex and leads to undecidable or even non-semi-decidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. Additionally the conversions between different types of multi-head finite automata induce in most cases size bounds that cannot be bounded by any recursive function, so-called non-recursive trade-offs. These strong negative results trigger the study of subclasses and alternative characterizations of multi-head finite automata for a better understanding of the nature of non-recursive trade-offs and, thus, the borderline between decidable and undecidable problems. In the present paper, we tour a fragment of this literature. [ABSTRACT FROM AUTHOR]

Abstract: We present a formalization and a formal total correctness proof of a MiniSAT-like SAT solver within the system Isabelle/HOL. The solver is based on the DPLL procedure and employs most state-of-the-art SAT solving techniques, including the conflict-guided backjumping, clause learning, and the two-watched unit propagation scheme. A shallow embedding into Isabelle/HOL is used and the solver is expressed as a set of recursive HOL functions. Based on this specification, the Isabelle’s built-in code generator can be used to generate executable code in several supported functional languages (Haskell, SML, and OCaml). The SAT solver implemented in this way is, to our knowledge, the first fully formally and mechanically verified modern SAT solver. [Copyright &y& Elsevier]

Abstract: It is well known that one can use an adaptation of the inverse-limit construction to solve recursive equations in the category of complete ultrametric spaces. We show that this construction generalizes to a large class of categories with metric-space structure on each set of morphisms: the exact nature of the objects is less important. In particular, the construction immediately applies to categories where the objects are ultrametric spaces with ‘extra structure’, and where the morphisms preserve this extra structure. The generalization is inspired by classical domain-theoretic work by Smyth and Plotkin. For many of the categories we consider, there is a natural subcategory in which each set of morphisms is required to be a compact metric space. Our setting allows for a proof that such a subcategory always inherits solutions of recursive equations from the full category. As another application, we present a construction that relates solutions of generalized domain equations in the sense of Smyth and Plotkin to solutions of equations in our class of categories. Our primary motivation for solving generalized recursive metric-space equations comes from recent and ongoing work on Kripke-style models in which the sets of worlds must be recursively defined. We show a series of examples motivated by this line of work. [ABSTRACT FROM AUTHOR]

Abstract: In this work we provide a combinatorial analysis of bucket recursive trees, which have been introduced previously as a natural generalization of the growth model of recursive trees. Our analysis is based on the description of bucket recursive trees as a special instance of the so-called bucket increasing trees, which is a family of combinatorial objects introduced in this paper. Using this combinatorial description we obtain exact and limiting distribution results for the parameter depth of a specified element, descendants of a specified element and degree of a specified element. [Copyright &y& Elsevier]

Abstract: In the context of 2-player removal games, we define the notion of invariant game for which each allowed move is independent of the position it is played from. We present a family of invariant games which are variations of Wythoff’s game. The set of -positions of these games is given by a pair of complementary Beatty sequences related to the irrational quadratic number . We also provide a recursive characterization of this set. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate various decision problems concerning parameterized versions of some classes of machines. Let be the class of nondeterministic multitape Turing machine (TM) acceptors with a two-way read-only input, at most states, at most read–write worktapes, and at most symbols in the worktape alphabet, where are fixed positive integers. There is no restriction on the cardinality of the input alphabet. We are able to show the emptiness, disjointness, and universe (also called universality) problems to be decidable for . For the class consisting of machines in that always halt or whose minimal-time accepting computations can be bounded by some recursive function (where is the input length), the containment and equivalence problems are decidable. These results hold for other machines, e.g., when the worktapes are pushdown stacks (where on every step, each pushdown can only pop the top of the stack or replace the top of the stack by at most two symbols) or when stacks are counters (where on every step, a counter can be incremented by 1, decremented by 1, or remain unchanged, and can be tested for zero). Our results are the best possible in the sense that not parameterizing one of (or, in the case of counter machines, allowing the counters to increment by arbitrary integers that may change from machines to machines) makes the universe problem undecidable. We also give a simple characterization of the languages defined by . Finally, we investigate the applicability of our techniques to machines with multiple input heads or multiple input tapes. [Copyright &y& Elsevier]

Abstract: We give an algorithm for deciding productivity of a large and natural class of recursive stream definitions. A stream definition is called ‘productive’ if it can be evaluated continually in such a way that a uniquely determined stream in constructor normal form is obtained as the limit. Whereas productivity is undecidable for stream definitions in general, we show that it can be decided for ‘pure’ stream definitions. For every pure stream definition the process of its evaluation can be modelled by the dataflow of abstract stream elements, called ‘pebbles’, in a finite ‘pebbleflow net(work)’. And the production of a pebbleflow net associated with a pure stream definition, that is, the amount of pebbles the net is able to produce at its output port, can be calculated by reducing nets to trivial nets. [Copyright &y& Elsevier]

Abstract: Using a predicate transformer semantics of programs, we introduce statements for heap operations and separation logic operators for specifying programs that manipulate pointers. We prove a powerful Hoare total correctness rule for mutually recursive procedures manipulating pointers. The rule combines earlier proof rules for (mutually) recursive procedures with the frame rule for pointer programs. The theory, including the proofs, is implemented in the theorem prover PVS. In this implementation program variables and addresses can store values of almost any type of the theorem prover. [Copyright &y& Elsevier]

Abstract: Studying the learnability of classes of recursive functions has attracted considerable interest for at least four decades. Starting with Gold’s (1967) model of learning in the limit, many variations, modifications and extensions have been proposed. These models differ in some of the following: the mode of convergence, the requirements intermediate hypotheses have to fulfill, the set of allowed learning strategies, the source of information available to the learner during the learning process, the set of admissible hypothesis spaces, and the learning goals. A considerable amount of work done in this field has been devoted to the characterization of function classes that can be learned in a given model, the influence of natural, intuitive postulates on the resulting learning power, the incorporation of randomness into the learning process, the complexity of learning, among others. On the occasion of Rolf Wiehagen’s 60th birthday, the last four decades of research in that area are surveyed, with a special focus on Rolf Wiehagen’s work, which has made him one of the most influential scientists in the theory of learning recursive functions. [Copyright &y& Elsevier]

Abstract: Being motivated by John Tantalo’s Planarity Game, we consider straight line plane drawings of a planar graph with edge crossings and wonder how obfuscated such drawings can be. We define , the obfuscation complexity of , to be the maximum number of edge crossings in a drawing of . Relating to the distribution of vertex degrees in , we show an efficient way of constructing a drawing of with at least edge crossings. We prove bounds for an -vertex planar graph with minimum vertex degree . The shift complexity of , denoted by , is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If , then is linear in the number of vertices due to the known fact that the matching number of is linear. However, in the case we notice that can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing of a planar graph, it is NP-hard to find an optimum sequence of shifts making crossing-free. [Copyright &y& Elsevier]

Abstract: Many attempts to transcend the fundamental limitations to computability implied by the Halting Problem for Turing Machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. Thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. Here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability. [Copyright &y& Elsevier]

This paper considers when one can invert general recursive operators which map a class of functions to . In this regard, we study four different notions of inversion. We additionally consider enumeration of operators which cover all general recursive operators which map to in the sense that, for every general recursive operator mapping to , there is a general recursive operator in the enumerated sequence which behaves the same way as on . Three different possible types of enumeration are studied. [Copyright &y& Elsevier]

This paper proves two results. (1) Given two bounded context-free languages, it is recursively decidable whether or not there exists a regular language which includes the first and is disjoint with the second and (2) given two rational-ary bounded relations it is recursively decidable whether or not there exists a recognizable relation which includes the first and is disjoint with the second. [Copyright &y& Elsevier]

Let and be any two distinct nodes of an undirected graph , which is-connected. For , a-container of a-connected graph is a set of-disjoint paths joining and . A-container of is a-container if it contains all the nodes of . A graph is-connected if there exists a-container between any two distinct nodes. A bipartite graph is-laceable if there exists a-container between any two nodes from different parts of . Let and be two disjoint graphs with . Let , and is a bijection. Let . The set of-dimensional hypercube-like graph is defined recursively as (a) , complete graph with two nodes, and (b) if and are in , then is in . Let and is bipartite and . In this paper, we show that every graph in is-laceable for every , . It is shown that a constructed-graph can not be-connected. In addition, we show that every graph in is-connected for every , . [Copyright &y& Elsevier]

Abstract: An -bit Gray code is a circular listing of all -bit binary strings in which consecutive strings differ at exactly one bit. For , an -antipodal Gray code is a Gray code in which the complement of any string appears steps away from the string, clockwise or counterclockwise. Killian and Savage proved that an -antipodal Gray code exists when is a power of 2 or , and does not exist for or odd . Motivated by these results, we prove that for odd , an -antipodal Gray code exists if and only if . For even , we establish two recursive constructions for codes from smaller . Consequently, various -antipodal Gray codes are found for even ’s. Examples are for with odd and when , for when with , for when (an alternative proof for Killian and Savage’s result) …etc. [Copyright &y& Elsevier]

Abstract: Higher dimensional automata (HDA) represent a promising tool for modelling (“true”) concurrency in a both combinatorial and topological framework. Within these models, fast algorithms investigating deadlocks and unreachable regions have been devised previously on a background of easily understandable “directed” geometric ideas. In this article, we modify notions and methods from homotopy theory to define and investigate “essentially different” schedules in a HDA and to detect whether two given runs are essentially different using an algorithm again based on “directed geometry”. [Copyright &y& Elsevier]

Abstract: The two determinization procedures of Safra and Muller–Schupp for Büchi automata are compared, based on an implementation in a program called OmegaDet. [Copyright &y& Elsevier]

Abstract: Many problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global) pushdown games is known to be EXPTIME-complete, we show reachability in modular games to be NP-complete. We present a fixed-point computation algorithm for solving modular games such that in the worst case the number of iterations is exponential in the total number of returned values from the modules. If the strategy within a module does not depend on the global history, but can remember the history of the past invocations of this module, that is, if memory is local but persistent, we show that reachability becomes undecidable. [Copyright &y& Elsevier]

Abstract: We present an analog and machine-independent algebraic characterization of elementarily computable functions over the real numbers in the sense of recursive analysis: we prove that they correspond to the smallest class of functions that contains some basic functions, and closed by composition, linear integration, and a simple limit schema. We generalize this result to all higher levels of the Grzegorczyk Hierarchy. This paper improves several previous partial characterizations and has a dual interest: [ ] Concerning recursive analysis, our results provide machine-independent characterizations of natural classes of computable functions over the real numbers, allowing to define these classes without usual considerations on higher-order (type 2) Turing machines. [ ] Concerning analog models, our results provide a characterization of the power of a natural class of analog models over the real numbers and provide new insights for understanding the relations between several analog computational models. [Copyright &y& Elsevier]

Abstract: This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i.e., learning with anomalies. Learning from positive data only and from both positive and negative data is distinguished. The following learning models are studied: learning in the limit, finite identification, set-driven learning, conservative inference, and behaviorally correct learning. The attention is focused on the case that the number of allowed anomalies is finite but not a priori bounded. However, results for the special case of learning with an a priori bounded number of anomalies are presented, too. Characterizations of the learning models with anomalies in terms of finite tell-tale sets are provided. The observed varieties in the degree of recursiveness of the relevant tell-tale sets are already sufficient to quantify the differences in the corresponding learning models with anomalies. Finally, a complete picture concerning the relations of all models of learning with and without anomalies mentioned above is derived. [Copyright &y& Elsevier]

Abstract: This paper proves the decidability of several problems in the theory of HD , and PD systems, some of which that have been proved before but are now proved in a different way. First, the paper tackles the decidability of the nilpotency of HD systems and the infinitude of PD languages. Then, we prove the decidability of the problem of momentary stagnation of the growth function of PD systems. Finally, we suggest a way to solve the decidability of the momentary stagnation of the growth function of systems, proving the decidability of the infinitude of HD as a trivial consequence. [Copyright &y& Elsevier]

Stream X-machines are a formalisation of extended finite state machines that have been used to specify systems. One of the great benefits of using stream X-machines, for the purpose of specification, is the associated test generation technique which produces a test that is guaranteed to determine correctness under certain design for test conditions. This test generation algorithm has recently been extended to the case where the specification is non-deterministic. However, the algorithms for testing from a non-deterministic stream X-machine currently have limitations: either they test for equivalence, rather than conformance or they restrict the source of non-determinism allowed in the specification. This paper introduces a new test generation algorithm that overcomes both of these limitations, for situations where the implementation is known to be deterministic. [Copyright &y& Elsevier]

Let K be the two-dimensional grid. Let q be an integer greater than 1 and let Q={0,…,q-1}. Let s : Q→Q be defined by s(α)=(α+1) mod q, ∀α ∈ Q.In this work we study the following dynamic F on QZ2. For x ∈ QZ2 we define Fv(x)=s(xv) if the state s(xv) appears in one of the four neighbors of v in K and Fv(x)=xv otherwise.For x ∈ QZ2, such that {v∈Z2 : xv ≠ 0} is finite we prove that there exists a finite family of cycles such that the period of every vertex of K divides the lcm of their lengths. This is a generalization of the same result known for finite graphs. Moreover, we show that this upper bound is sharp. We prove that for every n⩾1 and every collection k1,…,kn of non-negative integers there exists yn ∈ QZ2 such that |{v∈Z2 : ynv ≠ 0}| = O(k12+⋯+kn2) and the period of the vertex (0,0) is p·lcm{k1,…,kn}, for some even integer p. [Copyright &y& Elsevier]