Fundamenta Informaticae - Volume 177, issue 1

Authors: Börger, Egon | Schewe, Klaus-Dieter

Article Type: Research Article

Abstract: “What is an algorithm?” is a fundamental question of computer science. Gurevich’s behavioural theory of sequential algorithms (aka the sequential ASM thesis) gives a partial answer by defining (non-deterministic) sequential algorithms axiomatically, without referring to a particular machine model or programming language, and showing that they are captured by (nondeterministic) sequential Abstract State Machines (nd-seq ASMs). However, recursive algorithms such as mergesort are not covered by this theory, as has been pointed out by Moschovakis, who had independently developed a different framework to mathematically characterize the concept of (in particular recursive) algorithm. In this article we propose an …axiomatic definition of the notion of sequential recursive algorithm which extends Gurevich’s axioms for sequential algorithms by a Recursion Postulate and allows us to prove that sequential recursive algorithms are captured by recursive Abstract State Machines , an extension of nd-seq ASMs by a CALL rule. Applying this recursive ASM thesis yields a characterization of sequential recursive algorithms as finitely composed concurrent algorithms all of whose concurrent runs are partial-order runs. Show more

Keywords: recursive algorithm, behavioural theory, abstract state machine, concurrent algorithm, partial-order run

DOI: 10.3233/FI-2020-1978

Citation: Fundamenta Informaticae, vol. 177, no. 1, pp. 1-37, 2020

Authors: Dowbor, Piotr | Kim, Yan

Article Type: Research Article

Abstract: The effective method (based on Theorem 5.3) of classifying tubular algebras by the Cartan matrices of tilting sheaves over weighted projective lines with all indecomposable direct summands in some finite “fundamental domain” , by the reduction to the two elementary problems of discrete mathematics having algorithmic solutions is presented in details (see Problem A and B). The software package CART_TUB being an implementation of this method yields the precise classification of all up to isomorphism tubular algebras of a fixed tubular type p, by creating the complete lists of their Cartan matrices, and furnish their tilting realizations. In particular, the …number of isomorphism classes of tubular algebras of the type p is determined (Theorem 2.3). Show more

Keywords: tubular algebra, Cartan matrix, weighted projective line, tilting sheaf, Euler form, algorithm, clique, weighted graph, adjacency matrix, index renumbering relation

DOI: 10.3233/FI-2020-1979

Citation: Fundamenta Informaticae, vol. 177, no. 1, pp. 39-67, 2020

Authors: Ghosal, Purnata | Raghavendra Rao, B.V.

Article Type: Research Article

Abstract: We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., n Ω(t (k )) lower bound for some function t of k ) on the size of the above models computing a multilinear polynomial that can be computed by a …depth four circuit of size g (k )n O (1) for some computable function g . Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large. Show more

DOI: 10.3233/FI-2020-1980

Citation: Fundamenta Informaticae, vol. 177, no. 1, pp. 69-93, 2020