Search

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]

The present paper investigates the quality of numberings measured in three different ways: (a) the complexity of finding witnesses of Kleene's Recursion Theorem in the numbering; (b) for which learning notions from inductive inference the numbering is an optimal hypothesis space; (c) the complexity needed to translate the indices of other numberings to those of the given one. In all three cases, one assumes that the corresponding witnesses or correct hypotheses are found in the limit and one measures the complexity with respect to the best criterion of convergence which can be achieved. The convergence criteria considered are those of finite, explanatory, vacillatory and behaviourally correct convergence. The main finding is that the complexity of finding witnesses for Kleene's Recursion Theorem and the optimality for learning are independent of each other. Furthermore, if the numbering is optimal for explanatory learning and also allows to solve Kleene's Recursion Theorem with respect to explanatory convergence, then it also allows to translate indices of other numberings with respect to explanatory convergence. [ABSTRACT FROM AUTHOR]

We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O ( n ) attempts. In contrast to this positive result for strings, we find that, in any Kolmogorov numbering, no enumerator of nontrivial size can generate a list containing the minimal index of a given partial-computable function. One cannot even achieve a laconic enumerator for nearly -minimal indices of partial-computable functions. [ABSTRACT FROM AUTHOR]

In this article we suggest a new systematic approach to studying algorithms on algebraic structures via primitive recursion. The approach is designed to fill the gap between abstract computable structure theory and feasible (in the sense of polynomial-time, computational or automatic) algebra. [ABSTRACT FROM AUTHOR]

Hjorth and Nies proposed notions of randomness corresponding to the higher recursion setting. In particular, they defined the notion of Π 1 1 -Martin-Löf randomness. In this article we present examples of Π 1 1 -Martin-Löf random reals which are obtained as measures of Π 1 1 open sets. [ABSTRACT FROM AUTHOR]

This paper proves the completeness of an extension of Hoare's logic and separation logic for pointer programs with mutual recursive procedures. This paper shows the expressiveness of the assertion language as well. This paper achieves a new system by introducing two new inference rules, and removes an axiom that is unsound in separation logic and other redundant inference rules for showing completeness. It introduces a novel expression that is used to describe complete information of a given state in a precondition. This work also uses the necessary and sufficient precondition of a program for the abort-free execution, which enables us to utilize strongest postconditions. [ABSTRACT FROM AUTHOR]

We investigate the common recursive structure of history-dependent dynamic models in science and engineering. We give formal semantics in terms of a hybrid algebraic–coalgebraic scheme, namely course-of-value iteration. This theoretical approach yields categories of observationally equivalent model representations with precise semantic relationships. Along the initial–final axis of these categories, history dependence can appear both literally and transformed into instantaneous state. The framework can be connected to philosophical and epistemological discourse on one side, and to algorithmic considerations for computational modeling on the other. [ABSTRACT FROM AUTHOR]

We elaborate a recursion-theoretic method to define real numbers which are random to any jump of the halting problem. This is obtained by generalizing a result of V. Becher and G. Chaitin dealing with the class of cofinite sets. As in the work of V. Becher and S. Grigorieff (but this time in the context of open sets in Cantor space) appeal to completeness phenomena replaces machine arguments. [ABSTRACT FROM AUTHOR]

We present applicative theories of words corresponding to weak, and especially logarithmic, complexity classes. The theories for the logarithmic hierarchy and alternating logarithmic time formalise function algebras with concatenation recursion as main principle. We present two theories for logarithmic space where the first formalises a new two-sorted algebra which is very similar to Cook and Bellantoni's famous two-sorted algebra B for polynomial time [4] . The second theory describes logarithmic space by formalising concatenation- and sharply bounded recursion. All theories contain the predicates W representing words, and V representing temporary inaccessible words. They are inspired by Cantini's theories [6] formalising B . [ABSTRACT FROM AUTHOR]

We introduce a new symbolic representation of algorithmic game semantics, and show how it can be applied for efficient verification of open (incomplete) programs. The focus is on an Algol-like programming language which contains the core ingredients of imperative and functional languages, especially on its second-order recursion-free fragment with infinite data types. We revisit the regular-language representation of game semantics of this language fragment. By using symbolic values instead of concrete ones, we generalize the standard notions of regular-language and automata representations of game semantics to those of corresponding symbolic representations. In this way programs with infinite data types, such as integers, can be expressed as finite-state symbolic-automata although the standard automata representation is infinite-state, i.e. the standard regular-language representation has infinite summations. Moreover, in this way significant reductions of the state space of game semantics models are obtained. This enables efficient verification of programs by our prototype tool based on symbolic game models, which is illustrated with several examples. [ABSTRACT FROM AUTHOR]

Abstract: The objective of this paper is to prove that the initial Pola setting, with both inductive and coinductive data, is sound for polynomial size (PSIZE). Explicitly this means all programs written in Pola have their output size bounded by a polynomial in their input size. The paper describes the polarized categorical semantics for Pola and establishes the result by providing categorical models for various fragments of Pola which have explicit size bound information built into the maps. To obtain PSIZE soundness for Pola with just inductive data, the semantics in sized sets suffices. Sized sets are sets equipped with a “size map” which associates to each element a size. Size is usually just a natural number but, more generally, the size could be an element of a size rig. A polarized category consists of an opponent and a player category joined by a module. Sized sets can be used to create a polarized category by letting the opponent and module maps be bounded by polynomials while the player category consists of maps bounded by a constant. This gives a Pola setting with inductive data and immediately establishes the PSIZE soundness of the initial Pola setting. The main technical difficulty of the paper is to provide a semantics which correctly models coinductive data as well. For this “amortized” sets are introduced: these are set in which a higher-order size function is associated to each element, which given a size returns a size. This is amortized as one is concerned with the asymptotic behavior of these functions. While amortized sets have coinductive data they are not affine closed: a final step, using equivalence relations, is required to obtain a model which includes this aspect of Pola structure. While PSIZE by itself is a very weak bound it is a crucial step in establishing polynomial space (PSPACE) and polynomial time (PTIME) bounds for these settings. [Copyright &y& Elsevier]

Abstract: In this article we describe three formulations of a multiobjective combinatorial optimization problem, as well as several complexity results and structural properties of these formulations. A multiobjective dynamic programming algorithm is proposed for each of the three formulations. Based on our theoretical and computational results we argue that a clever definition of the recursion, allowing for strong dominance criteria, is crucial in the design of a multiobjective dynamic programming algorithm. [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 introduce and study new combinatorial objects called Dyck tableaux which may be seen as a variant of permutation tableaux. These objects appear in the combinatorial interpretation of the physical model PASEP (Partially Simple Asymmetric Exclusion Process). Dyck tableaux afford a simple recursive structure through the construction of an insertion algorithm. With this tool, we are able to describe statistics which are relevant in the PASEP model, in a more direct way than in previous works. Moreover, we give a new and natural link between permutations and certain labeled Dyck paths known as subdivided Laguerre histories. [Copyright &y& Elsevier]

Abstract: In empirical cognitive science, for human learning, a semantic or behavioral U-shape occurs when a learner first learns, then unlearns, and, finally, relearns, some target concept. Within the formal framework of Inductive Inference, for learning from positive data, previous results have shown, for example, that such U-shapes are unnecessary for explanatory learning, but are necessary for behaviorally correct and non-trivial vacillatory learning. Herein we also distinguish between semantic and syntactic U-shapes. We answer a number of open questions in the prior literature as well as provide new results regarding syntactic U-shapes. Importantly for cognitive science, we see more of a previously noticed pattern that, for parameterized learning criteria, beyond very few initial parameter values, U-shapes are necessary for full learning power. We analyze the necessity of U-shapes in two memory-limited settings. The first setting is Bounded Memory State (BMS) learning, where a learner has an explicitly-bounded state memory, and otherwise only knows its current datum. We show that there are classes learnable with three (or more) memory states that are not learnable non-U-shapedly with any finite number of memory states. This result is surprising, since, for learning with one or two memory states, U-shapes are known to be unnecessary. This solves an open question from the literature. The second setting is that of Memoryless Feedback (MLF) learning, where a learner may ask a bounded number of questions about what data has been seen so far, and otherwise only knows its current datum. We show that there is a class learnable memorylessly with a single feedback query such that this class is not learnable non-U-shapedly memorylessly with any finite number of feedback queries. We employ self-learning classes together with the Operator Recursion Theorem for many of our results, but we also introduce two new techniques for obtaining results. The first is for transferring inclusion results from one setting to another. The main part of the second is the Hybrid Operator Recursion Theorem, which enables us to separate some learning criteria featuring complexity-bounded learners, employing self-learning classes. Both techniques are not specific to U-shaped learning, but applicable for a wide range of settings. [Copyright &y& Elsevier]

Abstract: In this paper we develop an axiomatic approach to structured specifications in which both the underlying logical system and corresponding institution of the structured specifications are treated as abstract institutions, which means two levels of institution independence. This abstract axiomatic approach provides a uniform framework for the study of structured specifications independently from any actual choice of specification building operators, and moreover it unifies the theory and the model oriented approaches. Within this framework we develop concepts and results about ‘abstract structured specifications’ such as co-limits, model amalgamation, compactness, interpolation, sound and complete proof theory, and pushout-style parameterization with sharing, all of them in a top down manner dictated by the upper level of institution independence. [Copyright &y& Elsevier]

Abstract: A -disjoint path cover of a graph is defined as a set of internally vertex-disjoint paths connecting given sources and sinks in such a way that every vertex of the graph is covered by a path in the set. In this paper, we analyze the -disjoint path cover of recursive circulant under the condition that at most faulty vertices and/or edges are removed. It is shown that when , has a -disjoint path cover (of one-to-one type) joining any pair of two distinct source and sink for arbitrary and subject to . In addition, it is proven that when , has a -disjoint path cover (of unpaired many-to-many type) joining any two disjoint sets of sources and sinks for arbitrary and satisfying , in which sources and sinks are freely matched. In particular, the mentioned bounds and of the two cases are shown to be optimal. [Copyright &y& Elsevier]

Abstract: Model checking has proven to be a useful analysis technique not only for concurrent systems, but also for genetic regulatory networks (Grns). Applications of model checking in systems biology have revealed that temporal logics should be able to capture both branching-time and fairness properties (needed for specifying multistability and oscillation properties, respectively). At the same time, they should have a user-friendly syntax easy to employ by non-experts. In this paper, we define Computation Tree Regular Logic (Ctrl), an extension of Ctl with regular expressions and fairness operators that attempts to match these criteria. Ctrl subsumes both Ctl and Ltl, and has a reduced set of temporal operators indexed by regular expressions. We also develop a translation of Ctrl into Hennessy–Milner Logic with Recursion (HmlR), an equational variant of the modal -calculus. This has allowed us to obtain an on-the-fly model checker with diagnostic for Ctrl by directly reusing the verification technology available in the Cadp toolbox. We illustrate the application of the Ctrl model checker by analyzing the Grn controlling the carbon starvation response of Escherichia coli. [Copyright &y& Elsevier]

Abstract: Any mathematical theory of algorithms striving to offer a foundation for programming needs to provide a rigorous definition for an abstract algorithm. The works reported by Girard (1988) in  and by Moschovakis (1989, 1995) in  are among the best examples of such attempts. They both try to offer a mathematically precise and rigorous formulation of an abstract algorithm, intend to keep the algorithmic flavour present and take the notion of recursion as primary and central. The present work is motivated by Girard’s GoI 2 paper (Girard (1988) , which offers a treatment of recursion in terms of fixed points of linear functions. It is situated in the context of the geometry of interaction (GoI) program and is carried out in the concrete setting of the space of bounded linear maps on a Hilbert space. In this paper, we extend the work in Girard (1988)  to the context of traced unique decomposition categories, once again emphasizing the role of abstract trace in the theory of computing. We show that traced unique decomposition categories enriched over partially additive monoids or their variations suffice to axiomatize and hence extend the work in Girard’s GoI 2 paper. The theory developed here allows us to formulate an abstract notion of an algorithm as a pair of morphisms in a traced unique decomposition category, an abstract notion of computation as the execution formula (defined using the trace operator) applied to an algorithm, and finally a notion of deadlock-freeness for algorithms. In addition, we can treat recursive definitions, fixed points and fixed point operators in a uniform way in terms of traced unique decomposition categories. [Copyright &y& Elsevier]

Abstract: It has been previously observed that for many -learnable computable families of computably enumerable (c.e. for short) sets all their computable numberings are evidently -equivalent, i.e. are equivalent with respect to reductions computable in the halting problem. We show that this holds for all -learnable computable families of c.e. sets, and prove that, in general, the converse is not true. In fact there is a computable family of c.e. sets such that all computable numberings of are computably equivalent and is not -learnable. Moreover, we construct a computable family of c.e. sets which is not -learnable though all of its computable numberings are -equivalent. We also give a natural example of a computable -learnable family of c.e. sets which possesses non--equivalent computable numberings. So, for the computable families of c.e. sets, the properties of -learnability and -equivalence of all computable numberings are independent. [Copyright &y& Elsevier]

Abstract: For , we know that the size of a smallest AND/OR/NOT formula computing the Boolean function is exactly : For any , it is at least by the classical Khrapchenko bound, and for we easily obtain a formula of size by writing and recursively expanding We show that for the formula obtained above is an essentially unique one that computes with size . In the equivalent framework of the Karchmer–Wigderson communication game, our result means that an optimal protocol for the parity of variables is essentially unique. [Copyright &y& Elsevier]

Abstract: This work extends studies of Angluin, Lange and Zeugmann on the dependence of learning on the hypothesis space chosen for the language class in the case of learning uniformly recursive language classes. The concepts of class-comprising (where the learner can choose a uniformly recursively enumerable superclass as the hypothesis space) and class-preserving (where the learner has to choose a uniformly recursively enumerable hypothesis space of the same class) are formulated in their study. In subsequent investigations, uniformly recursively enumerable hypothesis spaces have been considered. In the present work, we extend the above works by considering the question of whether learners can be effectively synthesized from a given hypothesis space in the context of learning uniformly recursively enumerable language classes. In our study, we introduce the concepts of prescribed learning (where there must be a learner for every uniformly recursively enumerable hypothesis space of the same class) and uniform learning (like prescribed, but the learner has to be synthesized effectively from an index of the hypothesis space). It is shown that while for explanatory learning, these four types of learnability coincide, some or all are different for other learning criteria. For example, for conservative learning, all four types are different. Several results are obtained for vacillatory and behaviourally correct learning; three of the four types can be separated, however the relation between prescribed and uniform learning remains open. It is also shown that every (not necessarily uniformly recursively enumerable) behaviourally correct learnable class has a prudent learner, that is, a learner using a hypothesis space such that the learner learns every set in the hypothesis space. Moreover the prudent learner can be effectively built from any learner for the class. [Copyright &y& Elsevier]

Abstract: This paper considers a generalization of various communication models based on the P system paradigm where two objects synchronously move across components. More precisely, the model uses blocks of four cells such that pairs of objects from two input cells travel together to target output cells. It is shown that the model introduced, based on interactions between blocks, is complete, being able to generate all recursively enumerable sets of natural numbers. It is also proven that completeness is achievable by using a minimal interaction between blocks, i.e. every pair of cells is the input or output for at most one block. It is also shown that the concepts introduced in this paper to define the model may be simulated by more particular communication primitives, including symport, antiport and uniport rules. This enables us to automatically translate a system using interaction rules in any of minimal symport, minimal antiport or conditional uniport P systems. [Copyright &y& Elsevier]

Abstract: In the past 40 years, research on inductive inference has developed along different lines, e.g., in the formalizations used, and in the classes of target concepts considered. One common root of many of these formalizations is Gold’s model of identification in the limit. This model has been studied for learning recursive functions, recursively enumerable languages, and recursive languages, reflecting different aspects of machine learning, artificial intelligence, complexity theory, and recursion theory. One line of research focuses on indexed families of recursive languages — classes of recursive languages described in a representation scheme for which the question of membership for any string in any of the given languages is effectively decidable with a uniform procedure. Such language classes are of interest because of their naturalness. The survey at hand picks out important studies on learning indexed families (including basic as well as recent research), summarizes and illustrates the corresponding results, and points out links to related fields such as grammatical inference, machine learning, and artificial intelligence in general. [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: In this paper, we investigate reflective inductive inference of recursive functions. A reflective IIM is a learning machine that is additionally able to assess its own competence. First, we formalize reflective learning from arbitrary, and from canonical, example sequences. Here, we arrive at four different types of reflection: reflection in the limit, optimistic, pessimistic and exact reflection. Then, we compare the learning power of reflective IIMs with each other as well as with the one of standard IIMs for learning in the limit, for consistent learning of three different types, and for finite learning. [Copyright &y& Elsevier]

Abstract: We show that for the family of Church–Rosser languages the Higman–Haines sets, which are the sets of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword, cannot be effectively constructed, although both these sets are regular for any language. This nicely contrasts the result on the effectiveness of the Higman–Haines sets for the family of context-free languages. The non-effectiveness is based on a non-recursive trade-off result between the language description mechanism of Church–Rosser languages and the corresponding Higman–Haines sets, which in turn is also valid for all supersets of the language family under consideration, and in particular for the family of recursively enumerable languages. Finally for the family of regular languages we prove an upper and a matching lower bound on the size of the Higman–Haines sets in terms of nondeterministic finite automata. [Copyright &y& Elsevier]

In language learning, strong relationships between Gold-style models and query models have recently been observed: in some quite general setting Gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. These ‘equalities’ hold in the context of learning indexable classes of recursive languages. Former studies on Gold-style learning of such indexable classes have shown that, in many settings, the enumerability of the target class and the recursiveness of its languages are crucial for learnability. Moreover, studying query learning, non-indexable classes have been mainly neglected up to now. So it is conceivable that the recently observed relations between Gold-style and query learning are not due to common structures in the learning processes in both models, but rather to the enumerability of the target classes or the recursiveness of their languages. In this paper, the analysis is lifted onto the context of learning arbitrary classes of recursively enumerable languages. Still, strong relationships between the approaches of Gold-style and query learning are proven, but there are significant changes to the former results. Though in many cases learners of one type can still be replaced by learners of the other type, in general this does not remain valid vice versa. All results hold even for learning classes of recursive languages, which indicates that the recursiveness of the languages is not crucial for the former ‘equality’ results. Thus we analyze how constraints on the algorithmic structure of the target class affect the relations between two approaches to language learning. [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]

Abstract: We introduce a general model of random context multiset grammars as well as the concept of multiset random context checkers and transducers. Our main results show how recursively enumerable sets of finite multisets can be generated using these models of computing; corresponding results for antiport P systems are established, too. [Copyright &y& Elsevier]

Abstract: Inductive inference is concerned with algorithmic learning of recursive functions. In the model of learning in the limit a learner successful for a class of recursive functions must eventually find a program for any function in the class from a gradually growing sequence of its values. This approach is generalised in uniform learning, where the problem of synthesising a successful learner for a class of functions from a description of this class is considered. A common reduction-based approach for comparing the complexity of learning problems in inductive inference is intrinsic complexity. Informally, if a learning problem (a class of recursive functions) A is reducible to a learning problem (a class of recursive functions) B, then a solution for B can be transformed into a solution for A. In the context of intrinsic complexity, reducibility between two classes is expressed via recursive operators transforming target functions in one direction and sequences of corresponding hypotheses in the other direction. The present paper is concerned with intrinsic complexity of uniform learning. The relevant notions are adapted and illustrated by several examples. Characterisations of complete classes finally allow for various insightful conclusions. The connection to intrinsic complexity of non-uniform learning is revealed within several analogies concerning first the structure of complete classes and second the general interpretation of the notion of intrinsic complexity. [Copyright &y& Elsevier]

Abstract: We give “syntactic’’ characterizations of context-sensitive languages (CSLs) in terms of some restricted models of symport/antiport P systems. These are the first such characterizations of CSLs in terms of P systems. In particular, we show the following for any language L over a binary alphabet: [(1)] Let m be any integer . Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with m membranes and multiple number of symbols (objects). Moreover, holding the number of membranes at m, there is an infinite hierarchy in computational power (within the class of binary CSLs) with respect to the number of symbols. [(2)] Let s be any integer . Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with s symbols and multiple number of membranes. Moreover, holding the number of symbols at s, there is an infinite hierarchy in computational power with respect to the number of membranes. (Similar results hold for languages over an alphabet of symbols.) Thus (1) and (2) say that in order for the restricted symport/antiport P systems to accept all binary CSLs, at least one parameter (either the number of symbols or the number of membranes) must grow. These are the first results of their kind in the P systems area. They contrast a known result that (unrestricted) symport/antiport P systems with symbols and membranes accept (or generate) exactly the recursively enumerable sets of numbers even for . We also note that previous characterizations of formal languages in the membrane computing literature are mostly for the Parikh images of languages. Variations of our model yield characterizations of regular languages, languages accepted by one-way space-bounded Turing machines, and recursively enumerable languages. [Copyright &y& Elsevier]

Abstract: An element of an effectively given domain is computable iff its basic Scott open neighbourhoods are recursively enumerable. We thus refer to computable elements as Scott computable and define an element to be Lawson computable if its basic Lawson open neighbourhoods are recursively enumerable. Since the Lawson topology is finer than the Scott topology, a stronger notion of computability is obtained. For example, in the powerset of the natural numbers with its standard effective presentation, an element is Scott computable iff it is a recursively enumerable set, and it is Lawson computable iff it is a recursive set. Among other examples, we consider the upper powerdomain of Euclidean space, for which we prove that Scott and Lawson computability coincide with two notions of computability for compact sets recently proposed by Brattka and Weihrauch in the framework of type-two recursion theory. [Copyright &y& Elsevier]

Abstract: We investigate the descriptional complexity of deterministic two-way -head finite automata (-DHA). It is shown that between non-deterministic pushdown automata and any -DHA, , there are savings in the size of description which cannot be bounded by any recursive function. The same is true for the other end of the hierarchy. Such non-recursive trade-offs are also shown between any -DHA, , and . We also address the particular case of unary languages. In general, it is possible that non-recursive trade-offs for arbitrary languages reduce to recursive trade-offs for unary languages. Here we present huge lower bounds for the unary trade-offs between non-deterministic finite automata and any -DHA, . Furthermore, several known simulation results imply the presented trade-offs for other descriptional systems, e.g., deterministic two-way finite automata with pebbles or with linearly bounded counters. [Copyright &y& Elsevier]

Formal arithmetical system PRAU is defined as an extension of R.L. Goodstein''s system PRA of the primitive recursive arithmetic; it is based on the consideration of functions similar to primitive recursive functions but in general not everywhere defined. It is proved that PRAU is a conservative extension of PRA. Some classes of the program schemes (PRA-schemes and PRAU-schemes) are introduced; it is proved that the classes of functions computable by such schemes coincide with the classes of functions taking part, correspondingly, in PRA and PRAU. [Copyright &y& Elsevier]

In the context of possibly infinite computations yielding finite or infinite (binary) outputs, the space 2⩽ω = 2* ∪ 2ω appears to be one of the most fundamental spaces in Computer Science. Though underconsidered, next to 2ω, this space can be viewed (Section 3.5.2) as the simplest compact space native to computer science.In this paper we study some of its properties involving topology and computability.Though 2⩽ω can be considered as a computable metric space in the sense of computable analysis, a direct and self-contained study, based on its peculiar properties related to words, is much illuminating.It is well known that computability for maps 2ω → 2ω reduces to continuity with recursive modulus of continuity. With 2⩽ω, things get less simple. Maps 2ω → 2⩽ω or 2⩽ω → 2⩽ω induced by input/output behaviours of Turing machines on finite or infinite words—which we call semicomputable maps—are not necessarily continuous but merely lower semicontinuous with respect to the prefix partial ordering on 2⩽ω. Continuity asks for a stronger notion of computability.We prove for (semi)continuous and (semi)computable maps F : I→O with I,O∈{2ω,2⩽ω} a detailed representation theorem (Theorem 81) via functions f : 2* → 2* following two approaches: bottom-up from f to F and top-down from F to f. [Copyright &y& Elsevier]

We introduce a subalgebra BC- of Bellantoni and Cook''s safe-recursion function algebra BC. Functions of the subalgebra have safe arguments that are non-contractible (i.e non-duplicable). We propose a definition of safe and normal variables in light affine logic (LAL), and show that BC- is the largest subalgebra that is interpretable in LAL, relative to that definition. Though BC- itself is not PF complete, there are extensions of it (by additional schemes for defining functions with safe arguments) that are, and are still interpretable in LAL and so preserve PF closure. We focus on one such which is BC- augmented by a definition-by-cases construct and a restricted form of definition-by-recursion scheme over safe arguments. As a corollary we obtain a new proof of the PF completeness of LAL. [Copyright &y& Elsevier]

Two restricted imperative programming languages are considered: One is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. The paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. This gives rise to a uniform measure μ on both loop and stack programs, that is, a function that assigns to each such program P a natural number μ(P) computable from the syntax of P.It is shown that stack programs of μ-measure n compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class En+2. In particular, stack programs of μ-measure 0 compute precisely the polynomial-time computable functions.Furthermore, it is shown that loop programs of μ-measure n compute exactly the functions in En+2. In particular, loop programs of μ-measure 0 compute precisely the linear-space computable functions. [Copyright &y& Elsevier]

We continue from (Ann. Pure Appl. logic 114 (2002) 117) our study of reasoning about recursion equations in rudimentary theories for inductive data, dubbed intrinsic theories. We show that the functions that are provable using unipolar induction are precisely the primitive-recursive functions, where we call an instance of induction unipolar if data predicates do not occur in the induction formula both positively and negatively.Two special cases of this result are well known, namely induction over Σ10 and Π10. Here, however, induction formulas may have unrestricted quantifier alternations as long as those quantifiers that are relativized to data do not violate the prescribed restriction. The main technical challenge is in showing that the functions provable by unipolar induction, even in classical logic, are primitive-recursive.The result is generic with respect to the underlying inductive data, suggesting a potentially useful formalization of primitive-recursive mathematics. [Copyright &y& Elsevier]

The implicit characterizations of the polynomial-time computable functions FP given by Bellantoni–Cook and Leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. Hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. We do so in this paper for Cobham''s definition of FP by bounded recursion and for Bellantoni–Cook''s safe recursion and prove that the resulting classes capture exactly NPMV, the nondeterministic polynomial-time computable partial multifunctions. We also consider the relationship between our schemes and a notion of nondeterministic recursion defined by Leivant and show that the latter characterizes the total functions of NPMV. We view these results as giving evidence that NPMV is the appropriate analog of partial recursive. This view is reinforced by earlier results of Spreen and Stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between NPMV and NP sets. Furthermore, since NPMV is obtained from FP in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that FP is properly seen as playing the role of primitive recursion. [Copyright &y& Elsevier]

Recursion theory on the reals, the analog counterpart of recursive function theory, is an approach to continuous-time computation inspired by the models of Classical Physics. In recursion theory on the reals, the discrete operations of standard recursion theory are replaced by operations on continuous functions such as composition and various forms of differential equations like indefinite integrals, linear differential equations and more general Cauchy problems. We define classes of real recursive functions in a manner similar to the standard recursion theory and we study their complexity. We prove both upper and lower bounds for several classes of real recursive functions, which lie inside the elementary functions, and can be characterized in terms of space complexity. In particular, we show that hierarchies of real recursive classes closed under restricted integration operations are related to the exponential space hierarchy. The results in this paper, combined with earlier results, suggest that there is a close connection between analog complexity classes and subrecursive classes, at least in the region between FLINSPACE and the primitive recursive functions. [Copyright &y& Elsevier]

Within the scope of inductive inference a recursion theoretic approach is used to model learning behaviour. The fundamental model considered is Gold''s identification of recursive functions in the limit. Modifying the corresponding definition has proposed several inference classes, which have been compared regarding the capacities of the relevant learners. The present paper is concerned with a meta-version of this learning model. Given a description of a class of target functions, a uniform learner is supposed to develop a specific successful method for learning the represented class. The same modifications as in the elementary model are considered in the context of uniform learning, especially respecting identification capacities. It turns out that the former separations of inference classes are reflected on the meta-level, in particular finite classes of recursive functions—which constitute the most simple learning problems in the elementary model—are evidence of these separations. [Copyright &y& Elsevier]

We establish a first step towards a “Rice theorem” for tilings: for non-trivial sets, it is undecidable to know whether two different tile sets produce the same tilings of the plane. Then, we study quasiperiodicity functions associated with tilings. This function is a way to measure the regularity of tilings. We prove that, not only almost all recursive functions can be obtained as quasiperiodicity functions, but also, a function which overgrows any recursive function. [Copyright &y& Elsevier]

This paper studies parallel recursion. The trace specification language used in this paper incorporates sequentially, nondeterminism, reactiveness (including infinite traces), three forms of parallelism (including conjunctive, fair-interleaving and synchronous parallelism) and general recursion. In order to use Tarski''s theorem to determine the fixpoints of recursions, we need to identify a well-founded partial order. Several orders are considered, including a new order called the lexical order, which tends to simulate the execution of a recursion in a similar manner as the Egli-Milner order. A theorem of this paper shows that no appropriate order exists for the language. Tarski''s theorem alone is not enough to determine the fixpoints of parallel recursions. Instead of using Tarski''s theorem directly, we reason about the fixpoints of terminating and nonterminating behaviours separately. Such reasoning is supported by the laws of a new composition called partition. We propose a fixpoint technique called the partitioned fixpoint, which is the least fixpoint of the nonterminating behaviours after the terminating behaviours reach their greatest fixpoint. The surprising result is that although a recursion may not be lexical-order monotonic, it must have the partitioned fixpoint, which is equal to the least lexical-order fixpoint. Since the partitioned fixpoint is well defined in any complete lattice, the results are applicable to various semantic models. Existing fixpoint techniques simply become special cases of the partitioned fixpoint. For example, an Egli-Milner-monotonic recursion has its least Egli-Milner fixpoint, which can be shown to be the same as the partitioned fixpoint. The new technique is more general than the least Egli-Milner fixpoint in that the partitioned fixpoint can be determined even when a recursion is not Egli-Milner monotonic. Examples of non-monotonic recursions are studied. Their partitioned fixpoints are shown to be consistent with our intuition. [Copyright &y& Elsevier]

The notions “recursively enumerable” and “recursive” are the basic notions of effectivity in classical recursion theory. In computable analysis, these notions are generalized to closed subsets of Euclidean space using their metric distance functions. We study a further generalization of these concepts to subsets of computable metric spaces. It appears that different characterizations, which coincide in case of Euclidean space, lead to different notions in the general case. However, under certain additional conditions, such as completeness and effective local compactness, the situation is similar to the Euclidean case. We present all results in the framework of “Type-2 Theory of Effectivity” which allows to express effectivity properties in a very uniform way: instead of comparing properties of single subsets, we compare corresponding representations of the hyperspace of closed subsets. Such representations do not only induce a concept of computability for single subsets, but they even yield a concept of computability for operations on hyperspaces, such as union, intersection, etc. We complete our investigation by studying the special situation of compact subsets. [Copyright &y& Elsevier]

In this paper I use the notion of trace defined in (Theoret. Comput. Sci. 266 (2001) 159) to extend Coquand''s constructive proof (C. R. Acad. Sci. Ser. I 314 (1992)) of the ultimate obstination theorem of Colson to the case when mutual recursion is allowed. As a by-product I get an algorithm that computes the value of a primitive recursive combinator applied to lazy integers (infinite or partially undefined arguments may appear). I also get, as Coquand got from his proof, that, even when mutual recursion is allowed, there is no primitive recursive definition f such that f(Sn(⊥))=Sn2(⊥). [Copyright &y& Elsevier]

Multiway decision graphs are a new class of decision graphs for representing abstract states machines. This yields a new verification technique that can deal with the data-width problem by using abstract sorts and uninterpreted functions to represent data value and data operations, respectively. However, in many cases, it may suffer from the non-termination of the state enumeration procedure. This paper presents a novel approach to solving the non-termination problem when the generated set of states, even infinite, represents a structured domain where terms (states) share certain repetitive patterns. The approach is based on the schematization method developed by Chen and Hsiang, namely ρ-terms. Schematization provides a suitable formalism for finitely manipulating infinite sets of terms. We illustrate the effectiveness of our method by several examples. [Copyright &y& Elsevier]

We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class.In the first part of the paper, we consider learning from text and introduce a concept of limit-refuting learning that is intermediate between refuting learning and reliable learning. We give characterizations for these concepts and show some results about their relative strength and their relation to confident learning.In the second part of the paper we consider learning from texts that for some k contain all positive Πk-formulae that are valid in the standard structure determined by the set to be learned. In this model, the following results are shown. For the language with successor, any countable axiomatizable class can be limit-refuting learned from Π1-texts. For the language with successor and order, any countable axiomatizable class can be reliably learned from Π1-texts and can be limit-refuting learned from Π2-texts, whereas the axiomatizable class of all finite sets cannot be limit-refuting learned from Π1-texts. For the full language of arithmetic, which contains in addition plus and times, for any even k there is an axiomatizable class that can be limit-refuting learned from Πk+1-texts but not from Πk-texts. A similar result with k+3 in place of k+1 holds with respect to the language of Presburger''s arithmetic. [Copyright &y& Elsevier]

This paper is concerned with the equational logic of definitions whose semantics is given in terms of final coalgebra maps. The framework for our study is iteration theories (cf. e.g. Bloom and E´sik, Iteration Theories: The Equational Logic of Iterative Processes, EATCS Monographs on Theoretical Computer Science, Springer, Berlin, 1993; Theoret. Comput. Sci. 179 (1–2) (1997)), recently re-introduced as models of the FLR0 fragment of the formal language of recursion (Hurkens et al., J. Symbolic Logic 63 (2) (1998) 45; Mos Chovakis, J. Symbolic Logic 54 (1989) 1216; in: M.L. Dalla Chiara et al. (Eds.), Logic and Scientific Methods, Kluwer, Dordrecht, 1997, p. 179). We present a new class of iteration theories derived from final coalgebras. This allows us to reason with a number of types of fixed-point equations which heretofore seemed to require metric or order-theoretic ideas. All of the work can be done using finality properties and equational reasoning. Having a semantics, we obtain the following completeness result: the equations involving fixed-point terms which are valid for final coalgebra interpretations are exactly those valid in a number of contexts pertaining to recursion. For example, they coincide with the equations valid for least-fixed-point recursion on dcpo's. We also present a new version of the proof of the well-known completeness result for iteration theories (see E´sik, Comput. Linguistics Comput. Languages 4 (1982) 95; Hurkens et al., 1998). Our work brings out a connection between coalgebraic reasoning and recursion. [Copyright &y& Elsevier]