Fundamenta Informaticae - Volume 3, issue 1

Article Type: Other

DOI: 10.3233/FI-1980-3101

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. i-ix, 1980

Authors: Gould, Jerren | Wegman, Edward J.

Article Type: Research Article

Abstract: We establish the basic notion of automata in environments and solve some of the basic problems in the general theory of automata in deterministic environment (ADE). ADE are, in general, stronger than probabilistic automata. In an effort to find when an ADE and a PA have the same capability, we introduce the concept of simulation of an ADE by a PA. Every ADE with a finite environment set can be simulated by a PA (Theorem 1). There are sets which cannot be defined by PA but can be defined by ADE with finite environment sets and, hence, can be …simulated by a PA. ADE for which the environment can be reduced to a finite set can be simulated by a PA (Theorem 2). The set of stochastic matrices is a semi-group. We investigate the case where the environment set is also a semi-group and the transition function is a homomorphism between the semi-groups. If the semi-group environment set can be generated by a finite set, then the ADE can be simulated by a PA (Theorem 3). The continuous time PA of Knast [2] is seen to be a special case of the ADE. Show more

Keywords: automaton, probabilistic automaton, automaton in environments, probabilistic tables, cut-point, probabilistic cut-point event, environment

DOI: 10.3233/FI-1980-3102

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 1-13, 1980

Authors: Rozenberg, Grzegorz | Vermeir, Dirk

Article Type: Research Article

Abstract: The concept of metalinearity in ETOL systems is investigated. Some structural characterizations, a pumping lemma and the closure properties of the resulting class of languages are established. Finally, some applications in the theory of L systems of finite index are provided.

Keywords: Formal languages, ETOL systems, finite index

DOI: 10.3233/FI-1980-3103

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 15-36, 1980

Authors: Rytter, Wojciech

Article Type: Research Article

Abstract: Functional automata are models of algorithms of a certain class. The following problems concerning functional automata are presented and solved in the paper: 1. The problem of minimization of functional automat. 2. The problem of the existence of the nondeterministic functional automaton nonequivalent to any deterministic one. 3. The problem of optimal control for the functional automaton. 4. The problem of the existence of a universal automaton.

Keywords: functional automaton, minimization, control, measurable functional automaton, nondeterminism

DOI: 10.3233/FI-1980-3104

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 37-44, 1980

Authors: Mirkowska, Grażyna

Article Type: Research Article

Abstract: Algorithmic properties of nondeterministic programs are studied and axiomatized completely. Nondeterministic programs require two kinds of algorithmic formulas describing their behaviour: ΔKa – all computations of the program K are finite and all results satisfy a and ∇Ka – there exists a finite computation such that its result satisfies the formula a .

Keywords: nondeterministic program, algorithmic logic, completeness

DOI: 10.3233/FI-1980-3105

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 45-64, 1980

Authors: Janicki, Ryszard

Article Type: Research Article

Abstract: The paper deals with a class of programs called deterministic Mazurkiewicz algorithms. It considers languages associated with such algorithms by using symbols instead of actual relations and concatenation of words rather than composition of actual relations. It is shown that the class of languages so generated is precisely the class of simple context-free languages of Korenjak and Hoperoft [8].

Keywords: deterministic Mazurkiewicz algorithm, simple context-free language

DOI: 10.3233/FI-1980-3106

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 65-75, 1980

Authors: Best, Eike

Article Type: Research Article

Abstract: Real non-sequential processes can be described in a consistent way if they are assumed to satisfy a certain density property. Density as defined in [1] can be interpreted as postulating that a “global state” consists of a “progress snap-shot” of all single activities which constitute it. The present report shows that postulating density amounts to postulating that (a) each single history of a process is either infinite or has a first cause (but not both), and (b) each single future of a process is either infinite or has a last effect (but not both). This result is interpreted and …applied to the question of Turing-computability. Show more

Keywords: non-sequential, processes, causal nets, computability

DOI: 10.3233/FI-1980-3107

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 77-93, 1980

Authors: Cenzer, Douglas

Article Type: Research Article

Abstract: A set A of words on a finite alphabet Σ is said to be generable if it is the closure of a computable inductive operator; in particular, if S is a semi-Thue system then the set of words derivable in S is generable. An RE set of words (equivalently, a phrase-structure or type 0 language in the sense of Chomsky [Information and Control 2 (1959), 137–167]) which is non-generable is constructed by means of a finite injury priority argument. The construction is refined to obtain a non-generable set of degree 0′ and, for any degree …d , a non-generable set of degree ⩽ d . Show more

Keywords: formal language, semi-Thue system, recursive function, inductive definition, generable, degree of unsolvability

DOI: 10.3233/FI-1980-3108

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 95-103, 1980

Authors: Courcelle, Bruno | Raoult, Jean-Claude

Article Type: Research Article

Abstract: We give a completion theorem for ordered magmas (i.e. ordered algebras with monotone operations) in a general form. Particular instances of this theorem are already known, and new results follow. The semantics of programming languages is the motivation of such investigations.

Keywords: complete partial orders, semantics of programming languages

DOI: 10.3233/FI-1980-3109

Citation: Fundamenta Informaticae, vol. 3, no. 1, pp. 105-116, 1980