Fundamenta Informaticae - Volume 17, issue 3

Article Type: Other

DOI: 10.3233/FI-1992-17301

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. i-vii, 1992

Authors: Rauszer, Cecylia M.

Article Type: Research Article

Abstract: Stable autoepistemic sets are treated as S4 maximal theories. This approach allows to use the Lindenbaum algebra of modal logic as a tool in investigations of existence of a special kind of stable sets. Namely, for a given set A , the algebraic constructions of minimal stable sets based on A and moderately grounded expansions of A are shown.

DOI: 10.3233/FI-1992-17302

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 175-186, 1992

Authors: Gold, Robert | Vogler, Walter

Article Type: Research Article

Abstract: This paper discusses a number of properties that a partial order semantics should have in order to support the modular construction of nets and to deal with finite capacities. Characterizations for these properties are shown, and a new semantics is introduced which seems to be the natural choice if a certain set of properties is required.

DOI: 10.3233/FI-1992-17303

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 187-209, 1992

Authors: Huynh, Dung T. | Tian, Lu

Article Type: Research Article

Abstract: In this paper, we investigate several equivalence relations for probabilistic labeled transition systems: bisimulation equivalence, readiness equivalence, failure equivalence, trace equivalence, maximal trace equivalence and finite trace equivalence. We formally prove the inclusions (equalities) among these equivalences. We also show that readiness, failure, trace, maximum trace and finite trace equivalences for finite probabilistic labeled transition systems are decidable in polynomial time. This should be contrasted with the PSPACE completeness of the same equivalences for classical labeled transition systems. Moreover, we derive an efficient polynomial time algorithm for deciding bisimulation equivalence for finite probabilistic labeled transition systems. The special case …of initiated probabilistic transition systems will be considered. We show that the isomorphism problem for finite initiated labeled probabilistic transition systems is NC (1) equivalent to graph isomorphism. Show more

Keywords: Bisimulation equivalence, readiness equivalence, failure equivalence, trace equivalence, maximal trace equivalence, finite trace equivalence, probabilistic labeled transition system, initiated probabilistic labeled transition system, probabilistic relation, probabilistic automaton, complexity, reducibility

DOI: 10.3233/FI-1992-17304

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 211-234, 1992

Authors: Velauthapillai, Mahendran

Article Type: Research Article

Abstract: In this paper we define two new inference classes Team Density and Team Uniform Density . The team density class turns out to be the “most powerful” of all the inference classes that have been defined and studied so far. We compare these classes to previously defined classes. We obtain necessary and sufficient conditions for one team density class to be a subset of another team density class. Similar results are obtained for team uniform density class. We also have compare team density and team uniform density classes and obtained necessary and sufficient conditions for one class to be …a subset of another. Most importantly we show that team density, the “most powerfull” class, cannot cover the BC class. From this result we obtain several theorems as corollaries that have been proved in earlier papers. Show more

DOI: 10.3233/FI-1992-17305

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 235-251, 1992

Authors: Madry, Małgorzata

Article Type: Research Article

Abstract: Six λ -languages over function-types between algebras B , N and Υ are considered. Type N = ( 0 → 0 ) → ( 0 → 0 ) is called a non-negative integers type; B = ( 0 → 0 ) → ( ( 0 → 0 ) → ( 0 → 0 ) ) is called a binary words type; Υ = ( 0 → ( 0 → 0 ) ) → ( 0 → 0 ) is called a binary trees type. These associations come from the isomorphism …between the types and corresponding algebraic structures. Closed terms whose types are the above mentioned function-types represent unary functions of appropriate types. The problem is: what class of functions is represented by the closed terms of the examined type. It is proved that for B → N , N → B , Υ → N , Υ → B there exists a finite base of functions such that any λ -definable function is some combination of the base functions. The algorithm which, for every closed term, returns the function in the form of a combination of the base functions is given. For two other types, B → Υ and N → Υ , a method of constructing λ -representable functions using primitive recursion is shown. Show more

DOI: 10.3233/FI-1992-17306

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 253-270, 1992

Authors: Ramakrishna, Y.S. | Moser, L.E. | Dillon, L.K. | Melliar-Smith, P.M. | Kutty, G.

Article Type: Research Article

Abstract: We present an automata-theoretic decision procedure for Since/Until Temporal Logic (SUTL), a linear-time propositional temporal logic with strong non-strict since and until operators. The logic, which is intended for specifying and reasoning about computer systems, employs neither next nor previous operators. Such operators obstruct the use of hierarchical abstraction and refinement and make reasoning about concurrency difficult. A proof of the soundness and completeness of the decision procedure is given, and its complexity is analyzed.

DOI: 10.3233/FI-1992-17307

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 271-282, 1992

Article Type: Correction

DOI: 10.3233/FI-1992-17308

Citation: Fundamenta Informaticae, vol. 17, no. 3, pp. 283-283, 1992