Fundamenta Informaticae - Volume 60, issue 1-4

Authors: Półrola, Agata | Penczek, Wojciech

Article Type: Research Article

Abstract: The paper presents three methods for applying partitioning algorithms, used for generating abstract models for timed automata, to the case of time Petri nets. Each of these methods is based on a different approach to the concrete semantics of a net, and can potentially be more efficient than the others in a particular case. Besides the theoretical description, we provide some …preliminary experimental results, obtained from the implementation integrated with the model checking tool VerICs Show more

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 307-331, 2004

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: In recent years, a number of classical results connecting rational languages with finite semigroups have been extended to infinite-word languages using the notion of an ω-semigroup: a semigroup augmented with an associative infinite product. This paper takes a closer look at the associative infinite product itself. It suggests some improvements and presents a couple of new facts.

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 333-350, 2004

Authors: Skowron, Andrzej | Synak, Piotr

Article Type: Research Article

Abstract: We outline some results of our current research on developing a methodology for solving problems of spatio-temporal reasoning. We consider classifiers for complex concepts in spatio-temporal reasoning that are constructed hierarchically. We emphasise the fact that the construction of such hierarchical classifiers should be supported by domain knowledge. Approximate reasoning networks (AR networks) are proposed for approximation of reasoning schemes expressed in natural language. Such reasoning schemes are extracted from knowledge bases …representing domain knowledge. This approach makes it possible to induce classifiers for complex concepts by constructing them along schemes of reasoning extracted from domain knowledge. Show more

Keywords: complex object, concept approximation, pattern, rough sets, spatio-temporal reasoning, classifier, network of classifiers

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 351-366, 2004

Authors: Tini, Simone | Maggiolo-Schettini, Andrea

Article Type: Research Article

Abstract: We give an algorithm for synthesizing Generalized Mealy Machines from LTL-formulae. The main novelty of the paper is that the algorithm is compositional. Its complexity coincides with the lower bound of the synthesis problem.

Keywords: mealy machines, LTL, synthesis

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 367-382, 2004

Authors: Virbitskaite, Irina B. | Gribovskaya, Natalya S.

Article Type: Research Article

Abstract: The intention of the paper is to show the applicability of the general categorical framework of open maps to the setting of timed extensions of partial order models, in order to transfer general concepts of equivalences to the models. In particular, we define categories of timed event structures, whose morphisms are to be thought of as simulations, and accompanying (sub)categories of observations, to which the corresponding notions of open maps are developed. We then use the …open maps framework to obtain abstract bisimilarities which are established to coincide with timed extensions of well-known partial order based equivalences. Show more

Keywords: category theory, open maps, timed event structures, timed partial order equivalences

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 383-399, 2004

Authors: Wolski, Marcin

Article Type: Research Article

Abstract: We investigate Galois connections and their relations to the major theories of (qualitative) data analysis: Rough Set Theory (RST), Formal Concept Analysis (FCA) and John Stuart Mill Reasoning (JSM-Reasoning). Polarities, a type of contravariant Galois connections, and their relationships with data analysis has been already well-known. This paper shows how axialities, a type of covariant Galois connections, are …related to problems adressed by data analysis and prove that they give rise to a number of interesting lattices. Show more

Keywords: galois connection, polarity lattice, axiality, concept, rough set, lattice

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 401-415, 2004

Authors: Zbrzezny, Andrzej

Article Type: Research Article

Abstract: The paper deals with the problem of checking reachability for timed automata. In order to check reachability of a~state satisfying some property, first the transition relation of a timed automaton is unfolded iteratively to some depth and encoded as a propositional formula. Next, the property is translated to a propositional formula and satisfiability of the conjunction of the two defined above formulas is checked. The unfolding of the transition relation can be terminated when either a …state satisfying the property has been found or all the states of the timed automaton have been searched. In this paper we propose some improvements of the encoding of the transition relation for timed automata. The improvements are partially based on a new discretization scheme. The efficiency of the improved encoding is strongly supported by the experimental results. We also introduce a method for checking unreachability. Show more

Citation: Fundamenta Informaticae, vol. 60, no. 1-4, pp. 417-434, 2004