Fundamenta Informaticae - Volume 83, issue 1-2

Authors: Hay, Nicholas J.

Article Type: Research Article

Abstract: In Algorithmic Information Theory, the algorithmic complexity of a sequence is the length of the shortest program which generates it. Is there a measure of the complexity of a computer? We define the simulation complexity of a computer to be the least cost of simulating that computer on a fixed universal computer. We generalise this to processes, computers which can have potentially infinite output (e.g. monotone Turingmachines). Thismeasure has monotone complexity as a special case. …Simulation complexity has applications to sequence prediction, leading to a clarification of a central prediction error inequality and a stronger form of dominance. Enumerable semimeasures are functions which represent sequence predictors. These semimeasures can be in turn represented by processes. A universal process generates a universal semimeasure: one that outperforms any other predictor but for a cost depending on how complex that predictor is. This extra cost is exactly the simulation complexity of the predictor. Show more

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 117-140, 2008

Authors: Hertling, Peter | Spandl, Christoph

Article Type: Research Article

Abstract: First, we analyse the computability theoretic relationship between the defining set S of a "gap shift" and the language of the gap shift. Therefore, we look at various computability theoretic conditions that the set S of a gap shift or the language of a gap shift might satisfy: decidability, computable enumerability, and computable enumerability of the complement. Then we look at the topological entropy of a gap shift and analyse the relationship between on the one …hand the various kinds of computability theoretic conditions on a gap shift that we just mentioned and on the other hand various kinds of computability theoretic conditions on the entropy resp. on any real number in the unit interval: computability, left-computability, and right-computability. Show more

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 141-157, 2008

Authors: Jain, Sanjay | Stephan, Frank | Nan, Ye

Article Type: Research Article

Abstract: This work extends studies of Angluin, Lange and Zeugmann on how learnability of a language class depends on the hypothesis space used by the learner. While previous studies mainly focused on the case where the learner chooses a particular hypothesis space, the goal of this work is to investigate the case where the learner has to cope with all possible hypothesis spaces. In that sense, the present work combines the approach of Angluin, Lange and Zeugmann …with the question of how a learner can be synthesized. The investigation for the case of uniformly r.e. classes has been done by Jain, Stephan and Ye [6]. This paper investigates the case for indexed families and gives a special attention to the notions of conservative and non U-shaped learning. Show more

Keywords: Inductive inference, prescribed learning, uniform learning, indexed families, conservative learning

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 159-175, 2008

Authors: Ryabko, Boris

Article Type: Research Article

Abstract: We consider finite-alphabet and real-valued time series and the following four problems: i) estimation of the (limiting) probability P(x_0 … x_s ) for every s and each sequence x_0 … x_s of letters from the process alphabet (or estimation of the density p(x_0 , …, x_s ) for real-valued time series), ii) the so-called on-line prediction, where the conditional probability P(x_{t+1} ∣x_1 …x_2 … x_t ) (or the conditional density P(x_{t+1} ∣x_1 x_2 … x_t )) should be estimated, where x_1 x_2 … x_t are given, iii) regression and iv) classification (or so-called problems with side information). We show that Kolmogorov complexity (KC) and universal codes (or universal data compressors), whose codeword length can be considered as an estimation of KC, can be used as a basis for constructing asymptotically optimal methods for the above problems. (By definition, a universal code can "compress" any sequence generated by a stationary and ergodic source asymptotically to the Shannon entropy of the source.) Show more

Keywords: time series, nonparametric estimation, universal coding, data compression, on-line prediction, Shannon entropy, stationary and ergodic process, regression

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 177-196, 2008

Authors: Selivanov, Victor L. | Wagner, Klaus W.

Article Type: Research Article

Abstract: We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular ω-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi automata (respectively, for the nondeterministic Rabin, Muller, Mostowski and Büchi automata). For the deterministic Rabin and Streett automata and for the nondeterministic Streett automata upper and lower complexity bounds for the topological properties are established.

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 197-217, 2008

Authors: Zheng, Xizhong

Article Type: Research Article

Abstract: Computably enumerable (c.e., for short) reals are the limits of computable increasing sequences of rational numbers. In this paper we introduce the notion of h-bounded c.e. reals by restricting numbers of big jumps in the sequences by the function h and shown an Ershov-style hierarchy of h-bounded c.e. reals which holds even in the sense of Turing degrees. To explore the possible hierarchy of c.e. sets, we look at the h-initially bounded computable sets which restricts …number of the changes of the initial segments. This, however, does not lead to an Ershov-style hierarchy. Finally we show a computability gap between computable reals and the strongly c.e. reals, that is, a strongly c.e. real cannot be approximated by a computable increasing sequence of rational numbers whose big jump numbers are bounded by a constant unless it is computable. Show more

Keywords: c.e. sets, c.e. reals, bounded c.e. reals, Ershov's Hierarchy

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 219-230, 2008