Search

Finite topological spaces and their dimensions have many applications in computer science, e.g., in digital topology, computer graphics and the analysis and synthesis of digital images. Georgiou et. al. [11] provided a polynomial algorithm for computing the covering dimension dim(X;) of a finite topological space (X;). In addition, they asked whether algorithms of the same complexity for computing the small inductive dimension ind(X;) and the large inductive dimension Ind(X;) can be developed. The first problem was solved in a previous paper [4]. Using results of the that paper, we also solve the second problem in this paper. We present a polynomial algorithm for Ind(X;), so that there are now efficient algorithms for the three most important notions of a dimension in topology. Our solution reduces the computation of Ind(X;), where the specialisation pre-order of (X;) is taken as input, to the computation of the maximal height of a specific class of directed binary trees within the partially ordered set. For the latter an efficient algorithm is presented that is based on order- and graph-theoretic ideas. Also refinements and variants of the algorithm are discussed. [ABSTRACT FROM AUTHOR]

"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. [ABSTRACT FROM AUTHOR]

Digital Bibliography and Library Project dataset is a collection of bibliographic records of computer science publications of various authors and co-authors. It contains approximately 1.5 million bibliographic records. An algorithm for an author's information retrieval is developed to retrieve details of specific author publications and correlation among authors. Further performance of an author is measured with parameters like consistency, contribution factor, stability, cooperativeness, and solidity. The work presented is tested on the DBLP dataset. Experimental results clearly support the claim that it works efficiently for retrieving specific author-publication records and its analysis with respect to suggested parameters. [ABSTRACT FROM AUTHOR]

The time complexity of algorithms, i.e., the scaling of the time required for solving a problem instance as a function of instance size, is of key interest in theoretical computer science and practical applications. In this work, we present a fully automated tool – Empirical Scaling Analyzer (ESA) – for performing sophisticated and detailed empirical scaling analyses. The methodological approach underlying ESA is based on a combination of automatic function fitting and bootstrap sampling; previous versions of the methodology have been used in prior work to characterize the empirical scaling behaviour of several prominent, high-performance SAT and TSP solvers. ESA is applicable to any algorithm or system, as long as running time data can be collected on sets of problem instances of various sizes. We present results from rigorous stress-testing to critically assess ESA on scenarios with challenging characteristics. We also give an overview of empirical scaling results obtained using ESA. [ABSTRACT FROM AUTHOR]