Fundamenta Informaticae - Volume 31, issue 1

Authors: Buszkowski, Wojciech | Kołowska-Gawiejnowicz, Mirosława

Article Type: Research Article

Abstract: We prove some theorems on representation of residuated semigroups and monoids in algebras of binary relations. One of them has been proved in Andréka and Mikulás [3], and the others are new, though also closely related to some results in [3]. The main novelty of this paper is a simple method of proof, based upon a construction of canonical models for Lambek calculi by means of labeled formulas, whereas [3] uses graph-theoretic constructions. We handle labeled formulas in a way similar to Kurtonina [15] and the second author [14], but we make no use of Labeled Deductive Systems, which is …an essential simplification. Show more

DOI: 10.3233/FI-1997-3111

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 1-12, 1997

Authors: Esparza, Javier

Article Type: Research Article

Abstract: The paper provides a structural characterisation of the reachable markings of Petri nets in which every transition has exactly one input place. As a corollary, the reachability problem for this class is proved to be NP-complete. Further consequences are: the uniform word problem for commutative context-free grammars is NP-complete; weak-bisimilarity is semidecidable for Basic Parallel Processes.

Keywords: Petri nets, Commutative Context-free Grammars, Basic Parallel Processes, Weak bisimilarity

DOI: 10.3233/FI-1997-3112

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 13-25, 1997

Authors: Grzymala-Busse, Jerzy W.

Article Type: Research Article

Abstract: A new version of the rule induction system LERS is described and compared with the old version of LERS. Experiments were done for comparison of performance for both versions of LERS and the two other rule-induction systems: AQ15 and C4.5. The new LERS system performance is fully comparable with performance of the other two systems.

DOI: 10.3233/FI-1997-3113

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 27-39, 1997

Authors: Koshiba, Takeshi

Article Type: Research Article

Abstract: We study slender context-sensitive languages, i.e., those containing at most a constant number of words of each length. Recently, it was proved that every slender regular language can be described by a finite union of terms of the form uvi w [9] and every slender context-free language can be described by a finite union of terms of the form uvi wxi y [4, 10]. We show a hierarchy of slender languages which is properly contained in the family of context-sensitive languages and which starts with the family of slender context-free languages, or slender regular languages. Each slender context-sensitive language in …the hierarchy can be described by a finite union of terms of the form x1 yi 1 x2 yi 2 ··· xn yi n xn+1 . Show more

Keywords: slender languages, control sets, cryptosystems

DOI: 10.3233/FI-1997-3114

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 41-47, 1997

Authors: Michalski, Ryszard S. | Imam, Ibrahim F.

Article Type: Research Article

Abstract: A decision structure is a simple and powerful tool for organizing a decision process. It differs from a conventional decision tree in that its nodes are assigned tests that can be functions of the attributes, rather than single attributes; the branches stemming from a node can be assigned a subset of attribute values rather than a single attribute value (test outcome); and the leaves can be assigned one or more alternative decisions. We describe a methodology for learning decision structures from declarative knowledge expressed in the form of decision rules. The decision rules are generated by an expert, or by …an AQ-type inductive learning program (with or without constructive induction). From a given set of rules, one can generate many different decision structures. The proposed methodology generates the one that is most suitable for the given decision-making situation, according to a multicriterion evaluation function. Experiments with a program implementing the proposed methodology have demonstrated its many useful features. Show more

Keywords: machine learning, inductive learning, decision structures, decision trees, decision rules, attribute selection, knowledge acquisition, data mining, knowledge discovery

DOI: 10.3233/FI-1997-3115

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 49-64, 1997

Authors: Romanowska, Anna

Article Type: Research Article

Abstract: Snack-algebras - algebras introduced for modelling databases - are shown to be distributive replicas of dissemilattices.

Keywords: incomplete databases, power domains, snack-algebras, (free and distributive) dissemilattices

DOI: 10.3233/FI-1997-3116

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 65-77, 1997

Authors: Lee, Shie-Jue | Lin, Wei-Jer

Article Type: Research Article

Abstract: Zero-defect is extremely important for VLSI designs. Formal techniques for verifying the correctness of logic designs overcome the limits of test case simulation. Many formal systems have been proposed for verification purpose. However, verification of VLSI designs is not enough. It would be equally or more important to correct wrong designs. Little attention has been paid on diagnosis of logic designs. We propose a formal system, based on a propositional logic theorem prover, to verify a combinational logic design and to fix the design if it is incorrect. By referring to the models obtained for an incorrect design and applying …some heuristics, the system can locate errors and correct the design in an intelligent way. Show more

Keywords: specification, logic design, verification, diagnosis, models, heuristics

DOI: 10.3233/FI-1997-3117

Citation: Fundamenta Informaticae, vol. 31, no. 1, pp. 79-105, 1997