Fundamenta Informaticae - Volume 30, issue 2

Authors: Basarab, Şerban A.

Article Type: Research Article

DOI: 10.3233/FI-1997-30201

Citation: Fundamenta Informaticae, vol. 30, no. 2, pp. 125-149, 1997

Authors: Findler, Nicholas V.

Article Type: Research Article

Abstract: The danger of getting into a combinatorial explosion has remained probably the most serious impediment to using knowledge-based systems for real-life problems. Justifiable heuristics must cut down the size of potentially huge search spaces to a realistic and manageable size - without jeopardizing the success of finding satisfactory solutions. This paper describes some techniques that have proved to be effective in the operation of two different systems: the Quasi-Optimizer (QO) and the Generalized Production Rule System (GPRS). The QO is a domain-independent automatic knowledge acquisition tool that can obtain, verify, fuse and optimize human expertise. It generates computer models, descriptive …theories, of human decision making strategies, and can also select and combine the best components of several such models into a single strategy which may be considered a normative theory in the statistical sense. The techniques developed to reduce the danger of combinatorial explosion with the QO include selecting the most independent (near-orthogonal) decision variables, chunking conceptually coherent decision variables, eliminating statistical outlier values, and using dynamically evolving experimental designs to result in a near-uniform reliability distribution of the strategy responses. The GPRS can estimate/predict values of hidden variables and can thus serve as a module of an expert system in need of numerical or functional estimates of hidden variable values. (Hidden variables can be observed and measured only intermittently and at irregular points of time and space – in contrast with open variables whose values can be identified at any time and location.) The estimation is based on generalized production rules expressing stochastic and potentially causal relations between known values of hidden variables and certain mathematical properties of the open variable distribution. A multi-dimensional learning process adds to, consolidates and optimizes the generalized rule base. It gradually merges “similar enough” production rules, and eliminates spurious and statistically not justifiable ones. Such processes reduce the danger of combinatorial explosions in knowledge acquisition. Finally, we note that human decision makers appear to resort to similar methods, although in a less systematic manner, when they are confronted with very large decision spaces. Show more

DOI: 10.3233/FI-1997-30202

Citation: Fundamenta Informaticae, vol. 30, no. 2, pp. 151-160, 1997

Authors: Ilie, Lucian

Article Type: Research Article

Abstract: We investigate the computational complexity of the basic type of contextual languages, that is, the ones introduced by Marcus and called subsequently external contextual languages. We prove that the family of languages generated by external contextual grammars with context-free selection contains only polynomial time parsable languages.

DOI: 10.3233/FI-1997-30203

Citation: Fundamenta Informaticae, vol. 30, no. 2, pp. 161-167, 1997

Authors: Kandulski, Maciej

Article Type: Research Article

Abstract: We show that derivation trees in the generalized Lambek calculus can be transformed to a normal form. This fact is employed in the proof of the inclusion of the class of phrase languages generated by categorial grammars based on the generalized Lambek calculus in the class of phrase languages generated by categorial grammars based on the generalized Ajdukiewicz calculus.

Keywords: syntactic calculi, categorial grammars, phrase languages

DOI: 10.3233/FI-1997-30204

Citation: Fundamenta Informaticae, vol. 30, no. 2, pp. 169-181, 1997

Authors: Mäkinen, Erkki | Ţiplea, Ferucio Laurenţiu

Article Type: Research Article

Abstract: We consider here some special forms of ambiguity for pure context-free grammars, namely pattern avoiding ambiguity, pattern preserving ambiguity, pattern ambiguity, and grammar avoiding ambiguity. The first two properties are undecidable for arbitrary pure context-free grammars, and in a particular but general enough case we can effectively decide whether or not a pure context-free grammar is pattern preserving ambiguous.

Keywords: pure contex-free grammar, ambiguity, cryptosystems

DOI: 10.3233/FI-1997-30205

Citation: Fundamenta Informaticae, vol. 30, no. 2, pp. 183-191, 1997

Authors: Llabrés, Mercè | Rosselló, Francesc

Article Type: Research Article

Abstract: The algebraic transformation of hypergraphs, under the so-called double-pushout (DPO) approach, was invented more than two decades ago, and thoroughly developed since then. We introduce in this paper a new approach to DPO algebraic transformation of hypergraphs and, more in general, of unary partial algebras, which generalizes the aforementioned “classical” DPO approach to hypergraph transformation. While the classical approach was based on the (usual) homomorphisms of hypergraphs, our new approach is based on the total conformisms, a type of morphisms of hypergraphs imported from the theory of partial algebras, which can be described, roughly speaking, as those mappings between hypergraphs …that “reflect” the structure of the target object. In this paper we give both an algebraic and an operational characterization of this new DPO transformation, first for unary partial algebras and then, as a particular case, for hypergraphs. We also study its abstract properties related to parallelism and concurrency through the determination of the HLR conditions it satisfies with respect to several natural classes of morphisms. Show more

Keywords: Double-pushout algebraic transformation, partial algebras, hypergraphs, total conformisms

DOI: 10.3233/FI-1997-30206

Citation: Fundamenta Informaticae, vol. 30, no. 2, pp. 193-226, 1997