Fundamenta Informaticae - Volume 25, issue 1

Authors: Bethke, Inge | Rodenburg, Piet

Article Type: Research Article

Abstract: We propose an extension of purely equational reasoning with an induction rule, to obtain an intermediate between the equational theory of an algebraic specification and its ω-closure.

DOI: 10.3233/FI-1996-25101

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 1-15, 1996

Authors: Fernau, Henning

Article Type: Research Article

Abstract: In this paper, we emphasize the differences of grammar families and their properties versus language families and their properties. To this end, we investigate grammar families from an abstract standpoint, developping a new framework of reasoning. In particular when considering decidability questions, special care must be taken. We illustrate this by inspecting some theorems and their proofs in the field of regulated rewriting. As an exercise, we show that there is no ‘effective’ grammatical characterization of the family of recursive languages.

DOI: 10.3233/FI-1996-25102

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 17-34, 1996

Authors: Bondarenko, V.A. | Yurov, S.V.

Article Type: Research Article

Abstract: A polyhedron Mn which is the convex hull of a set of characteristic vectors for all cubic subgraphs of the complete graph Gn is studied. It is shown that the problem of vertices nonadjacency recognition for this polyhedron is NP-complete and the density of its polyhedral graph is exponential on n. Such a set of properties combines the polyhedron Mn with the known polyhedron of Hamiltonian cycles.

DOI: 10.3233/FI-1996-25103

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 35-38, 1996

Authors: Bujosa, Andrés | Criado, Regino

Article Type: Research Article

Abstract: In this paper we introduce the concept of linear equation of symbols in the context of p-tangles, we obtain several “linear results” and we apply this results to address a possible algebraic description of the unification algorithm.

DOI: 10.3233/FI-1996-25104

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 39-48, 1996

Authors: Narendran, Paliath

Article Type: Research Article

Abstract: We show that elementary ACI10 unification is in P, even with constant restrictions. As a corollary, we prove that validity of quantified Horn formulae can be tested in O(n2 ) time. Solvability of elementary disunification problems modulo ACI10 is shown to be NP-hard.

DOI: 10.3233/FI-1996-25105

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 49-57, 1996

Authors: Kaufmann, Susanne | Kummer, Martin

Article Type: Research Article

Abstract: One topic arising in recent research on “Bounded Query Classes” is to consider quantitative aspects of recursion theory, and in particular various notions of parameterized recursive approximations of sets. An important question is, for which values of the parameters – depending on the type of approximation – the approximated set is necessarily recursive. Beigel's Nonspeedup Theorem, Rummer's Cardinality Theorem and Trakhtenbrot's Theorem provide answers using nonuniform constructions. This paper investigates to which extend these constructions can be made uniform. Beigel's Nonspeedup Theorem is equivalent to the statement that every branch of a recursively enumerable tree of bounded width is recursive. …There is no algorithm which computes a branch from the index of the tree, but there are nontrivial positive results by weakening the requirements as follows: For some fixed number k, an algorithm is wanted which, given an index of a tree, outputs a list of k programs such that at least one of them computes a branch of the tree up to finitely many errors. What is the least k for which this works? In this paper it is shown that, for recursively enumerable trees of width at most n, the least possible k is 2n−1. For trees arising from Trakhtenbrot's Theorem with parameters m, n, the optimal value is k = n − m + 1. In addition, several other, related classes of trees are investigated. Show more

DOI: 10.3233/FI-1996-25106

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 59-78, 1996

Authors: Korczyńsky, Waldemar

Article Type: Research Article

Abstract: In the paper Gaussian monoids with zero as a basis for modeling of concurrence and a kind of consistence are proposed and a notion of concurrent system is defined. The main idea is to replace the binary relation of concurrence defined on a set of activities (transitions in Petri nets, events etc.) by a more general notion of independence of multisets.

Keywords: Concurrence, Petri nets, monoids, ideals, category, processes

DOI: 10.3233/FI-1996-25107

Citation: Fundamenta Informaticae, vol. 25, no. 1, pp. 79-98, 1996