Fundamenta Informaticae - Volume 64, issue 1-4

Authors: Pawlak, Zdzisław

Article Type: Research Article

Abstract: This paper concerns a new approach to intelligent data analysis based on information flow distribution study in a flow graph. Branches of a flow graph are interpreted as decision rules, whereas a flow graph is supposed to describe a decision algorithm. We propose to model decision processes as flow graphs and analyze decisions in terms of flow spreading in a graph.

Keywords: Flow graphs, data mining, information flow, intelligent data analysis, Bayes' rule

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 369-377, 2005

Authors: Polkowski, Lech | Semeniuk-Polkowska, Maria

Article Type: Research Article

Abstract: In this paper, dedicated to Professor Solomon Marcus on the occasion of His 80th birthday, we discuss the idea of intensional many-valued logic reflecting the logical content of rough set approach to analysis and treatment of uncertainty. In constructing the variety of logics presented in the paper, we make use of a certain kind of tolerance (similarity) relations called rough mereological tolerances. A study of tolerance relations that arise in rough set environments was initiated in …1994, with the paper [23], in which basic ideas pertaining to tolerance relations in the rough set framework were pointed to. The analysis of the role tolerance relations may play in machine learning based on rough set-theoretic ideas was carried out by Professor Solomon Marcus in His seminal paper, written during His stay in Warsaw in December of the year 1994. At the same time the first author had first ideas related to the applicability of ideas of mereology in the rough set analysis of uncertainty. In a later analysis it has turned out that mereological approach has led to a development of a new paradigm in reasoning under uncertainty, called rough mereology, proposed by Lech Polkowski and Andrzej Skowron. Within this paradigm, one is able to construct a variety of tolerance relations. Those tolerance relations, induced by rough mereological constructs called rough inclusions, serve as a basis for constructing a variety of logics, called rough mereological logics, that are related to the inherent structure of any rough set universe. In this paper, we introduce gradually all essential and necessary notions from the area of rough set theory, mereology and rough mereology, and then we discuss tolerance relations induced by rough inclusions along with some methods for inducing rough inclusions with desired properties. The paper culminates with a discussion of intensional logics based on rough mereological tolerance relations. In this way, we explore one of so many paths in scientific research, that have been either pointed to or threaded by Professor Solomon Marcus. Show more

Keywords: rough mereology, logics for rough sets, similarity relations

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 379-390, 2005

Authors: Salomaa, Arto

Article Type: Research Article

Abstract: We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called γ-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.

Keywords: Subword, scattered subword, number of subwords, Parikh matrix, ambiguity

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 391-404, 2005

Authors: Scollo, Giuseppe

Article Type: Research Article

Abstract: The Collatz problem is comprised of two distinct, separate questions: existence of eventually periodic Collatz reductions with a nontrivial period, and existence of period-free Collatz reductions. This paper introduces a few distinct, related formalizations of the Collatz dynamics as term rewriting systems, using elementary concepts from the theory of state transition dynamics. Some of the subject systems act on finite terms, whereas others rewrite terms that are endowed with a countable, recursively defined …structure. The latter presents a convenient framework for the investigation of extensions of the Collatz dynamics to dense systems. Show more

Keywords: state transition dynamics, attractor, periodicity, quasiperiodicity, infinitary rewriting

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 405-416, 2005

Authors: Skowron, Andrzej

Article Type: Research Article

Abstract: The approximation space definition has evolved in rough set theory over the last 15 years. The aim was to build a unified framework for concept approximations. We present an overview of this evolution together with some operations on approximation spaces that are used in searching for relevant approximation spaces. Among such operations are inductive extensions and granulations of approximation spaces. We emphasize important consequences of the paper for research on approximation of vague concepts and reasoning …about them in the framework of adaptive learning. This requires developing new approach to vague concepts going beyond the traditional rough or fuzzy approaches. Show more

Keywords: vague concept approximation, reasoning about vague concepts, approximation spaces, rough sets, inductive extensions, granulation of approximation spaces, adaptive learning

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 417-431, 2005

Authors: Tatar, Doina

Article Type: Research Article

Abstract: There is a renewed interest in word sense disambiguation (WSD) as it contributes to various applications in natural language processing. In this paper we survey vector-based methods for WSD in machine learning. All the methods are corpus-based and use definition of context in the sense introduced by S. Marcus [11].

Keywords: Word sense disambiguation, machine learning, context

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 433-442, 2005

Authors: Titchener, Mark R. | Nicolescu, Radu | Staiger, Ludwig | Gulliver, Aaron | Speidel, Ulrich

Article Type: Research Article

Abstract: Lempel and Ziv (1976) proposed a computable string production-complexity. In this paper, our emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. We derive expressions for complexity bounds subject to certain constraints. We derive an analytic approximation to the upper bound to linearize the complexity measure. The linearized measure enables us to propose an entropy measure, observed elsewhere to correspond …closely with the Kolmogorov-Sinai entropy in simple dynamical systems. Show more

Keywords: Formal languages, generative systems, prefix codes, complexity measures, T-codes, entropy, information

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 443-461, 2005

Authors: Tomescu, Ioan

Article Type: Research Article

Abstract: Let A be an alphabet of cardinality m, k_n be a sequence of positive integers and ω∈ A* (|ω|=k_n ). In this paper it is shown that if lim sup_{n&rarr;&infin;} k_n /ln n<1/ln m, then almost all words of length n over A contain the factor ω, but if lim sup_{n&rarr;&infin;} k_n /ln n>1/ln m, then this property is not true. Also, if lim inf_{n&rarr;&infin;} …k_n /ln n>1/ln m, then almost all words of length n over A do not contain the factor ω. Moreover, if lim_{n&rarr;&infin;} (ln n-k_n ln m)=α∈ R, then lim sup_{n&rarr;&infin;} |W(n,k_n ,ω,A)| /m^m ≤1−exp (−exp(α)) and lim inf_{n&rarr;&infin;} |W (n, k_n ,ω,A)|/m^n ≥1−exp (−(1−1/m) exp(α)), where W(n, k_n , ω, A) denotes the set of words of length n over A containing the factor ω of length k_n . Show more

Keywords: Word, factor, recurrence relation, characteristic equation, pseudo-Vandermonde determinant, autocorrelation polynomial, generating function

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 463-470, 2005

Authors: Yu, Sheng

Article Type: Research Article

Abstract: In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.

Keywords: State complexity, regular languages, finite languages, finite automata

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 471-480, 2005