Fundamenta Informaticae - Volume 22, issue 3

Authors: Moshkov, Mikhail

Article Type: Research Article

Abstract: Lower and upper bounds for the depth of decision trees computing Boolean functions are established and Shannon functions of the decision tree depth are determined for closed classes of Boolean functions.

DOI: 10.3233/FI-1995-2231

Citation: Fundamenta Informaticae, vol. 22, no. 3, pp. 203-215, 1995

Authors: Dassow, Jürgen | Paun, Gheorghe | Vicolov, Sorina

Article Type: Research Article

Abstract: The paper looks for necessary conditions for a language to be generated by a cooperating distributed grammar system with modes = k and ≥ k of derivation. It is proved that the length set of such languages contains infinite arithmetical progressions. Some consequences of this result are derived, concerning the power of these grammars and the closure properties of the corresponding families. Then, one proves that these systems can generate non-semi-linear languages. (Both these questions were formulated as open problems in the field literature.)

DOI: 10.3233/FI-1995-2232

Citation: Fundamenta Informaticae, vol. 22, no. 3, pp. 217-226, 1995

Authors: Dix, Jürgen

Article Type: Research Article

Abstract: Our aim in this article is to present a method for classifying and characterizing the various different semantics of logic programs with negation that have been considered in the last years. Instead of appealing to more or less questionable intuitions, we take a more structural view: our starting point is the observation that all semantics induce in a natural way non-monotonic entailment relations “ |˜ ”. The novel idea of our approach is to ask for the properties of these |˜ -relations and to use them for describing all possible semantics. The main properties discussed in this paper are adaptations …of rules that play a fundamental rôle in general non-monotonic reasoning: Cumulativity and Rationality. They were introduced and investigated by Gabbay, Kraus, Lehmann, Magidor and Makinson. We show that the 3-valued version COMP3 of Clark's completion, the stratified semantics MsuppP as well as the well-founded semantics WFS and two extensions of it behave very regular: they are cumulative, rational and one of them is even supraclassical. While Pereira's recently proposed semantics O-SEM is not rational it is still cumulative. Cumulativity fails for the regular semantics REG-SEM of You/Yuan (recently shown to be equivalent to three other proposals). In a second article we will supplement these strong rules with a set of weak rules and consider the problem of uniquely describing a given semantics by its strong and weak properties together. Show more

DOI: 10.3233/FI-1995-2233

Citation: Fundamenta Informaticae, vol. 22, no. 3, pp. 227-255, 1995

Authors: DIX, Jürgen

Article Type: Research Article

Abstract: Our aim in this article is to supplement the set of strong properties introduced in the preceding article ([Dix94]) with a set of weak principles in order to characterize semantics of logic programs. In [Dix94] we introduced our point of view: we observed that all semantics induce in a natural way a sceptical non-monotonic entailment relation SEMscept . We ask for the properties of these sceptical relations and use them to describe all possible semantics. We collect in this paper serious shortcomings of some semantics proposed recently. Their strange behaviour led us to formulate in a natural way certain principles …to avoid these problems. We argue that any well-behaved semantics should satisfy these principles. The main results state that our list of weak principles is complete in the following sense: any well-behaved-semantics is an extension of the well-founded semantics WFS and coincides for stratified programs with Apt, Blair, and Walker's supported model MsuppP . We also claim that two extensions of the well-founded semantics (introduced in the preceding article) are uniquely characterized by their strong and weak properties. Show more

DOI: 10.3233/FI-1995-2234

Citation: Fundamenta Informaticae, vol. 22, no. 3, pp. 257-288, 1995

Authors: Kolpakov, Roman M.

Article Type: Research Article

Abstract: In the paper the complexity of generation of certain sets of rational numbers by Boolean functions is evaluated. On the basis of that evaluation a necessary condition for the generation of some sets of rational numbers in the interval (0, 1) over an arbitrary class of Boolean functions is established.

DOI: 10.3233/FI-1995-2235

Citation: Fundamenta Informaticae, vol. 22, no. 3, pp. 289-298, 1995

Authors: Degano, Pierpaolo | Raffoni, Leonarda

Article Type: Research Article

Abstract: The random-assignment method for ensuring fairness for non-deterministic and/or concurrent languages is revised in order to make it dependent on the different priorities that each process may have. Priorities affect the choice of the scheduler in that a processes with high priority is preferred to others with a lower priority, still ensuring that all and only fair computations are originated. The actual presentation of the method is based on the non-standard model of the natural numbers of [C70].

DOI: 10.3233/FI-1995-2236

Citation: Fundamenta Informaticae, vol. 22, no. 3, pp. 299-306, 1995