Fundamenta Informaticae - Volume 107, issue 4

Authors: Andary, Philippe | Patrou, Bruno | Valarcher, Pierre

Article Type: Research Article

Abstract: We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

Keywords: primitive recursion, algorithms, abstract state machines, structural complexity

DOI: 10.3233/FI-2011-405

Citation: Fundamenta Informaticae, vol. 107, no. 4, pp. 313-330, 2011

Authors: Bhattacharya, Bhaswar B.

Article Type: Research Article

Abstract: In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A k-chain of a regular n-gon is the segment of the boundary of the regular n-gon formed by a set of k (≤ n) consecutive vertices of the regular n-gon. We show that for every odd positive integer k, there exists an integer N(k), such that the Fermat-Weber point of a set of k fixed points lying on the vertices a k-chain of a n-gon coincides with a vertex of the chain …whenever n ≥ N(k). We also show that $\lceil$πm(m + 1) - π2 /4$\rceil$ ≤ N(k) ≤ $\lfloor$πm(m + 1) + 1$\rfloor$, where k (= 2m + 1) is any odd positive integer. We then extend this result to a more general family of point set, and give an O(hk log k) time algorithm for determining whether a given set of k points, having h points on the convex hull, belongs to such a family. Show more

Keywords: Computational geometry, Facility location, Fermat-Weber Problem, Optimization, Polygons

DOI: 10.3233/FI-2011-406

Citation: Fundamenta Informaticae, vol. 107, no. 4, pp. 331-343, 2011

Authors: Cojocaru, Liliana

Article Type: Research Article

Abstract: In this paper we investigate the communication and cooperation phenomenon in Cooperating Distributed Grammar Systems (henceforth CDGSs). In this respect, we define several complexity structures and two complexity measures, the cooperation and communication complexity measures. These measures are studied with respect to the derivation modes and fairness conditions under which CDGSs may work. We deal with trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with regular, linear, and context-free components. Cooperation and communication processes in CDGSs with regular and linear components are of equal complexity. The two (equal) cooperation and communication complexity measures are either …constant or linear, as functions of lengths of words in the generated language. The same result holds for the cooperation and communication complexity of q-fair languages generated by CDGSs with regular and linear components. For the case of non-constant communication (cooperation) the time and space used by a nondeterministic multitape Turing machine to recognize weakly q-fair languages are linear, as is the communication (cooperation) complexity. For CDGSs with context-free components the cooperation and communication complexity may be different. These measures are either linear or logarithmic functions, in terms of lengths of words in the generated language. In order to find trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with context-free components we study asymptotic behavior of growth functions characteristic to these measures. We prove that languages generated by CDGSs with context-free components are accepted by nondeterministic multitape Turing machines either in quadratic time, linear space, and with cooperation complexity that varies from logarithmic to linear, or in polynomial or exponential time and space, and linear cooperation complexity. Show more

Keywords: CDGSs, q-fair languages, Szilard languages, Turing machines, cooperation and communication complexity, time and space complexity

DOI: 10.3233/FI-2011-407

Citation: Fundamenta Informaticae, vol. 107, no. 4, pp. 345-378, 2011

Authors: Faber, Wolfgang | Leone, Nicola | Maratea, Marco | Ricca, Francesco

Article Type: Research Article

Abstract: The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient …implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits. Show more

Keywords: Knowledge Representation and Reasoning, Nonmonotonic Reasoning, Answer Set Programming, Heuristics, Aggregates

DOI: 10.3233/FI-2011-408

Citation: Fundamenta Informaticae, vol. 107, no. 4, pp. 379-413, 2011

Authors: Feng, Dingcheng | Chen, Feng | Xu, Wenli

Article Type: Research Article

Abstract: Learning Markov boundaries from data without having to learn a Bayesian network first can be viewed as a feature subset selection problem and has received much attention due to its significance in the wide applications of AI techniques. Popular constraint based methods suffer from high computational complexity and are usually unstable in spaces of high dimensionality. We propose a new perspective from matroid theory towards the discovery of Markov boundaries of random variable in the domain, and develop a learning algorithm which guarantees to recover the true Markov boundaries by a greedy learning algorithm. Then we use the precision matrix …of the original distribution as a measure of independence to make our algorithm feasible in large scale problems, which is essentially an approximation of the probabilistic relations with Gaussians and can find possible variables in Markov boundaries with low computational complexity. Experimental results on standard Bayesian networks show that our analysis and approximation can efficiently and accurately identify Markov boundaries in complex networks from data. Show more

Keywords: Markov boundary, conditional independence, matroid

DOI: 10.3233/FI-2011-409

Citation: Fundamenta Informaticae, vol. 107, no. 4, pp. 415-434, 2011