Fundamenta Informaticae - Volume 9, issue 3

Article Type: Other

DOI: 10.3233/FI-1986-9301

Citation: Fundamenta Informaticae, vol. 9, no. 3, pp. i-vi, 1986

Authors: Černý, Anton | Gruska, Jozef

Article Type: Research Article

Abstract: A new type of nonhomogeneous real time trellis automata, the so-called modular trellis automata, is introduced and various results concerning their normal forms, power, simulations, and decision problems are shown. Modular trellis automata are a mathematical abstraction, in the form of a recognizer, of an intuitive notion of an array of simple processors assembled in a simple and modular way. Distribution of processors in a real-time trellis automaton forms a two-dimensional structure called trellis. Basic characterizations and properties of modular trellises are summarized and modularity of various special trellises – regular, product, self-embedding, and self-overlapping – is investigated.

DOI: 10.3233/FI-1986-9302

Citation: Fundamenta Informaticae, vol. 9, no. 3, pp. 253-282, 1986

Authors: Chytil, Michal P.

Article Type: Research Article

Abstract: We define a superclass of the class of context-free languages, denoted ACFL (almost context-free languages) and construct an infinite sequence of non-context-free languages of decreasing complexity, belonging to ACFL. The languages in ACFL share many important properties of context-free languages. For example, a slight generalization of pumping lemma for context-free languages holds also for languages in ACFL. Similarly, some of the questions decidable for context-free languages are decidable in ACFL and start to be undecidable immediately outside the class. ACFL is a full AFL and contains an infinite strictly decreasing chain of full AFLs.

Keywords: Almost context-free language, context-free language, one-way auxiliary pushdown automaton, pumping lemma, abstract family of languages, complexity of computations

DOI: 10.3233/FI-1986-9303

Citation: Fundamenta Informaticae, vol. 9, no. 3, pp. 283-321, 1986

Authors: Leung, Joseph Y.-T. | Monien, Burkhard

Article Type: Research Article

Abstract: We consider the computational complexity of finding an optimal deadlock recovery. It is known that for an arbitrary number of resource types the problem is NP-hard even when the total cost of deadlocked jobs and the total number of resource units are “small” relative to the number of deadlocked jobs. It is also known that for one resource type the problem is NP-hard when the total cost of deadlocked jobs and the total number of resource units are “large” relative to the number of deadlocked jobs. In this paper we show that for one resource type the problem is solvable …in polynomial time when the total cost of deadlocked jobs or the total number of resource units is “small” relative to the number of deadlocked jobs. For fixed m ⩾ 2 resource types, we show that the problem is solvable in polynomial time when the total number of resource units is “small” relative to the number of deadlocked jobs. On the other hand, when the total number of resource units is “large”, the problem becomes NP-hard even when the total cost of deadlocked jobs is “small” relative to the number of deadlocked jobs. The results in the paper, together with previous known ones, give a complete delineation of the complexity of this problem under various assumptions of the input parameters. Show more

DOI: 10.3233/FI-1986-9304

Citation: Fundamenta Informaticae, vol. 9, no. 3, pp. 323-342, 1986

Authors: Wagner, Eric G.

Article Type: Research Article

Abstract: The aim of this paper is to model recursive types, equational types, and elementary programming control constructs (such as conditionals and while-do) in one, comparatively simple, algebraic framework, that can be used for theoretical studies and as a basis for data type and program specification. To this end we introduce a new kind of algebraic theory, the RV-theory. We give simple examples of the use of such theories for data type specification. We provide a mathematical semantics for these specifications that extends the initial algebra semantics for equational specification to include recursive types.

DOI: 10.3233/FI-1986-9305

Citation: Fundamenta Informaticae, vol. 9, no. 3, pp. 343-370, 1986