Fundamenta Informaticae - Volume 50, issue 1

Authors: Beauquier, Danièle

Article Type: Research Article

Abstract: We prove that given a Markov Decision Process (MDP) and a fixed subset of its states~F, there is a Markov policy which maximizes everywhere the probability to reach F infinitely often. Moreover such a maximum policy is computable in polytime in the size of the MDP. This result can be applied in order to control a system with randomized or uncertain behavior with respect to a given property to optimize.

Keywords: Markov Decision Processes, Büchi automata, performance evaluation

Citation: Fundamenta Informaticae, vol. 50, no. 1, pp. 1-13, 2002

Authors: Kacprzak, Magdalena

Article Type: Research Article

Abstract: In this paper is introduced a proof system for branching time temporal logic, called PTL. It allows to verify static and dynamic properties of nondeterministic programs, which are expressed as a temporal formulas of PTL language. The strong completeness theorem of this system is presented.

Keywords: temporal logic, a complete axiomatization

Citation: Fundamenta Informaticae, vol. 50, no. 1, pp. 15-31, 2002

Authors: Klaudel, Hanna | Pommereau, Franck

Article Type: Research Article

Abstract: This paper presents an extension of an algebra of high-level Petri nets with operations for suspension and abortion. These operations are sound with respect to the semantics of preemption, and can be applied to the modelling of the semantics of high-level parallel programming languages with preemption-related features. As an illustration, the paper gives an application to the modelling of a multi-tasking system in a parallel programming language, which is provided with a concurrent semantics based on …Petri nets and for which implemented tools can be used. Show more

Keywords: Petri nets, compositionality, preemption, tasks

Citation: Fundamenta Informaticae, vol. 50, no. 1, pp. 33-55, 2002

Authors: Moshkov, Mikhail Ju.

Article Type: Research Article

Abstract: Bayesian Networks (BN) are convenient tool for representation of probability distribution of variables. We study time complexity of decision trees which compute values of all observable variables from BN. We consider (1,2)-BN in which each node has at most 1 entering edge, and each variable has at most 2 values. For an arbitrary (1,2)-BN we obtain lower and upper bounds on minimal depth of decision tree that differ not more than by a factor of 4, and …can be computed by an algorithm which has polynomial time complexity. The number of nodes in considered decision trees can grow as exponential on number of observable variables in BN. We develop an polynomial algorithm for simulation of the work of decision trees which depth lies between the obtained bounds. Show more

Keywords: Bayesian networks, decision trees, complexity, simulation

Citation: Fundamenta Informaticae, vol. 50, no. 1, pp. 57-76, 2002

Authors: Sureson, Claude

Article Type: Research Article

Abstract: Motivated by the analogy ``(NP/Poly)∼analytic'', we propose a co-analytic set W whose finite equivalent W_finite is coNP-complete. The complement of W is in fact a variant of ``infinite clique''. A combinatorial proof of the non-analyticity of W is produced and studied in order to be (eventually) ``finitized'' into a probabilistic proof of ``W_finite ∉ NP/Poly (this would imply NP≠CoNP). A reasonable objective could be to determine a specific class of nondeterministic …circuits which allow a finitization of the arguments of the infinite case, and thus which cannot compute W_finite. Show more

Keywords: Nondeterministic polynomial time, circuits, analytic sets

Citation: Fundamenta Informaticae, vol. 50, no. 1, pp. 77-110, 2002