Bicentres de langages algébriques

Resume Les notions de bicentre et bicentre strict d'un langage, définies par A. De Luca, A. Restivo et S. Salemi généralisent la notion de centre d'un langage définie par M. Nivat. L'objet du présent papier est de répondre á la question suivante lorsque désigne la famille des langages algébriques ou l'une de ses sous-familles classiques:Si L appartient à , le bicentre de L (respectivement le bicentre strict de L) appartient-il à ?Le principal résultat est une réponse positive à cette question lorsqu'il s'agit de la notion de bicentre et que est un full-AFL uniforme de langages algébriques.

---

Bicenters of context-free languages

Summary The notions of bicenter and strict bicenter of a language have been defined by A. De Luca, A. Restivo and S. Salemi and are a generalisation of the notion of center of a language, defined by M, Nivat. This paper deals with the following question, when is the family of context-free languages or one of its classical subfamilies:when L is in , is the bicenter (resp. the strict bicenter) of L also in ?Concerning the notion of bicenter, the main result of the paper is a positive answer when is a uniform full-AFL of context-free languages.

     

Axiomatic approach to total correctness of programs

Summary We present here an axiomatic approach which enables one to prove by formal methods that his program is totally correct (i.e., it terminates and is logically correct—does what it is supposed to do). The approach is similar to Hoare's approach [3] for proving that a program is partially correct (i.e., that whenever it terminates it produces correct results). Our extension to Hoare's method lies in the possibility of proving both correctness and termination by one unified formalism. One can choose to prove total correctness by a single step, or by incremental proof steps, each step establishing more properties of the program.     

Procédures de reprise dans les systèmes de gestion de base de données réparties

Summary In this paper, two recovery techniques used to restore the integrity of the distributed database management system operating in the presence of intermittent failures and with a checkpointing and roll-back recovery scheme are analysed and compared. A mathematical model of the distributed database management system is proposed to evaluate its disponibility at the updating and interrogating operations in the case of one, two, three and four distributed copies. Numerical illustrations are presented and it is shown that the recovery procedure based on the transfert of the valid copies across the network is better in some given conditions of processing of the distributed database management system.

---

---

Cette recherche a été effectuée dans le cadre de la convention de recherche IRIA-SIRIUS n77077

---

Equipe de Recherche Associée au C.N.R.S. n 452 Al Khowarizmi     

Reasoning about programs in continuation-passing style

Plotkin's _v -calculus for call-by-value programs is weaker than the -calculus for the same programs in continuation-passing style (CPS). To identify the call-by-value axioms that correspond to on CPS terms, we define a new CPS transformation and an inverse mapping, both of which are interesting in their own right. Using the new CPS transformation, we determine the precise language of CPS terms closed under -transformations, as well as the call-by-value axioms that correspond to the so-called administrative -reductions on CPS terms. Using the inverse mapping, we map the remaining and equalities on CPS terms to axioms on call-by-value terms. On the pure (constant free) set of -terms, the resulting set of axioms is equivalent to Moggi's computational -calculus. If the call-by-value language includes the control operatorsabort andcall-with-current-continuation, the axioms are equivalent to an extension of Felleisenet al.'s _v -C-calculus and to the equational subtheory of Talcott's logic IOCC.This article is a revised and extended version of the conference paper with the same title [42]. The technical report of the same title contains additional material.The authors were supported in part by NSF grant CCR 89-17022 and by Texas ATP grant 91-003604014.     

Computer enhanced assessment of case-notes in studies of psychopathology: The example of an autistic subject

Case report notes on encounters and exchanges between a clinician and a patient are a rich and irreplaceable source of information in studies of psychopathology. The analysis and exploitation of these notes may be considerably enhanced by transcribing the original notes to computer text files, and subsequently submitting these files to computerized reading. This makes it possible to take account both of qualitative and quantitative features of the behaviour and events described in the notes. Notes taken during encounters with an autistic subject were analyzed in this way. The subject's verbal and gestural repertoires were identified, together with their relative frequencies, their principal associations, and their trends over successive encounters for the items described. The method also made it possible to specify the way in which the Observer was involved in encounters, and his role in them. Major conclusions were that the autistic subject distinctly avoided triadic situations, preferentially pronounced words and phonemes similar to those of his own name, and did not distinguish between the representations he had of persons, objects, places, gestures and words. He also failed to distinguish between the representation he had of himself and of his own name.J.-M. Vidal (Docteur d'Etat, 1976) is Chargé de Recherche CNRS. He studied the behavioral process of attachment in animals before studying discontinuities of mind between animals and humans, and psychopathological processes of non-attachment in autistic subjects. He has published, Motivation et attachement, inEncyclopédie de la Pléiade, Paris: Gallimard, 1987, and Evolution des psychismes et évolution des organismes, inDarwinisme et Société, Paris: Presses Universitaires de France, 1992. R. Quris is Ingénieur de Recherche CNRS. He specializes in the application of linear algebraic models in multivariate analysis which he originally applied to behavioral data from animals. More recently, he extended these applications, with his ANATEXT program, to the analysis of lexical data drawn from clinical dialogues. He is also the author of other multivariate analysis programs:Calmat Matrix Computation Tool, v. 1.4 (1993), Exeter Software, 100 North Country Road, Setauket, NY 11733, andGTABM, gestionnaire de tableaux multiples, v. 2.0 (1994), CNRS 74E, rue de Paris, 3069 Rennes, France.     

Sur les générateurs algébriques et linéaires

Résumé Nous étudions certaines propriétés des générateurs algébriques et linéaires. Nous montrons que le langage algébrique E engendré par la grammaire: S aSbSc + d domine tous les langages algébriques par applications séquentielles fidèles. Nous en déduisons que pour tout langage algébrique L et tout générateur algébrique L, il existe une transduction rationnelle fonctionnelle et fidèle telle que L=(L). Ce résultat, qui n'est pas vérifié pour la famille, Lin, des langages algébriques linéaires, nous permet de montrer qu'aucun générateur algébrique n'appartient à la famille EDTOL. Enfin, nous établissons que si L est un générateur linéaire, L # est un générateur séquentiel pour Lin.

---

Algebraic and linear generators

Summary We study some properties of algebraic and linear generators. We show that the algebraic language E generated by the grammar: S aSbSc + d dominates every algebraic language by faithful sequential mappings. We deduce that, for every algebraic language L and every algebraic generator L, there exists a faithful rational function such that L=(L). This result, which does not hold for the family of linear languages, permits us to show that no algebraic generator belongs to the family EDTOL. Also, we prove if L is a linear generator then L # is a sequential generator for Lin.

     

Cockpit cognition: Education,the military and cognitive engineering

The goals of public education, as well as conceptions of human intelligence and learning, are undergoing a transformation through the application of military-sponsored information technologies and information processing models of human thought. Recent emphases in education on thinking skills, learning strategies, and computer-based technologies are the latest episodes in the postwar military agenda to engineer intelligent components, human and artificial, for the optimal performance of complex technological systems. Public education serves increasingly as a human factors laboratory and production site for this military enterprise, whose high performance technologies and command and control paradigms have also played central roles in the emergence of the information economy.Our final hope is to develop the brain as a natural resource ... Human intelligence will be the weapon of the future.Luis Alberto MachadoThis paper will also appear, under the title Mental Material inCyborg Worlds: The Military Information Society, eds. Les Levidow and Kevin Robins, London: Free Association Press, (in press).     

Did Frege Believe Frege's Principle?

In this essay I will consider two theses that are associated with Frege,and will investigate the extent to which Frege really believed them.Much of what I have to say will come as no surprise to scholars of thehistorical Frege. But Frege is not only a historical figure; he alsooccupies a site on the philosophical landscape that has allowed hisdoctrines to seep into the subconscious water table. And scholars in a widevariety of different scholarly establishments then sip from thesedoctrines. I believe that some Frege-interested philosophers at various ofthese establishments might find my conclusions surprising.Some of these philosophical establishments have arisen from an educationalmilieu in which Frege is associated with some specific doctrine at theexpense of not even being aware of other milieux where other specificdoctrines are given sole prominence. The two theses which I will discussillustrate this point. Each of them is called Frege's Principle, but byphilosophers from different milieux. By calling them milieux I do not want to convey the idea that they are each located at some specificsocio-politico-geographico-temporal location. Rather, it is a matter oftheir each being located at different places on the intellectuallandscape. For this reason one might (and I sometimes will) call them(interpretative) traditions.     

CesiumSpray: a Precise and Accurate Global Time Service for Large-scale Systems

In large-scale systems, such as Internet-based distributed systems, classical clock-synchronization solutions become impractical or poorly performing, due to the number of nodes and/or the distance among them. We present a global time service for world-wide systems, based on an innovative clock synchronization scheme, named CesiumSpray. The service exhibits high precision and accuracy; it is virtually indefinitely scalable; and it is fault-tolerant. It is deterministic for real-time machinery in the local area, which makes it particularly well-suited for, though not limited to, large-scale real-time systems. The main features of our clock synchronization scheme can be summarized as follows: hybrid external/internal synchronization protocol improves effectiveness of synchronization; heterogeneous failure semantics for clocks and processors improves previous lower bounds on processors; two-level hierarchy improves scalability. The root of the hierarchy is the GPS satellite constellation, which sprays its reference time over a set of nodes provided with GPS receivers, one per local network. The second level of the hierarchy performs internal synchronization, further spraying the external time inside the local network.     

EigenTracking: Robust Matching and Tracking of Articulated Objects Using a View-Based Representation

This paper describes an approach for tracking rigid and articulated objects using a view-based representation. The approach builds on and extends work on eigenspace representations, robust estimation techniques, and parameterized optical flow estimation. First, we note that the least-squares image reconstruction of standard eigenspace techniques has a number of problems and we reformulate the reconstruction problem as one of robust estimation. Second we define a subspace constancy assumption that allows us to exploit techniques for parameterized optical flow estimation to simultaneously solve for the view of an object and the affine transformation between the eigenspace and the image. To account for large affine transformations between the eigenspace and the image we define a multi-scale eigenspace representation and a coarse-to-fine matching strategy. Finally, we use these techniques to track objects over long image sequences in which the objects simultaneously undergo both affine image motions and changes of view. In particular we use this EigenTracking technique to track and recognize the gestures of a moving hand.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Long unavoidable patterns

Summary We examine long unavoidable patterns, unavoidable in the sense of Bean, Ehrenfeucht, McNulty. Zimin and independently Schmidt have shown that there is only one unavoidable pattern of length 2 ⁿ -1 on an alphabet with n letters; this pattern is a quasi-power in the sense of Schützenberger. We characterize the unavoidable words of length 2 ⁿ -2 and 2 ⁿ -3. Finally we show that every sufficiently long unavoidable word has a certain quasi-power as a subword.This work was done while the author stayed at LITP, Université Paris 6, France     

Exploiting transition locality in automatic verification of finite-state concurrent systems

In this paper we show that statistical properties of the transition graph of a system to be verified can be exploited to improve memory or time performances of verification algorithms.We show experimentally that protocols exhibit transition locality. That is, with respect to levels of a breadth-first state space exploration, state transitions tend to be between states belonging to close levels of the transition graph. We support our claim by measuring transition locality for the set of protocols included in the Mur verifier distribution .We present a cache-based verification algorithm that exploits transition locality to decrease memory usage and a disk-based verification algorithm that exploits transition locality to decrease disk read accesses, thus reducing the time overhead due to disk usage. Both algorithms have been implemented within the Mur verifier.Our experimental results show that our cache-based algorithm can typically save more than 40% of memory with an average time penalty of about 50% when using (Mur) bit compression and 100% when using bit compression and hash compaction, whereas our disk-based verification algorithm is typically more than ten times faster than a previously proposed disk-based verification algorithm and, even when using 10% of the memory needed to complete verification, it is only between 40 and 530% (300% on average) slower than (RAM) Mur with enough memory to complete the verification task at hand. Using just 300 MB of memory our disk-based Mur was able to complete verification of a protocol with about 10⁹ reachable states. This would require more than 5 GB of memory using standard Mur .     

Minimization of norms and logarithmic norms by diagonal similarities

It is a commonly occurring problem to find good norms · or logarithmic norms (·) for a given matrix in the sense that they should be close to respectively the spectral radius (A) and the spectral abscissa (A). Examples may be the certification thatA is convergent, i.e. (A)A<1 or stable, i.e. (A)(A)<0. Often the ordinary norms do not suffice and one would like to try simple modifications of them such as using an ordinary norm for a diagonally transformed matrix. This paper treats this problem for some of the ordinary norms.

---

Minimisierung von Normen und Logarithmischen Normen durch Diagonale Transformationen

Zusammenfassung Ein oft vorkommendes praktisches Problem ist die Konstruktion von guten Normen · und logarithmischen Normen (·) für eine gegebene MatrixA. Mit gut wird dann verstanden, daß A den Spektralradius (A)=max |₁| und (A) die Spektralabszisse (A)=max Re _i gut approximieren. Beispiele findet man für konvergente Matrizen wo (A)A<1 gewünscht ist, und für stabile Matrizen wo (A)(A)<0 zu zeigen ist. Wir untersuchen hier, wie weit man mit Diagonaltransformationen und dengewöhnlichsten Normen kommen kann.

     

Browsers for distributed systems: Universal paradigm or siren's song?

Webbased browsers are quickly becoming ubiquitous in the workplace. Software development managers are quick to incorporate browsers into a broad range of software development projects, often inappropriately. The purpose of this paper is to examine the technical issues relevant to incorporating browsers as a component of a commercial offtheshelf (COTS)based solution. Issues examined include portability, performance, functionality, security, human factors, distribution, installation, upgrading, componentbased development, runtime configuration management, and licensing.     

F. L. Bauer 80

Zusammenfassend lässt sich de lege lata jedenfalls festhalten, dass Softwareagenten mangels Rechtspersönlichkeit und Geschäftsfähigkeit keine eigenen Willenserklärungen abgeben und damit nicht nach Stellvertretungsrecht behandelt werden können. Prof. Dr. Peter Sester, s. S. 311     

CLSS: An Intelligent Crane Lorry Scheduling System

Companies that provide crane-lorry services are faced with the daily need to perform vehicle and driver allocation and scheduling. Many companies still do this manually due to the lack of suitable technologies. This manual approach is both time consuming and inaccurate and most probably will not lead to an optimized plan that can reduce operational costs. In this paper, we describe the design of a system called Crane Lorry Scheduling System (CLSS) that we have developed for the largest crane lorry company in Hong Kong. A crane lorry company is a company that provides lorries with different types of mounted crane equipment and drivers to service different types of moving and lifting jobs. CLSS is a Web-based application that streamlines communication with customers, subcontractors and employees/lorry drivers. We modeled the lorry-assignment problem as a constraint-satisfaction problem (CSP) algorithm, which we call the Crane Lorry Optimizing Engine (CLOE). CLOE was designed to be easily customizable to match the needs and requirements of different crane lorry companies. We experimented with two versions of CLOE, regular CLOE that finds best solutions and X-CLOE that finds optimal solutions. Results from our tests show that CLOE is faster and generates better quality plans than the manual approach.     

A database for linguists: Intelligent querying and increase of data

What do database (DB) querying and information retrieval imply for linguistics? What are data for the linguist? How can one envisage efficient access to data? I propose that DB querying in language sciences be designed linguistically and directly determined by linguistic data. Linguists from various backgrounds could then use a consensual query tool. An implemented data-directed DB querying system, which was developed for research on French interrogative structures, is presented in detail.Rachel Panckhurst teaches and researches in computational linguistics at the Université Paul Valéry-Montpellier III, France. Her research interests include natural language processing and information retrieval systems. She is currently devising a computer-assisted classification system for verbal subcategorization in French. She received her PhD (doctorat nouveau régime) in computational linguistics in December 1990 (Université Clermont II). Recent works include: Scatlex: une aide informatisée pour la construction d'entrées lexicales verbales, ICO Québec: Hiver 1993, pp. 61–67; Comment allier les besoins du linguiste et l'utilisation intelligente de bases de données? CIL '92 Proceedings, Québec, September 1993, pp 301–304.This article is a revised and extended English version of a paper in French, Comment allier les besoins du linguiste et l'utilisation intelligente de bases de données, Proceedings of the XVth International Congress of Linguists, Québec, August 1992, pp. 301–304, and was written during a post-doctoral fellowship (AUPELF-UREF) at the Centre d'ATO-CI, (Recherche et développement en linguistique computationnelle (RDLC)), Université du Québec à Montréal. The paper is adapted from part of Chapter 4 of a doctoral dissertation, Panckhurst, 1990. Many thanks are due to Jean-Marie Marandin who first encouraged me to write the paper and who read and gave constructive criticism on a previous version. I would also like to thank Sophie David and Claude Ricciardi Rigault (French version) and Fay Panckhurst (English version) for their helpful remarks. Finally, an anonymous reviewer provided constructive criticism, for which I am grateful. Any remaining errors are of course my own.     

Disinformation: The Use of False Information

The distinction between misinformation and disinformation becomes especially important in political, editorial, and advertising contexts, where sources may make deliberate efforts to mislead, deceive, or confuse an audience in order to promote their personal, religious, or ideological objectives. The difference consists in having an agenda. It thus bears comparison with lying, because lies are assertions that are false, that are known to be false, and that are asserted with the intention to mislead, deceive, or confuse. One context in which disinformation abounds is the study of the death of JFK, which I know from more than a decade of personal research experience. Here I reflect on that experience and advance a preliminary theory of disinformation that is intended to stimulate thinking on this increasingly important subject. Five kinds of disinformation are distinguished and exemplified by real life cases I have encountered. It follows that the story you are about to read is true.     

Automated Proof Construction in Type Theory Using Resolution

We provide techniques to integrate resolution logic with equality in type theory. The results may be rendered as follows. A clausification procedure in type theory, equipped with a correctness proof, all encoded using higher-order primitive recursion. A novel representation of clauses in minimal logic such that the -representation of resolution steps is linear in the size of the premisses. A translation of resolution proofs into lambda terms, yielding a verification procedure for those proofs. Availability of the power of resolution theorem provers in interactive proof construction systems based on type theory.