Fundamenta Informaticae - Volume 3, issue 2

Article Type: Other

DOI: 10.3233/FI-1980-3201

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

Authors: Gould, Jerren

Article Type: Research Article

Abstract: Flachs [1], Rabin [7], and Paz [6] have considered topics in the stability of probabilistic automata. Here we extend these results to the more general forms, automata in deterministic environments (ADE). We shall be concerned with two types of stability problems that arise from small perturbations of the environment configurations for an ADE. By consideration of the asymptotic properties of long products of stochastic matrices whose entries are subject to small perturbations concomitant to the environment configuration perturbations, we arrive at sufficient conditions for the state distribution function to be stable (s -stability). In its acceptor formulation the behavior of …an ADE is characterized by the sets T (A , e , λ ), the set of tapes accepted by A with environment sequence e and cut-point λ . Sufficient conditions are given for tape-acceptance stability (a -stability) in terms of s -stability and in terms that do not require s -stability. These stability results are pointwise results that give the size of the perturbation of the environment configuration to avoid instability. Show more

Keywords: Automaton, probabilistic automaton, automaton in environment, stability, a-stable, s-stable

DOI: 10.3233/FI-1980-3202

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 117-134, 1980

Authors: Păun, Gheorghe

Article Type: Research Article

Abstract: It is shown that a) there is an equal matrix language which cannot be written as a finite intersection of context-free languages and b) any finite intersection of context-free languages can be generated by a regular conditional grammar with context-free control languages.

Keywords: context-free languages, equal matrix languages, regular conditional grammars

DOI: 10.3233/FI-1980-3203

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 135-139, 1980

Authors: Albert, Jürgen | Maurer, Hermann | Rozenberg, Grzegorz

Article Type: Research Article

Abstract: In this paper we consider simple EOL forms (forms with a single terminal and single nonterminal) under uniform interpretations. We present a contribution to the analysis of generative power of simple EOL forms by establishing easily decidable necessary and sufficient conditions for simple EOL forms to generate (under uniform interpretations) CF languages only.

Keywords: context-free languages, Lindenmayer systems, grammatical similarity

DOI: 10.3233/FI-1980-3204

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 141-156, 1980

Authors: Mirkowska, Grażyna

Article Type: Research Article

Abstract: The paper is a continuation of the considerations connected with non-deterministic algorithmic logic. We will formulate a Hilbert style axiomatization basing on the analogous one defined for algorithmic logic. The main result is the theorem asserting that every consistent non-deterministic algorithmic theory possesses a model.

Keywords: algorithmic logic, deterministic algorithmic logic, non-deterministic algorithmic logic

DOI: 10.3233/FI-1980-3205

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 157-170, 1980

Authors: Bergstra, J.A. | Goeman, H.J.M. | Ollongren, A. | Terpstra, G.A. | van der Weide, Th.P.

Article Type: Research Article

Abstract: A set of axioms for structured objects of data is presented. In the structured objects components and levels are distinguished. Change of level is the result of a special application operator, components are accessible by successive selections. The set of access paths is also axiomatized. The set of axioms is uniform in the sense that features of various known classes of datastructures are combined.

Keywords: multi-level datastructures, programming

DOI: 10.3233/FI-1980-3206

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 171-180, 1980

Authors: Leitsch, Alexander

Article Type: Research Article

Abstract: The connection between index stes appearing in recursive enumerations of subrecursive classes and translating functions is investigated. Referring to a construction, which yields enumerations with low complexity for some index sets, we show that in such a case the complexity for some translating functions must be high. Furthermore a class of enumerations is discussed, which has elementary translating functions, but an important part of the index sets is not decidable by algorithms of the enumerated class (these index sets are of the form {x : ψ x ( a ) = f ( x ) …}). Show more

Keywords: recursive enumerations of subrecursive classes, complexity of translating functions, complexity of index sets

DOI: 10.3233/FI-1980-3207

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 181-188, 1980

Authors: Trnková, Věra

Article Type: Research Article

Abstract: General theory of relational automata, including non-deterministic linear and bilinear machines, structured non-deterministic tree automata and automata in some primitive classes of algebras, is developed. Particular attention is paid to languages accepted by finite relational automata.

Keywords: automata, relations, category, functor, functorial algebras, functorial machine, language

DOI: 10.3233/FI-1980-3208

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 189-233, 1980

Authors: Orłowska, Ewa

Article Type: Research Article

Abstract: The central method employed today for theorem-proving is the resolution method introduced by J. A. Robinson in 1965 for the classical predicate calculus. Since then many improvements of the resolution method have been made. On the other hand, treatment of automated theorem-proving techniques for non-classical logics has been started, in connection with applications of these logics in computer science. In this paper a generalization of a notion of the resolution principle is introduced and discussed. A certain class of first order logics is considered and deductive systems of these logics with a resolution principle as an inference rule are …investigated. The necessary and sufficient conditions for the so-called resolution completeness of such systems are given. A generalized Herbrand property for a logic is defined and its connections with the resolution-completeness are presented. A class of binary resolution systems is investigated and a kind of a normal form for derivations in such systems is given. On the ground of the methods developed the resolution system for the classical predicate calculus is described and the resolution systems for some non-classical logics are outlined. A method of program synthesis based on the resolution system for the classical predicate calculus is presented. A notion of a resolution-interpretability of a logic L in another logic L ′ is introduced. The method of resolution-interpretability consists in establishing a relation between formulas of the logic L and some sets of formulas of the logic L ′ with the intention of using the resolution system for L ′ to prove theorems of L . It is shown how the method of resolution-interpretability can be used to prove decidability of sets of unsatisfiable formulas of a given logic. Show more

Keywords: classical predicate calculus, ω+-valued logic, resolution principle, Herbrand’s theorem, completeness, decidability, program synthesis

DOI: 10.3233/FI-1980-3209

Citation: Fundamenta Informaticae, vol. 3, no. 2, pp. 235-268, 1980