Teaching languages on the computer at the University of Turin: CAI and interactive videodisc

This paper describes the use of computer-assisted instruction for the teaching of languages at the University of Turin. The computer is used in several ways: testing; classroom reinforcement; recovery; and text comprehension. We describe these various activities and attempt to pinpoint the advantages the computer offers over traditional media. In the final section, we explain how we have exploited two videodiscs for language teaching purposes.Enrico Borello has been associate professor of Applied Linguistics at the University of Florence since coming from the University of Turin in 1982. His research covers many areas of humanities computing and he is currently developing educational software, including interactive videodisc for the teaching of foreign languages. His publications include Linguistics and Communication, Turin, 1990; and several articles on computer-assisted learning.     

On the message complexity of binary byzantine agreement under crash failures

Summary The binary Byzantine Agreement problem requiresn–1 receivers to agree on the binary value broadcast by a sender even when some of thesen processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of meassages needed in the failure-free executions of such protocols.More specifically, we prove that any protocol that tolerates up tot faulty processes requires a total of at leastn+t–1 messages in its failure-free executions —and, therefore, at least [(n+t–1)/2] messages in the worst case and min (P ₀,P ₁)·(n+t–1) meassages in the average case, whereP _v is the probability that the value of the bit that the sender wants to broadcast isv. We also give protocols that solve the problem using only the minimum number of meassages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of meassage bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of meassage bits. Vassos Hadzilacos received a BSE from Princeton University in 1980 and a PhD from Harvard University in 1984, both in Computer Science. In 1984 he joined the Department of Computer Science at the University of Toronto where he is currently an Associate Professor. In 1990–1991 he was visiting Associate Professor in the Department of Computer Science at Cornell University. His research interests are in the theory of distributed systems. Eugene Amdur obtained a B. Math from the University of Waterloo in 1986 and a M.Sc. from the University of Toronto in 1988. He is currently employed by the Vision and Robotics group at the University of Toronto in both technical and research capacities. His current areas of interest are vision, robotics, and networking. Samuel Weber received his B.Sc. in Mathematics and Computer Science and his M.Sc. in Computer Science from the University of Toronto. Currently, he is at Cornell University as a Ph.D. student in Computer Science with a minor in Psychology. His research interests include distributed systems, and the semantics of programming languages.     

The evolution of the SR language

As a result of our experience, the SR distributed programming language has evolved. One change is that resources and processes are now dynamic rather than static. Another change is that operations and processes are now integrated in a novel way: all the mechanisms for process interaction — remote and local procedure call, rendezvous, dynamic process creation, and asynchronous message passing — are expressed in similar ways. This paper explains the rationale for these and other changes. We examine the fundamental issues faced by the designers of any distributed programming language and consider the ways in which these issues could be addressed. Special attention is given to the design objectives of expressiveness, simplicity, and efficiency. Gregory R. Andrews was born in Olympia, WA, in 1947. He received the B.S. degree in mathematics from Stanford University in 1969 and the Ph.D. degree in computer science from the University of Washington in 1974. From 1974–1979 he was an Assistant Professor of Computer Science at Cornell University. Since 1979 he has been an Associate Professor of Computer Science at the University of Arizona. During 1983–1984, he was a Visiting Associate Professor of Computer Science at the University of Washington. He has also consulted for the U.S. Army Electronics Command and Cray Laboratories. His research interests include concurrent programming languages and distributed operating systems; he is currently co-authoring (with Fred Schneider) a textbook on concurrent programming. Dr. Andrews is a member of the Association for Computing Machinery (ACM). From 1980–1983 he was Secretary-Treasurer of the ACM Special Interest Group on Operating Systems. He has also been on the Board of Editors of Information Processing Letters since 1979. Ronald A. Olsson was born in Huntington, NY, in 1955. He received B.A. degrees in mathematics and computer science and the M.A. degree in mathematics from the State University of New York, College at Potsdam, in 1977. In 1979, he received the M.S. degree in computer science from Cornell University. He was a Lecturer of Computer Science at the State University of New York, College at Brockport, from 1979 to 1981. Since 1981 he has been a graduate student in computer science at the University of Arizona and will complete his Ph.D. in June 1986. His research interests include programming languages, operating systems, distributed systems, and systems software. Mr. Olsson is a student member of the Association for Computing Machinery.This work is supported by NSF under Grant DCR-8402090, and by the Air Force Office of Scientific Research under Grant AFOSR-84-0072. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not-withstanding any copyright notices thereon     

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.     

The Common Style of Common Sense

The extraordinary impact of Thomas Paine's Common Sense has often been attributed to its style — to the simplicity and forcefulness with which Paine expressed ideas that many others before him had expressed. Comparative analysis of Common Sense and other pre-Revolutionary pamphlets suggests that Common Sense was indeed stylistically unique; no other pamphleteer came close to matching Paine's combination of simplicity and forcefulness.Lee Sigelman is Professor of Political Science at The George Washington University. His research interests range widely throughout the social sciences, including research methods, mass communication, political behavior, and political culture. He has recently published articles in Computers and the Humanities analyzing the work of Raymond Chandler and Edith Wharton.Colin Martindale is Professor of Psychology at the University of Maine. He is author of a number of articles and books on content analysis, literary history, and other topics. A recent book is The Clockwork Muse: The Predictability of Artistic Change (New York: Basic Books). He is Executive Editor of Empirical Studies of the Arts.Dean McKenzie is Professional Officer/Statistician for Psychological Medicine, Monash University, Melbourne, Australia. He is author of several articles concerned with machine learning and artificial intelligence.     

A project for Latin Lexicography: 2. A Latin morphological analyzer

This article describes a second aspect of the Project for Latin Lexicography (see previous article). We here concentrate on two aspects of the project. First, we describe the morphological analyzer, which comprises a base dictionary, a table of suffixes, a table of endings and a table of postfixes. Second, we describe the lemmatization module, which operates by reference to a series of grammatical codes or information given for the base, and reference codes. Giuseppe Cappelli is a program analyst working at the Institute for Computational Linguistics of the National Research Council of Pisa. He has written the software for the morphosyntactic analyzer of the Spanish language. He has also written the software for the morphological analyser of the Latin language in collaboration with the Classics Department of Turin University. At present, Cappelli is involved in the study of child language. His publications include (with M.N. Catarsi, A. Saba and D. Ratti) A Morphosyntactic analyser for Spanish, Computers in Literary and Linguistic Research, Pisa: Giardini Editori, 1982; and (with A. Bozzi) A Latin Morphological Analyser, in Data Base Oriented Source Editions, Kalamazoo, Michigan, 1988. Andrea Bozzi is a researcher at the Institute for Computational Linguistics of the National Research Council of Pisa. She has been involved in the automatic processing of late Latin translations of Hypocratical texts, from a lexicographical point of view. She has also implemented a morphological analyzer of the Latin language. Her publications include Note di lessicografia ippocratica. Il trattato sulle arie, le acque, i luoghi, Roma, 1982, and Il trattamento delle variante nello spoglio elttronico di un testo. Una prova sui Carmina di Claudiano, in MD, 16 (1986),155–79.     

An improved upperbound for distributed election in bidirectional rings of processors

We present a distributed algorithm for electing a leader (i. e., breaking symmetry) in bidirectional rings ofN processors with no global sense of orientation, that uses at most 1.44 ...N logN+O(N) messages in the worst case.Jan van Leeuwen received his M. Sc. degree in 1969 (cum laude) and the Ph.D. degree in 1972 from the University of Utrecht, Utrecht, The Netherlands. He held a postdoctorate fellowship in computer science at the University of California at Berkeley (1972–1973), visiting assistant professorship in computer science at the State University of New York at Buffalo (1973–1974, 1975–1976), and a visiting associate professorship in computer science at The Pennsylvania State University, University Park (1976–1977). In 1977 he was appointed Associate Professor of Computer Science at the University of Utrecht and became head of the new Department of Computer Science at this university. He is presently Full Professor of Computer Science. Dr. van Leeuwen is active in many disciplines within computer science. His primary research interests are fundamental studies in varied areas of computer science, viz. the analysis and complexity of computer algorithms, in both a theoretical and an applied sense (e. g. data structures, machine models, VLSI, parallel and distributed computing, and cryptography).Richard B. Tan is an Associate Professor of Mathematics and Computer Science at the University of Sciences and Arts of Oklahoma. He spends his summers at the University of Utrecht, the Netherlands. His research interests are in distributed computation and graph algorithms. He received the B. Sc. in Physics from Beloit College, WI., the M.S. in Computer Science and the Ph.D. (in 1980) in Mathematics from the University of Oklahoma.This work was done while the second author was visiting the University of Utrecht, supported by a grant of the Netherlands Organization for the Advancement of Pure Research (ZWO)     

Implementation of hierarchical F-channels for high-performance distributed computing

Summary High performance distributed computing systems require high performance communication systems.F-channels andHierarchical F-channels address this need by permitting a high level of concurrency like non-FIFO channels while retaining the simplicity of FIFO channels critical to the design and proof of many distributed algorithms. In this paper, we present counter-based implementations for F-channels and Hierarchical F-channels using message augmentation-appending control information to a message. These implementations guarantee that no messages are unnecessarily delayed at the receiving end. Keith Shafer received the B.A. degree in computer science and mathematics in 1986 from Mount Vernon Nazarene College, Mount Vernon, Ohio, USA, and the M.S. and Ph.D. degrees in computer science from The Ohio State University, Columbus, Ohio, USA, in 1988 and 1992, respectively. He is currently a Senior Research Scientist at OCLC Online Computer Library Center Inco, Dublin, OH, USA. His research interests include tools for comparing logical channels and methods for automatically constructing corpus grammars from tagged documents as an aid for database preparation and document conversion. Dr. Shafer is a member of the IEEE Computer Society. Mohan Ahuja received the M.A. degree in 1983 and the Ph.D. degree in 1985, both in computer science, from the University of Texas at Austin. He is currently with Department of Computer Science and Engineering, Univ. of California, San Diego. His recent research contributions include Global Flushing, message receipt in Receive-Phases, Incremental Publication of a Partial Order, Design of Highways (a high-performance distributed programming system) and — in collaboration with others — Passive-space and Time View, Performance evaluation of F-Channels, and Units of Computation in Fault-Tolerant Distributed Systems. His current research interests are in high-performance distributed communication and computing architectures, building high-performance systems, distributed operating systems, distributed algorithms, fault tolerance, and performance evaluation.Parts of this paper appeared in two conference papers, (1) Distributed Modeling and Implementation of High Performance Communication Architectures, in proceedings of the Thirteenth IEEE International Conference on Distributed Computing Systems, papes 56–65, 1993 and (2) Process-Channel_agem-Process model of asynchronous distributed communication, in proceedings of the Twelfth IEEE International Conference on Distributed Computing Systems, pages 4–11, 1992     

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 …     

Adaptive neighborhood selection in peer-to-peer networks based on content similarity and reputation

To address the two most critical issues in P2P file-sharing systems: efficient information discovery and authentic data acquisition, we propose a Gnutella-like file-sharing protocol termed Adaptive Gnutella Protocol (AGP) that not only improves the querying efficiency in a P2P network but also enhances the quality of search results at the same time. The reputation scheme in the proposed AGP evaluates the credibility of peers based on their contributions to P2P services and subsequently clusters nodes together according to their reputation and shared content, essentially transforming the P2P overlay network into a topology with collaborative and reputed nodes as its core. By detecting malicious peers as well as free-riders and eventually pushing them to the edge of the overlay network, our AGP propagates search queries mainly within the core of the topology, accelerating the information discovery process. Furthermore, the clustering of nodes based on authentic and similar content in our AGP also improves the quality of search results. We have implemented the AGP with the PeerSim simulation engine and conducted thorough experiments on diverse network topologies and various mixtures of honest/dishonest nodes to demonstrate improvements in topology transformation, query efficiency, and search quality by our AGP.

Hierarchical encoding of text: Technical problems and SGML solutions

One recurring theme in the TEI project has been the need to represent non-hierarchical information in a natural way — or at least in a way that is acceptable to those who must use it — using a technical tool that assumes a single hierarchical representation. This paper proposes solutions to a variety of such problems: the encoding of segments which do not reflect a document's primary hierarchy; relationships among non-adjacent segments of texts; ambiguous content; overlapping structures; parallel structures; cross-references; vague locations.David T. Barnard is Professor of Computing and Information Science at Queen's University. His research interests are in structured text processing and the compilation of programming languages. His recent publications include Tree-to-tree Correction for Document Trees, Queen's Technical Report, and Error Handling in a Parallel LR Substring Parser,Computer Languages, 19,4 (1993) 247–59.Lou Burnard is Director of the Oxford Text Archive at Oxford University Computing Services, with interests in electronic text and database technology. He is European Editor of the Text Encoding Initiative's Guidelines.Jean-Pierre Gaspart is with Associated Consultants and Software Engineers.Lynne A. Price (Ph.D., computer sciences, University of Wisconsin-Madison) is a senior software engineer at Frame Technology Corp. Her main area of research has been representing text structure for automatic processing. She has served on both the US and international SGML standards committee for several years and is the editor ofInternational Standard ISO/IEC 13673 on Conformance Testing for Standard Generalized Markup Language (SGML) Systems.C. M. Sperberg-McQueen is a Senior Research Programmer at the academic computer center of the University of Illinois at Chicago; his interests include medieval Germanic languages and literatures and the theory of electronic text markup. Since 1988 he has been editor in chief of the ACH/ACL/ALLC Text Encoding Initiative.Giovanni Battista Varile works for the Commission of the European Communities.This paper is derived from a working paper of the Metalanguage Committee entitled Notes on SGML Solutions to Markup Problems which was produced following a meeting of the committee in Luxembourg. The co-authors all participated in that meeting and provided input to this paper. Others serving on the committee at other times included David Durand (Boston University), Nancy Ide (Vassar College) and Frank Tompa (University of Waterloo).     

Appraising fairness in languages for distributed programming

The relations among various languages and models for distributed computation and various possible definitions of fairness are considered. Natural semantic criteria are presented which an acceptable notion of fairness should satisfy. These are then used to demonstrate differences among the basic models, the added power of the fairness notion, and the sensitivity of the fairness notion to irrelevant semantic interleavings of independent operations. These results are used to show that from the considerable variety of commonly used possibilities, only strong process fairness is appropriate forCSP if these criteria are adopted. We also show that under these criteria, none of the commonly used notions of fairness are fully aceptable for a model with an n-way synchronization mechanism. The notion of fairness most often mentioned for Ada is shown to be fully acceptable. For a model with nonblockingsend operations, some variants of common fairness definitions are appraised, and two are shown to satisfy the suggested criteria. Krzysztof R. Apt was born in 1949 in Poland. Received his Ph.D. in 1974 from Polish Academy of Sciences in Warsaw in mathematical logic. From 1974 until 1981 worked at various scientific institutions in the Netherlands and from 1981 until 1987 at C.N.R.S. in Paris, France. Spent 1985 as a visiting scientist at IBM Research Centre in Yorktown Heights, U.S.A. Currently holding an Endowed Professorship at the Department of Computer Sciences at the University of Texas at Austin; also a senior research scientist at the Centre for Mathematics and Computer Science in Amsterdam, the Netherlands. His research interests include program correctness and semantics, methodology of distributed computing, use of logic as a programming language and non-standard forms of reasoning. He has served on editorial boards of a number of journals and program committees of numerous conferences in computer science. Lectured in a dozen countries on four continents. Also, he has run two marathons and crossed Sumatra on a bicycle. Shmuel Katz received his B.A. in Mathematics and English Literature from U.C.L.A., and his M.Sc. and Ph.D. in Computer Science (1976) from the Weizmann Institute in Rehovot, Israel. From 1976 to 1981 he was a researcher at the IBM Israel Scientific Center. Presently, he is a Senior Lecturer in the Computer Science Department at the Technion in Haifa, Israel. In 1977–78, he visited for a year at the University of California, Berkeley, and in 1984–85 was at the University of Texas at Austin. He has also been a consultant for the MCC Software Technology Program. His research interests include the methodology of programming, specification methods, program verification and semantics, distributed programming, data structures, and programming languages. Nissim Francez received his B.A. in Mathematics and Philosophy from the Hebrew University in Jerusalem, and his M.Sc. and Ph.D. in computer science (1976) from the Weizmann Institute of Science, Rehovot, Israel. In 1976–77 he spent a postdoctoral year at Queen's university, Belfast, where he was introduced by C.A.R. Hoare to CSP. In 1977–78 he was an assistant professor at USC, Los Angeles. From 1978 he is with the Computer Science Department at the Technion. In 1982–83 he was on a sabbatical leave at IBM T.J. Watson Research Center. He has been a consultant for MCC's software technology program, working on multiparty activities in distributed systems. He had summer appointments in Harvard University, IBM T.J. Watson Research Center, Utrecht University, CWI (Amsterdam) and at MCC. He also served in several program committees. His research interests include program verification and the semantics of programming languages, mainly for concurrent and distributed programming. Is also interested in logic programming and recursive query evaluation and in compiler constration. He is the author of the first book onFairness. Unfortunately, he is incapable of Marathon running...     

On some operations on strings suggested by gene assembly in ciliates

We define three operations on strings and languages suggested by the process of gene assembly in hypotrichous ciliates. This process is considered to be a prine example of DNA computing in vivo. This paper is devoted to some computational aspects of these operations from a formal language point of view. The closure of the classes of regular and context-free languages under these operations is settled. Then, we consider theld-macronuclear language of a given languageL, which consists of allld-macronuclear strings obtained from the strings ofL by iteratively applying the loop-direct repeat-excision. Finally, we discuss some open problems and further directions of research. Rudolf Freund: He received his master and doctor degree in computer science from the Vienna University of Technology, Austria, in 1980 and 1982, respectively. In 1986, he received his master degree in mathematics and physics from the University Vienna, Austria. In 1988 he joined the Vienna University of Technology in Austria, where he became an Associate Professor in September 1995. He has given various lectures in theoretical computer science, especially on formal languages and automata. His research interests include array and graph grammars, regulated rewritung, infinite words, syntactic pattern recognition, neural networks, and especially models and systems for biological computing. In these fields he is author of more than sixty scientific papers. Carlos Martín-Vide: He is Professor and Head of the Research Group on Mathematical Linguistics at Rovira i Virgili University, Tarragona, Spain. His specialities are formal language theory and mathematical linguistics. His last volume edited is Where Mathematics, Computer Science, Linguistics and Biology Meet (Kluwer, 2001, with V. Mitrana). He published 150 papers in conference proceedings and journals such as: Acta Informatica, BioSystems. Computational Linguistics, Computers and Artificial Intelligence, Information Processing Letters, Information Sciences, International Journal of Computer Mathematics, New Generation Computing, Publicationes Mathematicae Debrecen, and Theoretical Computer Science. He is the editor-in-chief of the journal Grammars (Kluwer), and the chairman of the 1st International PhD School in Formal Languages and Applications (2001–2003). Victor Mitrana, Ph.D.: He is Professor of Computer Science at the Faculty of Mathematics, University of Bucharest. He received his MSc and PhD from the University of Bucharest in 1986 and 1993, respectively. In 1999 he was awarded with the “Gheorghe Lazar” Prize for Mathematics of the Romanian Academy. His research interests include: formal language theory and applications, combinatorics on words, computational models inspired from biology, mathematical linguistics. In these areas, he published three books, more than 100 papers, and edited two books. He is an associate editor of “The Korean Journal of Computational and Applied Mathematics” and an editor of “Journal of Universal Computer Science”.     

Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection

Summary This paper presents an efficient randomized emulation ofsingle-hop radio networkwith collision detection onmulti-hop radio networkwithout collision detection. Each step of the single-hop network is emulated by rounds of the multi-hop network and succeeds with probability 1–. (n is the number of processors,D the diameter and the maximum degree). It is shown how to emulate any polynomial algorithm such that the probability of failure remains . A consequence of the emulation is an efficient randomized algorithm for choosing a leader in a multi-hop network. Reuven Bar-Yehuda was born in Iran, on July 17th 1951. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1978, 1980, and 1983, respectively. He is currently a Senior Lecturer of Computer Science at the Technion. From 1984 to 1986, he was a visiting assistant professor in the Computer Science Dept. at the Duke Univesity His research interests include computational geometry, VLSI, graph algorithms and distributed algorithms. Oded Goldreich was born in Tel-Aviv, Israel, on February 4th 1957. Received B.A., M.Sc., and D.Sc. in Computer Science from the Technion — Israel Institute of Technology, Haifa, Israel, in 1980, 1982, and 1983, respectively. He is currently an Associate Professor of Computer Science at the Technion. From 1983 to 1986, he was a postdoctoral fellow at MIT's Laboratory for Computer Science. His research interests include cryptography and related areas, relation between randomness and algorithms, and distributed computation. Alon Itai was born in Scotland, on December 12th 1946. Received B.Sc. in Mathematics from the Hebrew University in Jerusalem in 1969. M.Sc., and Ph.D. in Computer Science from the Weizmann Institute of Science, Rehovot, Israel in 1971 and 1976. He is currently an Associate Professor of Computer Science at the Technion. His research interests include randomized and distributed algorithms, computational learning theory and performance evaluation.The second author was partially supported by grant No. 86-00301 from the United States—Israel Bi-national Science Foundation BSF), Jerusalem, Israel.     

Global Control of Robotic Highway Safety Markers: A Real-time Solution

This paper presents the design and implementation of a real-time solution for the global control of robotic highway safety markers. Problems addressed in the system are: (1) poor scalability and predictability as the number of markers increases, (2) jerky movement of markers, and (3) misidentification of safety markers caused by objects in the environment.An extensive analysis of the system and two solutions are offered: a basic solution and an enhanced solution. They are built respectively upon two task models: the periodic task model and the variable rate execution (VRE) task model. The former is characterized by four static parameters: phase, period, worst case execution time and relative deadline. The latter has similar parameters, but the parameter values are allowed to change at arbitrary times.The use of real-time tasks and scheduling techniques solve the first two problems. The third problem is solved using a refined Hough transform algorithm and a horizon scanning window. The approach decreases the time complexity of traditional implementations of the Hough transform with only slightly increased storage requirements.Supported, in part, by grants from the National Science Foundation (CCR-0208619 and CNS-0409382) and the National Academy of Sciences Transportation Research Board-NCHRP IDEA Program (Project #90).Jiazheng Shi received the B.E. and M.E. degrees in electrical engineering from Beijing University of Posts and Telecommunications in 1997 and 2000, respectively. In 2000, he worked with the Global Software Group, Motorola Inc. Currently, he is a Ph.D. candidate in the Computer Science and Engineering Department at the University of Nebraska–Lincoln. His research interests are automated human face recognition, image processing, computer vision, approximate theory, and linear system optimization.Steve Goddard is a J.D. Edwards Associate Professor in the Department of Computer Science & Engineering at the University of Nebraska–Lincoln. He received the B.A. degree in computer science and mathematics from the University of Minnesota (1985). He received the M.S. and Ph.D. degrees in computer science from the University of North Carolina at Chapel Hill (1995, 1998).His research interests are embedded, real-time and distributed systems with emphases in high assurance systems engineering and real-time, rate-based scheduling theory.Anagh Lal received a B.S. degree in Computer Science from the University of Mumbai (Bombay), Mumbai, in 2001. He is currently a graduate research assistant at the University of Nebraska–Lincoln working on a M.S. in Computer Science, and a member of the ConSystLab. His research interests lie in Databases, Constraint Processing and Real Time Systems. Anagh will be graduating soon and is looking for positions at research institutions.Jason Dumpert received a B.S. degree in electrical engineering from the University of Nebraska–Lincoln in 2001. He received a M.S. degree in electrical engineering from the University of Nebraska-Lincoln in 2004. He is currently a graduate research assistant at the University of Nebraska-Lincoln working on a Ph.D. in biomedical engineering. His research interests include mobile robotics and surgical robotics.Shane M. Farritor is an Associate Professor in the University of Nebraska–Lincolns Department of Mechanical Engineering. His research interests include space robotics, surgical robotics, biomedical sensors, and robotics for highway safety. He holds courtesy appointments in both the Department of Surgery and the Department of Orthopaedic Surgery at the University of Nebraska Medical Center, Omaha. He serves of both the AIAA Space Robotics and Automation technical committee and ASME Dynamic Systems and Control Robotics Panel. He received M.S. and Ph.D. degrees from M.I.T.     

Self-stabilizing multi-token rings

Summary A distributed system consists of a set of loosely connected machines that do not share a global memory. The system isself-stabilizing if it can be started in any global state and achieves consistency all by itself. This also means that the system can deal withinfrequent errors. This paper presents self-stabilizing multi-token rings. A multitoken ring is a generalization of a (one-)token ring. The algorithms presented are generalizations of a self-stabilizing mutual exclusion algorithm by Dijkstra [5] which can also be viewed as a token ring. We develop the algorithms in a stepwise manner, to show how and why we arrived at the final multi-token rings. The final parameterized algorithm represents a set of algorithms, one for each choice of the parameter. This enables one to select the algorithm with an optimal trade-off in desired flexibility versus memory requirements and stabilization time. Mitchell Flatebo received the B.S. degree in Mathematics (1990), the B.S. degree in Computer Science (1990), the M.S. degree in Mathematics (1992), and the M.S. degree in Computer Science (1993) from the University of Nevada, Las Vegas. He is currently a software engineer for Loral Space and Range Systems. His research interests include distributed systems, fault-tolerant computing, and self-stabilization. Ajoy Kumar Datta received the Ph.D. degree in Computer Science from the Jadavpur University, Calcutta, India in 1983. He is currently an Associate Professor of Computer Science at the University of Nevada, Las Vegas. His area of research is distributed and fault-tolerant computing —algorithms and self-stabilization. Anneke Schoone received an M.Sc. degree in Biology in 1978, an M.Sc. degree in Mathematics in 1981, and a Ph.D. degree in Computer Science in 1991 from Utrecht University (The Netherlands). Currently she is a senior research associate at the Department of Computer Science of Utrecht University, supported by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity) of the EC. Her research interests include assertional verification of distributed algorithms and the concept of self-stabilization.The research of this author was supported partially by the ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity), and partially by the Netherlands Organization for Scientific Research (NWO) under contract NF 62-376 (NFI project ALADDIN:Algorithmic Aspects of Parallel and Distributed Systems)     

A study of words relating to youth and old age in the plays of euripides and its special implications for Euripides'' Suppliant Women

This study focuses on the imagery of youth and old age in the plays of Euripides, especially the Suppliant Women, considering frequently used words in each play according to a formula developed by Guiraud. The study identifies a motif, the rejuvenation theme, an elaborate interaction between young and old, in the Suppliant Women and in: Alcestis, Heraclidae, Andromache, Hecabe, and Heracles. The difference between the use of neos (young, new) in the Suppliant Women and in the other plays is statistically significant. This word helps Euripides contrast two different kinds of youth: the fearful, rash, and animalistic (Theban); and that which has been properly schooled and led (Athenian). The greatest ground in the Suppliant Women for praising Athens is in her treatment of the young as a politically valuable force.Eva M. Thury is associate professor of Humanities and Communications at Drexel University in Philadelphia, Pa. She is currently working with computers to produce a concordance of the Latin prose work of John Milton. She has described that process in the Winter 1987–88 issue of Academic Computing (volume 2.4, pages 6–9, 57–61). She has also recently published in Rheinisches Museum für Philologie, Arethusa and American Journal of Philology.     

Self-stabilizing depth-first token circulation on networks

Summary This paper proposes a self-stabilizing protocol which circulates a token on a connected network in nondeterministic depth-first-search order, rooted at a special node. Starting with any initial state in which the network may have no token at all or more than one token, the protocol eventually makes the system stabilize in states having exactly one circulating token. With a slight modification to the protocol —by removing nondeterminism in the search — a depth-first-search tree on the network can be constructed. The proposed protocol runs on systems that allow parallel operations. Shing-Tsaan Huang was born in Taiwan on September 4, 1949. He got his Ph.D. degree in 1985 from Department of Computer Science, University of Maryland at College Park. Before he pursued his Ph.D. degree, he had worked several years in the computer industry in Taiwan. Professor Huang is currently the chairman of the Department of Computer Science, Tsing Hua University, Taiwan, Republic of China. His research interests include interconnection networks, operating systems and distributed computing. He is a senior member of the IEEE Computer Society and a member of the Association for Computing Machinery. Nian-Shing Chen was born in Taiwan on October 21, 1961. He received his Ph.D. degree in computer science from National Tsing Hua University in 1990. Dr. Chen is currently an associate professor with the Department of Information Management at Sun Yat-Sen University of Taiwan. His research interests include distributed systems, computer networks, computer viruses and expert systems. He is a member of IEEE and Phi Tau Phi honorary society.This research is supported by National Science Council of the Republic of China under the contract NSC81-0408-E-007-05 and NSC82-0408-E-007-027     

Robust Control for Steer-by-Wire Vehicles

The design and analysis of steer-by-wire systems at the actuation and operational level is explored. At the actuation level, robust force feedback control using inverse disturbance observer structure and active observer algorithm is applied to enhance the robustness vs non-modelled dynamics and uncertain driver bio-impedance. At the operational level, the robustness aspects vs parameter uncertainties in vehicle dynamics and driver bio-impedance are issued and for a given target coupling dynamics between driver and vehicle the design task is converted to a model-matching problem. H_∞ techniques and active observer algorithms are used to design the steer-by-wire controller. Robustness issues at both levels are covered by mapping stability bounds in the space of physical uncertain parameters.Naim Bajçinca has been working as a researcher at German Aerospace Center (DLR) in Oberpfaffenhofen since 1998. He has graduated studies on Physics (1994) and Electrical Engineering (1995) at the University of Prishtina. His main interests include methods of robust and nonlinear control, model-reference control, uncertain time-delay systems with applications on haptics, active vehicle steering and master-slave systems.Rui Cortesão received the B.Sc. in Electrical Engineering., M.Sc. in Systems and Automation and Ph.D. in Control and Instrumentation from the University of Coimbra in 1994, 1997, and 2003, respectively. He has been visiting researcher at DLR for more than two years (1998–2003), working on compliant motion control, data fusion and steer-by-wire. In 2002 he was visiting researcher at Stanford University, working on haptic manipulation. He is Assistant Professor at the Electrical Engineering Department of the University of Coimbra since 2003 and researcher of the Institute for Systems and Robotics (ISR-Coimbra) since 1994. His research interest include data fusion, control, fuzzy systems, neural networks and robotics.Markus Hauschild received his Diploma in Mechatronics from Munich University of Applied Sciences in 2002. He joined the DLR Institute of Robotics and Mechatronics in 2001 working on control strategies for Harmonic Drive gears. His research interests include human-machine-interfaces, x-by-wire, and modeling of biomedical systems. In 2003 he was visiting researcher at National Yunlin University of Science and Technology, Taiwan, developing iterative learning control for compensation of periodic disturbances. In the European ENACTIVE network of excellence he is the DLR coordinator for the “actuators and sensors for haptic interfaces” activities. Presently he is a PhD student at University of Southern California in the Department of Biomedical Engineering.     

Blackboard relations in the μLog coordination model

This paper describescoordination relations, that are relations that induce the presence or absence of data on some dataspaces from the presence or absence of other data on other dataspaces. To that end we build upon previous work on the μLog model and show that the coordination relations can be easily incorporated in it. This is achieved, on the one hand, by means of novel auxiliary operations, not classically used in Linda-like languages, and, on the other hand, by a translation technique reducing the extended μLog model to the core model augmented with the auxiliary operations. Among the most significant ones are multiple read and get operations on a blackboard, readall and getall operations, and tests for the absence of data on blackboards. Although simple, the form of coordination relations we propose is quite powerful as evidenced by a few examples including relations coming from the object-oriented paradigm such as inheritance relations. Jean-Marie Jacquet, Ph.D.: He is Professor at the Institute of Informatics at the University of Namur, Belgium, and, at an honorary title, Research Associate of the Belgian National Fund for Scientific Research. He obtained a Master in Mathematics from the University of Liège in 1982, a Master in Computer Science from the University of Namur in 1984 and a Ph.D. in Computer Science from the University of Namur in 1989. His research interest are in Programming Languages and Coordination models. He has served as a reviewer and program committee member of several conferences. Koen de Bosschere, Ph.D.: He holds the degree of master of Science in Engineering of the Ghent University, and a Ph.D. from the same University. He is currently research associate with the Fund for Scientific Research — Flanders and senior lecturer at the Ghent University, where he teaches courses on computer architecture, operating systems and declarative programming languages. His research interests are coordination in parallel logic programming, computer architecture and systems software.