Fundamenta Informaticae - Volume 10, issue 2

Article Type: Other

DOI: 10.3233/FI-1987-10201

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. i-vii, 1987

Authors: Wand, Mitchell

Article Type: Research Article

Abstract: We present a simple proof of Hindley’s Theorem: that it is decidable whether a term of the untyped lambda calculus is the image under type-erasing of a term of the simply typed lambda calculus. The proof proceeds by a direct reduction to the unification problem for simple terms. This arrangement of the proof allows for easy extensibility to other type inference problems.

DOI: 10.3233/FI-1987-10202

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. 115-121, 1987

Authors: Urzyczyn, Pawel

Article Type: Research Article

Abstract: We show an example of an algebra T∙ , such that every flow-chart program is equivalent in T∙ to a loop-free approximation of itself, while a program augmented by one binary push-down store is not equivalent in T∙ to any loop-free program. From this we deduce that the Deterministic Dynamic Logic of regular programs is strictly weaker than the Deterministic Context-Free Dynamic Logic.

DOI: 10.3233/FI-1987-10203

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. 123-141, 1987

Authors: Păun, Gheorghe | Novotný, Miroslav

Article Type: Research Article

Abstract: We prove that every nontrivial even linear language is linearly grammatizable by means of derivatives.

Keywords: generalized grammar with linear productions, derivative, permitting triple with derivatives corresponding to a language, language linearly grammatizable by means of derivatives, even context, even category, even linear language

DOI: 10.3233/FI-1987-10204

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. 143-148, 1987

Authors: Giancarlo, Raffaele | Rytter, Wojciech

Article Type: Research Article

DOI: 10.3233/FI-1987-10205

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. 149-160, 1987

Authors: Best, Eike | Merceron, Agathe

Article Type: Research Article

Abstract: A non-sequential process can be modelled by a partially ordered set. Conversely, one is led to study the properties to be fulfilled by a poset so that it can reasonably be viewed as the model of a non-sequential process. To this end, C.A. Petri has proposed a set of con currency axioms and a related property called D-continuity, a generalised version for partially ordered sets of Dedekind’s completeness property of the real numbers. In this paper we study Petri’s axioms of concurrency and some of their interdependencies. We also derive several characterisations of D-continuity and exhibit its relation with …the axioms of concurrency. Furthermore we apply our work to Petri nets: we introduce occurrence nets, some special posets which model the processes of a system net and we present their relations to D-continuity and the axioms of con currency. Finally we identify the class of the system nets whose processes are D-continuous and satisfy the axioms of concurrency. Show more

DOI: 10.3233/FI-1987-10206

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. 161-211, 1987

Authors: Bergstra, Jan | Tiuryn, Jerzy

Article Type: Research Article

Abstract: An unbounded queue over a finite set of data values is a process Q in A∞ defined by an infinite system of guarded equations. The aim of this paper is to show that no finite system of guarded equations is capable of defining Q.

DOI: 10.3233/FI-1987-10207

Citation: Fundamenta Informaticae, vol. 10, no. 2, pp. 213-223, 1987