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