Fundamenta Informaticae - Volume 83, issue 1-2

Article Type: Other

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. i-ii, 2008

Authors: Archibald, Margaret | Brattka, Vasco | Heuberger, Clemens

Article Type: Research Article

Abstract: The ordinary notion of algorithmic randomness of reals can be characterised as Martin-Löf randomness with respect to the Lebesgue measure or as Kolmogorov randomness with respect to the binary representation. In this paper we study the question of how the notion of algorithmic randomness induced by the signed-digit representation of the real numbers is related to the ordinary notion of algorithmic randomness. We first consider the image measure on real numbers induced by the signed-digit …representation. We call this measure the signed-digit measure and using the Fourier transform of this measure and the Riemann-Lebesgue Lemma we prove that this measure is not absolutely continuous with respect to the Lebesgue measure. We also show that the signed-digit measure can be obtained as a weakly convergent convolution of discrete measures and therefore, by the classical Theorem of Jessen and Wintner the Lebesgue measure is not absolutely continuous with respect to the signed-digitmeasure. Finally, we provide an invariance theoremwhich shows that if a computable map preserves Martin-Löf randomness, then its induced image measure has to be absolutely continuous with respect to the target space measure. This theorem can be considered as a loose analog for randomness of the Banach-Mazur theorem for computability. Using this Invariance Theorem we conclude that the notion of randomness induced by the signed-digit representation is incomparable with the ordinary notion of randomness. Show more

Keywords: Algorithmic randomness, computable analysis, signed-digit representation, Stern-Brocot tree, Farey fractions, Stern's diatomic sequence

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

Authors: Bienvenu, Laurent | Merkle, Wolfgang | Shen, Alexander

Article Type: Research Article

Abstract: A few years ago a nice criterion of Martin-Löf randomness in terms of plain (neither prefix nor monotone) Kolmogorov complexity was found (among many other results, it is published in [5]). In fact Martin-Löf came rather close to the formulation of this criterion around 1970 (see [4] and [7], p. 98); a version of it that involves both plain and prefix complexity1 was proven by Gacs in 1980 ([2], remark after corollary 5.4 on p. 391). …We provide a simple proof of this criterion that uses only elementary arguments very close to the original proof of Levin-Schnorr criterion of randomness (1973) in terms of monotone complexity ([3, 6]). Show more

Keywords: Martin-Löf randomness, Kolmogorov complexity

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 21-24, 2008

Authors: Bridges, D.S. | Vîţă, L.S.

Article Type: Research Article

Abstract: A notion of connectedness is introduced into the theory of apartness spaces, and various fundamental properties of connected sets are established.

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 25-34, 2008

Authors: Dassow, Jürgen | Stiebe, Ralf

Article Type: Research Article

Abstract: We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals necessary to generate a language. More specifically, we consider the behaviour of this measure with respect to language-theoretic operations. For given numbers c_1 , c_2 , …, c_n and an n-ary operation τ on language, we discuss the range of Var (τ(L_1 ,L_2 ,…L_n )) …where for 1 ⩽i⩽n, L_i is a context-free language with Var (L_i ) = c_i . The operations under discussion are the six AFL-operations: union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets. Show more

Keywords: context-free languages, descriptional complexity, AFL operations

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 35-49, 2008

Authors: Fernau, Henning | Stiebe, Ralf

Article Type: Research Article

Abstract: This paper generalizes the concept of blind multicounter languages to infinite words. We introduce two different acceptance modes of blind multicounter machines on ω-words, called synchrononous and asynchronous acceptance. These acceptance modes are compared with each other and with families of ω-languages of the form L = ∪_{1⩽i⩽k} U_i V^ω_i , where U_i , V_i are finitary blind multicounter languages.

Keywords: blind counter machines, ω-languages, closure properties

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 51-64, 2008

Authors: Freund, Rudolf | Oswald, Marion

Article Type: Research Article

Abstract: We investigate finite extended spiking neural P systems as acceptors for infinite sequences of symbols 1 and 0, i.e., of ω-words over {0, 1}. We show that regular ω-languages over {0, 1} can be characterized by deterministic/non-deterministic finite extended spiking neural P systems accepting ω-words in specific modes with respect to the infinite sequence of states the finite extended spiking neural P systems go through during the accepting computations.

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 65-73, 2008

Authors: Gao, Yuan | Salomaa, Kai | Yu, Sheng

Article Type: Research Article

Abstract: The state complexity of two combined operations, star of catenation and star of reversal, on regular languages is considered in this paper. Tight bounds are obtained for both combined operations. The results clearly show that the state complexity of a combined operation can be very different from the composition of the state complexities of its participating individual operations. A new approach for research in automata and formal language theory is also explained.

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 75-89, 2008

Authors: Gulliver, T. Aaron | Makwakwa, Isaiah | Speidel, Ulrich

Article Type: Research Article

Abstract: In a recent report, Gulliver and Speidel showed that complete sets of aperiodic and – in some cases periodic – necklaces can be generated for arbitrary lengths as fixed-length subsets of variable-length T-codes. The T-codes to which they applied this observation were specifically T-codes constructed by systematic T-augmentation, that is by T-augmentation sequences in which each T-expansion parameter is 1 (simple T-augmentation) and where the T-codes A_{(p1,p2,…,pi)} at each Taugmentation level i do not …contain any codewords shorter than pi (strictly minimal T-augmentation). This present paper generalizes their result to arbitrary T-codes and formalizes their earlier result as a special case of the general result. Show more

Keywords: Necklaces, Lyndon words, cyclic equivalence, T-codes, synchronization

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 91-107, 2008

Authors: Gössel, Michael | Sogomonyan, Egor

Article Type: Research Article

Abstract: In this paper a new non-linear error detection code with three non-linear check bits and an even number of k information bits is introduced. The proposed code may be considered as a modified parity code. The parity bit is split into two non-linear check bits and a third non-linear check bit is added. All odd errors are detected with certainty. All (also even) errors of arbitrary multiplicity for which at least one of the information bits is …correct are detected with a probability greater than or equal to 1/2. Show more

Citation: Fundamenta Informaticae, vol. 83, no. 1-2, pp. 109-115, 2008

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