Fundamenta Informaticae - Volume 4, issue 3

Article Type: Other

DOI: 10.3233/FI-1981-4301

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. i-xii, 1981

Authors: Mrożek, Marian

Article Type: Research Article

Abstract: We define the optimal generalized inverse of the directed graph, give its construction and prove that the graph has an inverse graph iff its optimal generalized inverse is its inverse. The construction of the optimal generalized inverse may be used in the preparation of the PERT networks by the computer.

Keywords: Directed graph, dual graph, inverse graph, line graph, PERT networks

DOI: 10.3233/FI-1981-4302

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 499-509, 1981

Authors: Rudnicki, Piotr | Trybulec, Andrzej

Article Type: Research Article

Abstract: An analytic investigation of formal languages is of practical value, apart from their description by means of generative grammars. This paper deals with the problem of grouping into classes the vocabulary elements of similar syntactic properties. The introduction of types for variables in programming languages is an example of such a grouping. In [3] a notion of syntactic partition onto sets of words has been defined. We prove below that there is continuum of such partitions.

Keywords: Formal languages, syntactic partition, classes of lexical tokens

DOI: 10.3233/FI-1981-4303

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 511-516, 1981

Authors: Goeman, Henk J.M.

Article Type: Research Article

Abstract: An active system component, the arbiter, is proposed as a system structuring concept for the implementation of synchronizing primitives. The concept is illustrated by showing a new and very simple implementation of the critical section with a busy form of waiting. This implementation will be refined in such a way that it does not need the commonly stated postulate of atomicity, according to which assignments to and inspections of common store locations are indivisible, non interfering, atomic actions. Thus we refute the well-known and widely believed “paradox of the critical region”. The use of the arbiter is further …illustrated by showing an implementation of the semaphore operations. These operations are implemented “on top of” the proposed implementation for the critical section, i.e. using the same busy form of waiting to ensure the mutual exclusion of concurrently issued individual semaphore operations. Nevertheless, the proposed implementation explicitly allows a nonbusy form of waiting to result from one of the semaphore operations by means of an interrupt mechanism. Show more

Keywords: Active system component, arbiter, synchronizing primitives, critical section, semaphore

DOI: 10.3233/FI-1981-4304

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 517-530d, 1981

Authors: Szijártó, Miklós

Article Type: Research Article

Abstract: The correspondence between sequential program schemes and formal languages is well known (Blikle and Mazurkiewicz (1972), Engelfriet (1974)). The situation is more complicated in the case of parallel program schemes, and trace languages (Mazurkiewicz (1977)) have been introduced to describe them. We introduce the concept of the closure of a language on a so called independence relation on the alphabet of the language, and formulate several theorems about them and the trace languages. We investigate the closedness properties of Chomsky classes under closure on independence relations, and as a special case we derive a new necessary and sufficient …condition for the regularity of the commutative closure of a language. Show more

Keywords: Formal languages, independence relation, trace languages, closure of languages on an independence relation

DOI: 10.3233/FI-1981-4305

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 531-549, 1981

Authors: Raś, Zbigniew

Article Type: Research Article

Abstract: This paper is the first of the three parts of work on the information retrieval systems proposed by Salton (see [24]). The system is defined by the notions of a partially ordered set of requests (A, ⩽), the set of objects X and a monotonic retrieval function U : A → 2X . Different conditions imposed on the set A and a function U make it possible to obtain various classes of information retrieval systems. We will investigate systems in which (A, ⩽) is a partially ordered set, a lattice, a pseudo-Boolean algebra and Boolean algebra. In my paper these …systems are called partially ordered information retrieval systems (po-systems) lattice information retrieval systems (l-systems); pseudo-Boolean information retrieval systems (pB-systems) and Boolean information retrieval systems (B-systems). The first part concerns po-systems and 1-systems. The second part deals with pB-systems and B-systems. In the third part, systems with a partial access are investigated. The present part discusses the method for construction of a set of attributes. Problems connected with the selectivity and minimalization of a set of attributes are investigated. The characterization and the properties of a set of attributes are given. Show more

Keywords: Information retrieval, selectivity, attributes, regular attributes, homomorphism

DOI: 10.3233/FI-1981-4306

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 551-603, 1981

Authors: Dańko, Wiktor

Article Type: Research Article

Abstract: In this paper a criterion of undecidability of theories based on algorithmic logic [1,8] is formulated. By the application of this criterion we are able to assert undecidability of algorithmic theory finite fields, theories of date structures e.g. dictionaries, storage management system and others theories of structures with finite universes. It is also proved that every decidable algorithmic theory admits elimination of iteration quantifiers and examples of decidable algorithmic theories are given.

Keywords: Algorithmic logic, formalized theory, algorithmic properties, decidability, undecidability

DOI: 10.3233/FI-1981-4307

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 605-628, 1981

Authors: Tiuryn, Jerzy

Article Type: Research Article

Abstract: A new logic to deal with properties of algorithmic processes in an abstract structure is proposed. This logic is based on the class of (deterministic) effective definitional schemes. A complete (infinitary) proof system is given. The paper contains among the other results, a “computation” of Hanf number of the above-mentioned logic, which turns out to he unexpectedly high.

Keywords: Logic, program schemes, axiomatization

DOI: 10.3233/FI-1981-4308

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 629-659, 1981

Authors: Bergstra, Jan | Tiuryn, Jerzy

Article Type: Research Article

Abstract: The following problem is investigated in the paper: what structures can be uniquely defined by algorithmic properties? The algorithmic properties are represented in this paper as open formulae of the logic of effective definitions. This approach can be viewed as an alternative way of defining abstract data types.

Keywords: Logic of programs, computation in abstract structures, algorithmic properties, abstract data types

DOI: 10.3233/FI-1981-4309

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 661-674, 1981

Authors: Mirkowska, Grażyna

Article Type: Research Article

Abstract: The aim of propositional algorithmic logic is to investigate the properties of program connectives. Complete axiomatic systems for deterministic as well as for nondeterministic interpretations of program variables are presented. They constitute basic sets of tools useful in the practice of proving the properties of program schemes. Propositional theories of data structures, e.g. the arithmetic of natural numbers and stacks, are constructed. This shows that in many aspects PAL is close to first-order algorithmic logic. Tautologies of PAL become tautologies of algorithmic logic after replacing program variables by programs and propositional variables by formulas. Another corollary to the completeness theorem …asserts that it is possible to eliminate nondeterministic program variables and replace them by schemes with deterministic atoms. Show more

Keywords: Logic of programs, algorithmic logic, nondeterminism, completeness

DOI: 10.3233/FI-1981-4310

Citation: Fundamenta Informaticae, vol. 4, no. 3, pp. 675-760, 1981