Fundamenta Informaticae - Volume 44, issue 4

Authors: Analyti, Anastasia | Spyratos, Nicolas | Constantopoulos, Panos

Article Type: Research Article

Abstract: In semantic and object-oriented data models, each class has one or more typing properties that associate it to other classes, and carry type information about all instances of the class. We introduce a new kind of property that we call instance-typing property. An instance-typing property associates an instance of a class to another class, and carries type information about that particular instance (and not about all instances of the class). Instance-typing properties are important as they …allow to represent summary information about an instance, in addition to specific information. In this paper, we study inheritance of properties from a class to an instance, using type information about the class, as well as type information about the instance. This kind of inheritance, that we call contextual instance-inheritance, provides us with the most specific type information about the instance, in a particular context. Intuitively, a context is a metaclass of interest with respect to which this most specific information is determined. We demonstrate that contextual instance-inheritance is a powerful conceptual modeling mechanism, capable of expressing valuable information about instances. We also provide a framework in which derived instance-inherited properties can be represented and retrieved in the same way as ``usual'' properties. Show more

Keywords: instance-inheritance, type information, context, inference rules, conceptual modeling, object-oriented modeling

Citation: Fundamenta Informaticae, vol. 44, no. 4, pp. 321-351, 2000

Authors: Dassow, Jürgen | Martín-Vide, Carlos | Păun, Gheorghe | Rodríguez-Patón, Alfonso

Article Type: Research Article

Abstract: Inspired from biochemistry and DNA computing, we introduce several variants of controlled concatenation of strings and languages: a finite set of pairs of strings is given and two arbitrary strings are concatenated only when among their substrings (scattered substrings, of various forms) we can find a pair in this control set. Five types of non-iterated and iterated (like Kleene closure) conditional concatenations are considered. The closure properties of abstract families of languages (hence also of families …in the Chomsky hierarchy) are settled. They are similar to the closure properties under usual concatenation and Kleene closure. A representation of regular languages in terms of these operations (and a coding) is also given. Then, we use the new concatenation operations as basic operations in Chomsky grammars: rewriting a nonterminal means concatenating a new string with the strings to the left and the right of that nonterminal, hence restricted concatenations can be used. Context-free grammars working in this restricted manner can generate non-context-free languages; in one case, characterizations of recursively enumerable or of context-sensitive languages are obtained, depending on using or not erasing rules. Some topics for further research are also suggested. Show more

Keywords: closure under controlled concatenation, characterization of regular languages

Citation: Fundamenta Informaticae, vol. 44, no. 4, pp. 353-372, 2000

Authors: Demri, Stéphane | Stepaniuk, Jarosław

Article Type: Research Article

Abstract: We characterize the computational complexity of a family of approximation multimodal logics in which interdependent modal connectives are part of the language. Those logics have been designed to reason in presence of incomplete information in the sense of rough set theory. More precisely, we show that all the logics have a PSPACE-complete satisfiability problem and we define a family of tolerance approximation multimodal logics whose satisfiability is EXPTIME-complete. This illustrates that the PSPACE upper bound for …this kind of multimodal logics is a very special feature of such logics. The PSPACE upper bounds are established by adequately designing Ladner-style tableaux-based procedures whereas the EXPTIME lower bound is established by reduction from the global satisfiability problem for the standard modal logic B. Show more

Keywords: rough sets, tolerance rough sets, multimodal logics, computational complexity, Ladner-style algorithm

Citation: Fundamenta Informaticae, vol. 44, no. 4, pp. 373-396, 2000

Authors: Kurucz, Agnes | Németi, István

Article Type: Research Article

Abstract: We consider classes of relation algebras expanded with new operations based on the formation of ordered pairs. Examples for such algebras are pairing (or projection) algebras of algebraic logic and fork algebras of computer science. It is proved by Sain and Németi [38] that there is no `strong' representation theorem for all abstract pairing algebras in most set theories including ZFC as well as most non-well-founded set theories. Such a `strong' representation theorem would state that …every abstract pairing algebra is isomorphic to a set relation algebra having projection elements which are defined with the help of the real (set theoretic) pairing function. Here we show that, by choosing an appropriate (non-well-founded) set theory as our metatheory, pairing algebras and fork algebras admit such `strong' representation theorems. Show more

Keywords: relation algebra, projection elements, non-well-founded set theories

Citation: Fundamenta Informaticae, vol. 44, no. 4, pp. 397-420, 2000