Fundamenta Informaticae - Volume 51, issue 4

Authors: Becher, Verónica | Chaitin, Gregory

Article Type: Research Article

Abstract: We consider the notion of algorithmic randomness relative to an oracle. We prove that the probability β that a program for infinite computations (a program that never halts) outputs a cofinite set is random in the second jump of the halting problem. Indeed, we prove that β is exactly as random as the halting probability of a universal machine equipped with an oracle for the second jump of the halting problem, in spite of the fact …that β is defined without considering oracles. Show more

Keywords: randomness, program size complexity, infinite computations

Citation: Fundamenta Informaticae, vol. 51, no. 4, pp. 325-338, 2002

Authors: Denis, François | Lemay, Aurélien | Terlutte, Alain

Article Type: Research Article

Abstract: We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of …transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic construction of the canonical RFSA similar to the subset construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our constructions. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 51, no. 4, pp. 339-368, 2002

Authors: Góra, Grzegorz | Wojna, Arkadiusz

Article Type: Research Article

Abstract: The article describes a method combining two widely-used empirical approaches to learning from examples: rule induction and instance-based learning. In our algorithm (RIONA) decision is predicted not on the basis of the whole support set of all rules matching a test case, but the support set restricted to a neighbourhood of a test case. The size of the optimal neighbourhood is automatically induced during the learning phase. The empirical study shows the interesting fact that it …is enough to consider a small neighbourhood to achieve classification accuracy comparable to an algorithm considering the whole learning set. The combination of k-NN and a rule-based algorithm results in a significant acceleration of the algorithm using all minimal rules. Moreover, the presented classifier has high accuracy for both kinds of domains: more suitable for k-NN classifiers and more suitable for rule based classifiers. Show more

Keywords: machine learning, instance-based learning, rule induction, nearest neighbour method

Citation: Fundamenta Informaticae, vol. 51, no. 4, pp. 369-390, 2002

Authors: Kopeček, Ivan | Novotný, Miroslav

Article Type: Research Article

Abstract: A system of equations is solved where the right side member of any equation is a known string and the left side member is formed by concatenation of some unknown strings. This problem appears in connection with the division of parts of speech into syllable segments.

Keywords: speech part, estimated segment, syllable segment, string, operation of catenation, length of a string, speech synthesis

Citation: Fundamenta Informaticae, vol. 51, no. 4, pp. 391-398, 2002

Authors: Meduna, Alexander | Kolář, Dušan

Article Type: Research Article

Abstract: This paper discusses some simple and natural restrictions of regulated pushdown automata, whose moves are regulated by some control languages. Most importantly, it studies one-turn regulated pushdown automata and proves that they characterize the family of recursively enumerable languages. In fact, this characterization holds even for atomic one-turn regulated pushdown automata of a reduced size. This result is established in terms of acceptance by final state and empty pushdown, acceptance by final …state, and acceptance by empty pushdown. Show more

Keywords: one-turn regulated pushdown automata, reduced and atomic variants, recursively enumerable languages

Citation: Fundamenta Informaticae, vol. 51, no. 4, pp. 399-405, 2002