Fundamenta Informaticae - Volume 49, issue 4

Authors: Atanasiu, Adrian | Martín-Vide, Carlos | Mateescu, Alexandru

Article Type: Research Article

Abstract: In this paper we investigate the injectivity of the Parikh matrix mapping. This research is done mainly on the binary alphabet. We identify a family of binary words, refered to as ``palindromic amiable'', such that two such words are palindromic amiable if and only if they have the same image by the Parikh matrix mapping. Some other related problems are discussed, too.

Keywords: Parikh matrix, palindrome, scattered subwords

Citation: Fundamenta Informaticae, vol. 49, no. 4, pp. 289-299, 2002

Authors: Bodlaender, Hans L. | Dinneen, Michael J. | Khoussainov, Bakhadyr

Article Type: Research Article

Abstract: In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational problems and processes of infinite duration. We consider the cases (1) where the first player wins when vertices in a specified set are visited infinitely often and vertices in another specified set are visited finitely often, (2) where the first player wins when exactly those …vertices in one of a number of specified disjoint sets are visited infinitely often, and (3) a generalization of these first two cases. We give polynomial time algorithms to determine which player has a winning strategy in each of the games considered. Show more

Keywords: complexity, graph and network algorithms, infinite graph games

Citation: Fundamenta Informaticae, vol. 49, no. 4, pp. 301-312, 2002

Authors: Dziemidowicz, Barbara

Article Type: Research Article

Abstract: In this paper continuing [1], we present a more general approach to restricted optimal unification, introduced and applied to learning algorithms for categorial grammars in [2] and further developed in [7,8,4,5]. We introduce a procedure of finding minimal unifiers with respect to some preordering relation between substitutions and solve a general problem of finding all minimal (in several senses) categorial grammars compatible with a given language sample.

Keywords:

Citation: Fundamenta Informaticae, vol. 49, no. 4, pp. 313-324, 2002

Authors: Johnson, C.A.

Article Type: Research Article

Abstract: The relationship between possible and supported models of unstratified indefinite deductive databases is studied, when disjunction is interpreted inclusively. Possible and supported models are shown to coincide under a suitable definition of supportedness, and the concept of a supported cover is introduced and shown to characterise possible models and facilitate top-down query processing and compilation under the possible model semantics. The properties and query processing of deductive databases under the possible model …semantics is compared and contrasted with the perfect model semantics. Show more

Keywords: Indefinite deductive databases, possible models, stable models, stationary models, supported models, perfect models, supported covers, query processing, query compilation

Citation: Fundamenta Informaticae, vol. 49, no. 4, pp. 325-347, 2002

Authors: Kłopotek, Mieczysław Alojzy

Article Type: Research Article

Abstract: Bayesian networks have many practical applications due to their capability to represent joint probability distribution in many variables in a compact way. There exist efficient reasoning methods for Bayesian networks. Many algorithms for learning Bayesian networks from empirical data have been developed. A well-known problem with Bayesian networks is the practical limitation for the number of variables for which a Bayesian network can be learned in reasonable time. A remarkable exception here is the Chow/Liu …algorithm for learning tree-like Bayesian networks. However, its quadratic time and space complexity in the number of variables may prove also prohibitive for high dimensional data. The paper presents a novel algorithm overcoming this limitation for the tree-like class of Bayesian networks. The new algorithm space consumption grows linearly with the number of variables n while the execution time is proportional to n·ln(n), hence both are better than those of Chow/Liu algorithm. This opens new perspectives in construction of Bayesian networks from data containing tens of thousands and more variables, e.g. in automatic text categorization. Show more

Keywords: machine learning, Bayesian networks, time and space complexity

Citation: Fundamenta Informaticae, vol. 49, no. 4, pp. 349-367, 2002

Authors: Pankowski, Tadeusz

Article Type: Research Article

Abstract: In the paper we deal with the problem of modeling and querying information in schemaless databases of partially labeled objects (PLO-DB). Partially labeled objects are used for modeling data within repositories integrating both structured and semistructured data. The proposed PLO (Partially Labeled Objects) data model originates from the OEM data model and extends it by allowing partial labeling of objects. For PLO-DB we propose a rule-oriented query language PathLog, which data manipulation paradigm is based on …set-theoretical operations and on rules (in Datalog style) involving Skolem functions and referential variables. The main contribution of the paper is the development of a formalized and consistent model of schemaless databases of partially labeled objects and its query language PathLog. Show more

Keywords: schemaless databases, semistructured data, partially labeled objects

Citation: Fundamenta Informaticae, vol. 49, no. 4, pp. 369-395, 2002