Fundamenta Informaticae - Volume 54, issue 2-3

Authors: Schmidt, Karsten

Article Type: Research Article

Abstract: We report work in progress on a distributed version of explicit state space generation in the Petri net verification tool LoLA. We propose a data structure where all available memory of all involved workstations can be fully exploited, and load balancing actions are possible at any time while the verification is running. It is even possible to extend the set of involved workstations while a verification is running.

Keywords: Petri net, state space, distributed verification

Citation: Fundamenta Informaticae, vol. 54, no. 2-3, pp. 253-262, 2003

Authors: Skowron, Andrzej | Stepaniuk, Jarosław | Peters, James F.

Article Type: Research Article

Abstract: We discuss the relationships between information systems and classifications as well as between infomorphisms and definability of relations (between whole objects and their parts) in information systems. Infomorphisms between information systems (classifications) IS_1 and IS_2 make it possible to define some formulas over IS_2 by means of formulas over IS_1. The remaining formulas over IS_2 can be approximatively defined by means of formulas over IS_1. The approximation operations are defined using the rough …set approach. We present definitions and examples of such approximations. Show more

Keywords: information systems, classifications, rough set theory, infomorphisms, definability, approximations, approximate reasoning, information nets

Citation: Fundamenta Informaticae, vol. 54, no. 2-3, pp. 263-277, 2003

Authors: Varpaaniemi, Kimmo

Article Type: Research Article

Abstract: This article continues research on the stubborn set method that constructs on-the-fly a reduced LTS that is CFFD-equivalent to the parallel composition of given LTSs. In particular, minimization of the number of successor states of a given state is reconsidered. The earlier suggested and/or-graph approach requires solving #P-complete counting problems in order to get the weights for the vertices of the and/or-graph. The "branch-and-bound" decision problem corresponding to the minimization of the sum of the computed weights is "only" NP-complete. …Unfortunately, #P-complete counting does not seem easily avoidable in the general case because it is PP-complete to check whether a given stubborn set produces at most as many successor states as another given stubborn set. Instead of solving each of the subproblems, one could think of computing approximate solutions in such a way that the total effect of the approximations is a useful approximation itself. Show more

Keywords: LTS, stubborn sets, and/or-graphs, approximability in optimization and counting

Citation: Fundamenta Informaticae, vol. 54, no. 2-3, pp. 279-294, 2003