Fundamenta Informaticae - Volume 48, issue 1

Authors: Bach, Joscha

Article Type: Research Article

Abstract: The efficiency of textual input of disabled users can be considerably improved by em-ploying prediction methods as they are used in data compression algorithms. In this paper, the application of the PPM algorithm is described along with a technique of utilizing multiple concur-rent prediction models. In a prototypical implementation called PRIS the method has been found to reduce the number of keystrokes necessary to enter textual data by 55 to 62 percent over common …text entry. Compared with zero-order prediction as used in most textual input aids that are currently used, PRIS reduces the number of keystrokes between 12 and 24 percent. Show more

Keywords: Text compression, PPM, Multiple prediction models, Text input, Rehabilitation

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 1-7, 2001

Authors: Frisco, Pierluigi | Zandron, Claudio

Article Type: Research Article

Abstract: A recent result shows that a variant of communicating distributed H system with two components can generate recursive enumerable languages. In this variant the filters are a finite union of sets whose number depends upon the simulated system. We prove here that it is possible to obtain the same result using filters testing the presence of couples of symbols. The number of the couples does not depend upon the simulated systems. Moreover we investigate variants of …communicating distributed H systems with limitations in the redistribution process. Show more

Keywords: Distributed H systems, splicing operation, two symbols filter

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 9-20, 2001

Authors: Koutny, Maciej | Pappalardo, Giuseppe

Article Type: Research Article

Abstract: We investigate the notion that a system is an acceptable implementation of another base or target system, in the case that the two systems (or processes) have different interfaces. For instance, the base processes can be thought of as specifications, or ideal processes operating in an error-free environment, while the implementations model their actual realisations, operating in an error-prone environment and possibly employing a variety of fault-tolerant techniques. Using the CSP model, …we relate implementations and base systems in terms of their observable behaviours. We obtain two fundamental results, viz. realisability and compositionality. The former ensures that implementations may be put to good use, while the latter guarantees that a target composed of several connected subsystems may be implemented by connecting their respective implementations. Show more

Keywords: Theory of parallel and distributed computation, behaviour abstraction, communicating sequential processes, compositionality

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 21-54, 2001

Authors: Meduna, Aleksander | Vurm, Petr

Article Type: Research Article

Abstract: This paper deals with selective substitution grammars. It concentrates on multisequential grammars with homogeneous selectors that have all their activated parts identical. The present paper reduces the number and size of selectors in these grammars. Indeed, it demonstrates that for every phrase-structure grammar, there exists an equivalent multisequential grammar having two homogeneous selectors, either of which has only two activated parts.

Keywords: Selective substitution grammars, multisequential grammars, homogeneous selectors, reduction

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 55-60, 2001

Authors: Nguyen, Hung Son

Article Type: Research Article

Abstract: Some data mining techniques, like discretization of continuous attributes or decision tree induction, are based on searching for an optimal partition of data with respect to some optimization criteria. We investigate the problem of searching for optimal binary partition of continuous attribute domain in case of large data sets stored in relational data bases (RDB). The critical for time complexity of algorithms solving this problem is the number of I/O database operations necessary to construct such …partitions. In our approach the basic operators are defined by queries on the number of objects characterized by means of real value intervals of continuous attributes. We assume the answer time for such queries does not depend on the interval length. The straightforward approach to the optimal partition selection (with respect to a given measure) requires O(N) basic queries, where N is the number of preassumed partition parts in the searching space. We show properties of the basic optimization measures making possible to reduce the size of searching space. Moreover, we prove that using only O(\log N) simple queries, one can construct a partition very close to optimal. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 61-81, 2001

Authors: Tourlakis, George

Article Type: Research Article

Abstract: We show that computability in a type-2 object is p-normal if type-1 partial inputs are computed by ``well-behaved oracles''.

Keywords: Computability, type-2 computability, oracles, p-normality

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 83-91, 2001

Authors: Zhao, Xishun | Ding, Decheng

Article Type: Research Article

Abstract: In this paper, we will place our emphasis on the problem of existence of extensions and on finding more efficient algorithms for computing extensions of nonmonotonic rule systems. First, in order to dedicate further research into nonmonotonic rule systems a new characterization and some new results are given. This characterization and these results lead to new algorithms for computing extensions. Second, a class of nonmonotonic rule systems, called regular nonmonotonic rule systems, is developed. The existence …of extensions and semi-monotonicity of regular nonmonotonic rule systems are proved. Third, we prove that each regular nonmonotonic rule system has at most 1.47^n extensions, where n is the number of elements occurring in the system. Show more

Keywords: Nonmonotonic rule system, Regular nonmonotonic rule system, Extension

Citation: Fundamenta Informaticae, vol. 48, no. 1, pp. 93-106, 2001