Cultural Heritage As a Vehicle for Basic Research in Computing Science: Pasteur's Quadrant and a Use‐Inspired Basic Research Agenda

Donald Stokes argued [ [Sto97] ] that for 50 years from the end of the Second World War to the end of the 20th century, there was an unhealthy taxonomy of research types which was formulated on a linear scale from pure to applied. The argument goes that the best research is only possible in environments which are free from contemplation of the potential uses to which results might be applied. In this paper, current research challenges in the application of ICTs to cultural heritage information are reviewed in order to consider where these applications‐linked needs require solutions that will advance the understanding of computational principles and help to develop new basic understanding in computer science, including shape manipulation and other aspects of importance in computer graphics and virtual environments. The paper draws extensively on the recently published EPOCH research agenda [ [AG07] ] for illustrations of the types of research which are required for the Cultural Heritage sector and the relationship between these and basic research challenges in Computing Science.     

Constructive negation and constraint logic programming with sets

The aim of this paper is to extend theConstructive Negation technique to the case ofCLP(SεT), a Constraint Logic Programming (CLP) language based on hereditarily (and hybrid) finite sets. The challenging aspects of the problem originate from the fact that the structure on whichCLP(SεT) is based is notadmissible closed, and this does not allow to reuse the results presented in the literature concerning the relationships betweenCLP and constructive negation. We propose a new constraint satisfaction algorithm, capable of correctly handling constructive negation for large classes ofCLP(SεT) programs; we also provide a syntactic characterization of such classes of programs. The resulting algorithm provides a novel constraint simplification procedure to handle constructive negation, suitable to theories where unification admits multiple most general unifiers. We also show, using a general result, that it is impossible to construct an interpreter forCLP(SεT) with constructive negation which is guaranteed to work for any arbitrary program; we identify classes of programs for which the implementation of the constructive negation technique is feasible. Agostino Dovier, Ph.D.: He is a researcher in the Department of Science and Technology at the University of Verona, Italy. He obtained his master degree in Computer Science from the University of Udine, Italy, in 1991 and his Ph.D. in Computer Science from the University of Pisa, Italy, in 1996. His research interests are in Programming Languages and Constraints over complex domains, such as Sets and Multisets. He has published over 20 research papers in International Journals and Conferences. He is teaching a course entitled “Special Languages and Techniques for Programming” at the University of Verona. Enrico Pontelli, Ph.D.: He is an Assistant Professor in the Department of Computer Science at the New Mexico State University. He obtained his Laurea degree from the University of Udine (Italy) in 1991, his Master degree from the University of Houston in 1992, and his Ph.D. degree from New Mexico State University in 1997. His research interests are in Programming Languages, Parallel Processing, and Constraint Programming. He has published over 50 papers and served on the program committees of different conferences. He is presently the Associate Director of the Laboratory for Logic, Databases, and Advanced Programming. Gianfranco Rossi, Ph.D.: He received his degree in Computer Science from the University of Pisa in 1979. From 1981 to 1983 he was employed at Intecs Co. System House in Pisa. From November 1983 to February 1989 he was a researcher at the Dipartimento di Informatica of the University of Turin. Since March 1989 he is an Associate Professor of Computer Science, currently with the University of Parma. He is the author of several papers dealing mainly with programming languages, in particular logic programming languages and Prolog, and extended unification algorithms. His current research interests are (logic) programming languages with sets and set unification algorithms.     

Efficient minimum spanning tree algorithms on the reconfigurable mesh

1 IntroductionLet G = (V, E) be a connected, undirected graph with a weight function W on the set Eof edges to the set of reals. A spanning tree is a subgraph T = (V, ET), ET G E, of C suchthat T is a tree. The weight W(T) of a spanning tree T is the sum of the weights of its edges.A spanning tree with the smallest possible'weight is called a minimum spanning tree (MST)of G. Computing an MST of a given weighted graph is an important problem that arisesin many applications. For this …     

Nonatomic mutual exclusion with local spinning

We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. This algorithm is derived from Yang and Anderson's atomic tree-based local-spin algorithm in a way that preserves its time complexity. No atomic read/write algorithm with better asymptotic worst-case time complexity (under the remote-mem-ory-refer-ences measure) is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity.The same cannot be said if one is interested in fast-path algorithms (in which contention-free time complexity is required to be O(1)) or adaptive algorithms (in which time complexity is required to depend only on the number of contending processes). We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process accesses Ω(log N/log log N) distinct variables to enter its critical section. Thus, fast and adaptive algorithms are impossible even if caching techniques are used to avoid accessing the processors-to-memory interconnection network.This paper was invited for inclusion in the special issue of this journal based on selected papers presented in PODC '02 (Distributed Computing 18(1)).It appears separately because of a publication delay. Yong-Jik Kimreceived a B.S. degree in Physics/Computer Science from Korea Advanced Institute of Science and Technology in 1998, and a Ph.D.degree in Computer Science from the University of Notrh Carolina at Chapel Hill in 2003. He currently works for the RDBMS group in Tmax Soft, and is otherwise occupied with his newborn daughter Darum, which means “difference” in Korean. James H. Anderson is a professor in the Department of Computer Science at the University of North Carolina at Chapel Hill. He received a B.S.degree in Computer Science from Michigan State University in 1982, an M.S. degree in Computer Science from Purdue University in 1983, and a Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. Before joining UNC-Chapel Hill in 1993, he was with the Computer Science Department at the University of Maryland between 1990 and 1993. Dr.Anderson's main research interests are within the areas of real-time systems and concurrent and distributed computing.     

Causal memory: definitions,implementation, and programming

Summary The abstraction of a shared memory is of growing importance in distributed computing systems. Traditional memory consistency ensures that all processes agree on a common order of all operations on memory. Unfortunately, providing these guarantees entails access latencies that prevent scaling to large systems. This paper weakens such guarantees by definingcausal memory, an abstraction that ensures that processes in a system agree on the relative ordering of operations that arecausally related. Because causal memory isweakly consistent, it admits more executions, and hence more concurrency, than either atomic or sequentially consistent memories. This paper provides a formal definition of causal memory and gives an implementation for message-passing systems. In addition, it describes a practical class of programs that, if developed for a strongly consistent memory, run correctly with causal memory. Mustaque Ahamad is an Associate Professor in the College of Computing at the Georgia Institute of Technology. He received his M.S. and Ph.D. degrees in Computer Science from the State University of New York at Stony Brook in 1983 and 1985 respectively. His research interests include distributed operating systems, consistency of shared information in large scale distributed systems, and replicated data systems. James E. Burns received the B.S. degree in mathematics from the California Institute of Technology, the M.B.I.S. degree from Georgia State University, and the M.S. and Ph.D. degrees in information and computer science from the Georgia Institute of Technology. He served on the faculty of Computer Science at Indiana University and the College of Computing at the Georgia Institute of Technology before joining Bellcore in 1993. He is currently a Member of Technical Staff in the Network Control Research Department, where he is studying the telephone control network with special interest in behavior when faults occur. He also has research interests in theoretical issues of distributed and parallel computing especially relating to problems of synchronization and fault tolerance.This work was supported in part by the National Science Foundation under grants CCR-8619886, CCR-8909663, CCR-9106627, and CCR-9301454. Parts of this paper appeared in S. Toueg, P.G. Spirakis, and L. Kirousis, editors,Proceedings of the Fifth International Workshop on Distributed Algorithms, volume 579 ofLecture Notes on Computer Science, pages 9–30, Springer-Verlag, October 1991The photograph of Professor J.E. Burns was published in Volume 8, No. 2, 1994 on page 59This author's contributions were made while he was a graduate student at the Georgia Institute of Technology. No photograph and biographical information is available for P.W. Hutto Gil Neiger was born on February 19, 1957 in New York, New York. In June 1979, he received an A.B. in Mathematics and Psycholinguistics from Brown University in Providence, Rhode Island. In February 1985, he spent two weeks picking cotton in Nicaragua in a brigade of international volunteers. In January 1986, he received an M.S. in Computer Science from Cornell University in Ithaca, New York and, in August 1988, he received a Ph.D. in Computer Science, also from Cornell University. On August 20, 1988, Dr. Neiger married Hilary Lombard in Lansing, New York. He is currently a Staff Software Engineer at Intel's Software Technology Lab in Hillsboro, Oregon. Dr. Neiger is a member of the editorial boards of theChicago Journal of Theoretical Computer Science and theJournal of Parallel and Distributed Computing.     

Forests, frames, and games: Algorithms for matroid sums and applications

This paper presents improved algorithms for matroid-partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned intok forests, and finding as many disjoint spanning trees as possible. The notion of a clump in a matroid sum is introduced, and efficient algorithms for clumps are presented. Applications of these algorithms are given to problems arising in the study of the structural rigidity of graphs, the Shannon switching game, and others.This is a revised and expanded version of a paper appearing in theProceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988. This research was supported in part by National Science Foundation Grants MCS-8302648 and DCR-851191.     

Rational bijection of rational sets

Summary In this paper we initiate the study of rational bijections, that is of rational transductions which are bijections of a rational (=regular) set R onto a rational set S. We present a complete and easily decidable characterization of the existence of a rational bijection between two given rational sets.This author acknowledges with pleasure the financial support of the Austrian Federal Ministry of Science and Research which allowed him to spend one week in Graz where this paper was initiated     

A practical general method for constructing LR(k) parsers

Summary The paper presents in detail the case for k=1 of a practical general method for constructing LR(k) parsers. For k=1 this method is of rival efficiency to the previous general algorithm described by the author in [21]. The method involves combining the states of an LR(k) parser as they are generated, reducing to a fraction, in the process, the number of configurations that need actually be evaluated, or for which space must be assigned — compared to such general methods as those of [1, 11, 12, 17]. The criteria of compatibility introduced for this purpose are such that the parser obtained is in practice identical in size to, or negligibly larger than, that obtained by resolving the inadequacies of an LR(o) parser (as is done for various subsets of the LR(k) grammars in [5, 8, 14, 20]).This paper is a development of one of the ideas proposed in Pager [16]. The work was supported by the National Science Foundation under Grant GJ-43362.     

Tight bounds for shared memory systems accessed by Byzantine processes

We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by Malkhi et al. [21]. We show that sticky bits are universal in the Byzantine failure model for n ≥ 3t + 1, an improvement over the previous result requiring n ≥ (2t + 1)(t + 1). Our result follows from a new strong consensus construction that uses sticky bits and tolerates t Byzantine failures among n processes for any n ≥ 3t + 1, the best possible bound on n for strong consensus. We also present tight bounds on the efficiency of implementations of strong consensus objects from sticky bits and similar primitive objects. Research supported in part by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. This work was partially completed while at AT&T Labs and while visiting the Institute for Advanced Study, Princeton, NJ. Research supported in part by US-Israel Binational Science Foundation Grant 2002246. This work was partially completed while visiting AT&T Labs. This work was partially completed while at AT&T Labs. Research supported in part by the National Science Foundation under Grant No. CCR-0331584. A preliminary version of the results presented in this paper appeared in [23].     

Almost ASAP semantics: from timed models to timed implementations

In this paper, we introduce a parametric semantics for timed controllers called the Almost ASAP (as soon as possible) semantics. This semantics is a relaxation of the usual ASAP semantics (also called the maximal progress semantics) which is a mathematical idealization that cannot be implemented by any physical device no matter how fast it is. On the contrary, any correct Almost ASAP controller can be implemented by a program on a hardware if this hardware is fast enough. We study the properties of this semantics and show how it can be analyzed using the tool HyTech. A preliminary and short version of this paper appeared in the Proceedings of the 7th International Workshop on Hybrid Systems: Computation and Control (HSCC 2004), Lecture Notes in Computer Science, vol 2993, pp 296–310. This work was supported by the FRFC project ``Centre Fédéré en Vérification' funded by the Belgian National Science Fundation (FNRS) under grant nr 2.4530.02. Research fellow supported by the Belgian National Science Fundation (FNRS). Received November 2004 Revised April 2005 and May 2005 Accepted May 2005 by M. J. Butler