Fundamenta Informaticae - Volume 17, issue 4

Article Type: Other

DOI: 10.3233/FI-1992-17401

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

Authors: Van Benthem, Johan

Article Type: Research Article

Abstract: Starting from a general dynamic analysis of reasoning and programming, we develop two main dynamic perspectives upon logic programming. First, the standard fixed point semantics for Horn clause programs naturally supports imperative programming styles. Next, we provide axiomatizations for Prolog-type inference engines using calculi of sequents employing modified versions of standard structural rules such as monotonicity or permutation. Finally, we discuss the implications of all this for a broader enterprise of ‘abstract proof theory’.

DOI: 10.3233/FI-1992-17402

Citation: Fundamenta Informaticae, vol. 17, no. 4, pp. 285-317, 1992

Authors: Aceto, Luca

Article Type: Research Article

DOI: 10.3233/FI-1992-17403

Citation: Fundamenta Informaticae, vol. 17, no. 4, pp. 319-331, 1992

Authors: Akdag, Herman | De Glas, Michel | Pacholczyk, Daniel

Article Type: Research Article

DOI: 10.3233/FI-1992-17404

Citation: Fundamenta Informaticae, vol. 17, no. 4, pp. 333-362, 1992

Authors: Mäkinen, Erkki

Article Type: Research Article

Abstract: Derivational complexity related to leftmost derivations of context-free grammars is studied by defining a new complexity measure based on characteristic samples of left Szilard languages.

DOI: 10.3233/FI-1992-17405

Citation: Fundamenta Informaticae, vol. 17, no. 4, pp. 363-368, 1992

Authors: Aceto, Luca

Article Type: Research Article

Abstract: The noninterleaving equivalences that have been proposed in the literature may be roughly divided into three classes, depending on the kind of observational scenarios underlying them. Some of them distinguish parallelism from nondeterminism by admitting explicit observations of the causal structure of systems; some others are based on the observation of distribution and still others on the assumption that actions have duration. In general, these three observational scenarios give rise to equivalences of incomparable discriminating power. In this paper, we show that three representative equivalences of the aforementioned classes, namely timed equivalence [Hen88], distributed bisimulation [CH89] and …causal bisimulation [DD88], coincide over a language for finite parallel processes without communication and restriction. The proof of this result is algebraic in style and relies on a theorem giving a finite, ω -complete axiomatization of causal bisimulation over the language under consideration. We also give a model for our language based upon causal trees and prove that it is fully abstract with respect to the largest congruence contained in strong bisimulation and preserved by a very simple form of action refinement [AH89]. Show more

DOI: 10.3233/FI-1992-17406

Citation: Fundamenta Informaticae, vol. 17, no. 4, pp. 369-397, 1992