Fundamenta Informaticae - Volume 36, issue 2-3

Authors: Amin, Mohamed

Article Type: Research Article

Abstract: In [2] it is shown that the family of languages generated by cooperating distributed (CD) grammar systems with context-free components in the derivation modes = k, ≥ k, for k ≥ 2, and the family of E0L languages are incomparable. Because one of the languages used in the proof of the incomparability does not work, we fill here the gap, using another language. We also give an effective procedure for constructing an ET0L system from a given context-free cooperating/distributed (CD) grammar system working in the maximum mode of cooperation.

DOI: 10.3233/FI-1998-36231

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 103-107, 1998

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

Article Type: Research Article

Abstract: We elaborate on the semantics of an enhanced object-oriented semantic network, where multiple instantiation, multiple specialization, and meta-classes are supported for both kinds of objects: entities and properties. By semantics of a semantic network, we mean the information (both explicit and derived) that the semantic network carries. Several data models use semantic networks to organize information. However, many of these models do not have a formalism defining what the semantics of the semantic network is. In our data model, in addition to the Isa relation, we consider a stronger form of specialization for properties, that we call restriction isa, or …Risa for short. The Risa relation expresses property value refinement. A distinctive feature of our data model is that it supports the interaction between Isa and Risa relations. The combination of Isa and Risa provides a powerful conceptual modeling mechanism. The user declares objects and relations between objects through a program. Reasoning is done through a number of (built-in) inference rules that allow for derivations both at instance and schema level. Through the inference rules, new objects and new relations between objects are derived. In our data model, inherited properties are considered to be derived objects. In addition to the inference rules, a number of (built-in) system constraints exist for checking the validity of a program. Show more

Keywords: semantic network, semantics, inheritance, inference rules, constraints, conceptual modeling

DOI: 10.3233/FI-1998-36232

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 109-144, 1998

Authors: Bérard, Béatrice | Petit, Antoine | Diekert, Volker | Gastin, Paul

Article Type: Research Article

Abstract: Timed automata are among the most widely studied models for real-time systems. Silent transitions, i.e., ϵ-transitions, have already been proposed in the original paper on timed automata by Alur and Dill [3]. We show that the class TLϵ of timed languages recognized by automata with ϵ-transitions, is more robust and more expressive than the corresponding class TL without ϵ-transitions. We then focus on ϵ-transitions without reset, i.e. ϵ-transitions which do not reset clocks. We propose an algorithm to construct, given a timed automaton, an equivalent one without such transitions. This algorithm is in two steps, it first suppresses the …cycles of ϵ-transitions without reset and then the remaining ones. Then, we prove that a timed automaton such that no ϵ-transition which resets clocks lies on any directed cycle, can be effectively transformed into a timed automaton without ϵtransitions. Interestingly, this main result holds under the assumption of non-Zenoness and it is false otherwise. To complete the picture, we exhibit a simple timed automaton with an ϵ-transition, which resets some clock, on a cycle and which is not equivalent to any ϵ-free timed automaton. To show this, we develop a promising new technique based on the notion of precise action. This paper presents a synthesis of the two conference communications [9] and [13]. Show more

DOI: 10.3233/FI-1998-36233

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 145-182, 1998

Authors: Dassow, Jürgen | Păunt, Gheorghe

Article Type: Research Article

Abstract: In the last years the operation of splicing which models a special type of recombination of genomes has been intensively studied, e.g. the effect of application of splicings to language families of classical formal language theory has been investigated. In this paper we present analogous results with respect to the operations inversion, translocation and duplication which are also descriptions of mutations of genomes.

Keywords: operations on formal languages, mutation in genomes

DOI: 10.3233/FI-1998-36234

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 183-200, 1998

Authors: Dovier, Agostino | Policriti, Alberto | Rossi, Gianfranco

Article Type: Research Article

Abstract: The first-order theories of lists, multisets, compact lists (i.e., lists where the number of contiguous occurrences of each element is immaterial), and sets are introduced via axioms. Such axiomatizations are shown to be very well-suited for the integration with free functor symbols governed by the classical Clark's axioms in the context of (Constraint) Logic Programming. Adaptations of the extensionality principle to the various theories taken into account is then exploited in the design of unification algorithms for the considered data structures. All the theories presented can be combined providing frameworks to deal with several of the proposed data structures simultaneously. …The unification algorithms proposed can be combined (merged) as well, to produce engines for such combination theories. Show more

Keywords: Axiomatic Set Theory, Unification

DOI: 10.3233/FI-1998-36235

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 201-234, 1998

Authors: Middelburg, Kees A.

Article Type: Research Article

Abstract: Duration calculus is a logical formalism designed for expressing and refining real-time requirements for systems. Timed frames are essentially transition systems meant for modeling the time-dependent behaviour of programs. We investigate the interpretation of duration calculus formulae in timed frames. We elaborate this topic from different angles and show that they agree with each other. The resulting interpretation is expected to make it generally easier to establish semantic links between duration calculus and formalisms aimed at programming. Such semantic links are prerequisites for a solid underpinning of approaches to system development that cover requirement capture through coding using both duration …calculus and some formalism(s) aimed at programming. Show more

Keywords: duration calculus, real-time requirements, timed frames, time-dependent behaviour, verification

DOI: 10.3233/FI-1998-36236

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 235-263, 1998

Authors: Stepaniuk, Jaroslaw

Article Type: Research Article

Abstract: Rough set methodology is based on concept (set) approximations constructed from available background knowledge represented in information systems [14]. In many applications only partial knowledge about approximated concepts is given. Hence quite often first a parametrized family of concept approximations is built and next, by parameters tuning the best, in a sense, approximation is chosen (see e.g. the variable precision rough set model [40]). In this paper we follow this approach in generalized approximation spaces. We discuss rough set model based on approximation spaces with uncertainty functions and rough inclusions. Elements of approximation space are parametrized, moreover for the proper …application of such model to a particular data set it is necessary to make optimization of the parameters. We discuss not only basic properties of the mentioned model, but strategies of parameters optimization as well. We also present different notions of rough relations. Optimization of different parameters can be based on the degree of inclusion of relations defined by condition and decision attributes. Some illustration of presented methods on real life medical data set is also included. Show more

DOI: 10.3233/FI-1998-36237

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 265-283, 1998

Authors: Zhiltsova, Larissa

Article Type: Research Article

Abstract: We investigate questions, relating to optimal binary coding of a language, for which a probability distribution is given on its words (for a stochastic language). As optimal we understand the coding, which gives minimum of mathematical expectation of a length of the coded word, or minimum of the coding cost. For any stochastic language with a finite value of the entropy we establish lower and upper bounds of the optimal coding cost, dependent only on the entropy, and we prove their unimprovability. For any stochastic context-free language with unique derivation it is found necessary and sufficient condition of existence of …finite values of the optimal coding cost and the entropy. Also an effective method of calculation of the entropy is found for the case when the considered condition holds. Show more

Keywords: Stochastic language, context-free grammar, entropy, optimal coding

DOI: 10.3233/FI-1998-36238

Citation: Fundamenta Informaticae, vol. 36, no. 2-3, pp. 285-305, 1998