An Approximate Method of Ellipsoids

A version of the method of ellipsoids is proposed in the paper that has the same asymptotic rate in volume convergence as the well-known Yudin-Nemirovskii-Shor method of ellipsoids. This method can be applied to one-dimensional problems, where it guarantees a decrease in the ratio of volumes equal to 2- 2 0.5858 on each iteration.     

Multilingual Dialogue-Based MT for monolingual authors: the LIDIA project and a first mockup

Dialogue-Based Machine Translation (DBMT) is a new paradigm for translation situations where other approaches such as the Linguistic-Based (LBMT) and the Knowledge-Based (KBMT) approaches, are not adequate. In DBMT, although the linguistic knowledge sources are still crucial, and extralinguistic knowledge might be used if available, emphasis is on indirect pre-editing through a negotiation and a clarification dialogue with the author in order to get high quality translations without revision. Authors are distinguished from spontaneous writers or speakers by the fact that they want to produce a clean final message and may be willing to enter into such dialogues. After having described the main situational, linguistic and ergonomic issues in DBMT for monolingual authors, we describe ongoing work on the LIDIA project. The typical translational situation considered is the production of multilingual technical documentation in the form of HyperCard stacks. Notable points in the linguistic design include multilevel transfer with interlingual acceptions, properties and relations, the guided language approach (typed textual fragments and lexical peferences), and a TEI-inspired representation of texts and structures. The current mockup, LIDIA-1.0, demonstrates the majority of these ideas on a HyperCard stack, to be translated from French into German, Russian and English. Some of its aspects are discussed in detail, in particular the user interface, the object-oriented implementation, and the production of disambiguation dialogues.     

Time lower bounds for parallel sorting on a mesh-connected processor array

Summary We prove that (1+6/2)n 2.22n is a time lower bound independent of indexing schemes for sorting n² items on an n × n mesh-connected processor array. We distinguish between indexing schemes by showing that there exists an indexing scheme which is provably worse than the snake-like row-major indexing for sorting. We also derive lower bounds for various indexing schemes. All these results are obtained by using the chain argument which we provide in this paper.A preliminary version of this paper was presented on the 3rd International Workshop on Parallel Computation and VLSI Theory, Corfu Island, Greece (June–July, 1988). Lect. Notes Comput. Sci. 319, 434–443 (1988)Research supported in part by the University of Kentucky research initiation award     

Decision procedures for elementary sublanguages of set theory: XIII. Model graphs,reflection and decidability

Positive solutions to the decision problem for a class of quantified formulae of the first order set theoretic language based on , , =, involving particular occurrences of restricted universal quantifiers and for the unquantified formulae of , , =, {...}, , where {...} is the tuple operator and is a general choice operator, are obtained. To that end a method is developed which also provides strong reflection principles over the hereditarily finite sets. As far as finite satisfiability is concerned such results apply also to the unquantified extention of , , =, {...}, , obtained by adding the operators of binary union, intersection and difference and the relation of inclusion, provided no nested term involving is allowed.     

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

Reflections on participatory design

The human-centred debate in Britain focuses on the idea of human-machine symbiosis, and the Dialogue debate in Scandinavia focuses on the deep understanding of human communication, through a process of inner reflection. Both of these debates provide a framework for the participatory design of AI systems.The emergence of social Europe creates the desirability for a sharing of social and cultural knowledge and resources among the citizens of Europe. This raises the possibility of exploiting the potential of new technology for the distribution and transfer of knowledge and skill among the citizens of Europe whilst retaining the diversity of their cultures and languages. These issues of transfer have been the focus of many AI researchers who have been concerned with the design of AI systems for the education, training and welfare of disadvantaged citizens. It is suggested that central to such a transfer is the design of participatory learning systems which focus on the mediation and distribution of knowledge in diverse socio-cultural contexts.In this paper, the SEAKE Centre's projects, especially Brighton Parosi, and Adult Literacy are discussed to provide an insight into the concepts and practice of designing such participatory systems. The philosophy of these projects was rooted in the sharing of social and cultural experiences, through participatory learning. The development of the projects involved a process of exchange of language and culture in both formal and informal learning environments. For the Parosi Project social interaction was the central core for the exchange of cultural experiences and the language acquisition process. The Adult Literacy project built on the exchange process, and used the idea of the mediation of knowledge for the design of a knowledge based system. The design process developed by the above two projects could be described as a participatory design approach which builds upon and extends the human-machine symbiosis and dialogue approaches.     

On-line Learning and the Metrical Task System Problem

The problem of combining expert advice, studied extensively in the Computational Learning Theory literature, and the Metrical Task System (MTS) problem, studied extensively in the area of On-line Algorithms, contain a number of interesting similarities. In this paper we explore the relationship between these problems and show how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include: An analysis of how two recent algorithms for the MTS problem can be applied to the problem of tracking the best expert in the decision-theoretic setting, providing good bounds and an approach of a much different flavor from the well-known multiplicative-update algorithms. An analysis showing how the standard randomized Weighted Majority (or Hedge) algorithm can be used for the problem of combining on-line algorithms on-line, giving much stronger guarantees than the results of Azar, Y., Broder, A., & Manasse, M. (1993). Proc ACM-SIAM Symposium on Discrete Algorithms (pp. 432–440) when the algorithms being combined occupy a state space of bounded diameter. A generalization of the above, showing how (a simplified version of) Herbster and Warmuth's weight-sharing algorithm can be applied to give a finely competitive bound for the uniform-space Metrical Task System problem. We also give a new, simpler algorithm for tracking experts, which unfortunately does not carry over to the MTS problem.Finally, we present an experimental comparison of how these algorithms perform on a process migration problem, a problem that combines aspects of both the experts-tracking and MTS formalisms.     

Directional derivatives of the maximum function

Directional differentiability of the function (x) = sup{f(x, u), u U} is proved for a class of smooth functions f. The result is applied to study the directional differentiability of the function (x) = sup{f(x, y), y F(x)}, where F is a multivalued mapping.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 171–173, March–April, 1992.     

Optimization Criteria and Geometric Algorithms for Motion and Structure Estimation

Prevailing efforts to study the standard formulation of motion and structure recovery have recently been focused on issues of sensitivity and robustness of existing techniques. While many cogent observations have been made and verified experimentally, many statements do not hold in general settings and make a comparison of existing techniques difficult. With an ultimate goal of clarifying these issues, we study the main aspects of motion and structure recovery: the choice of objective function, optimization techniques and sensitivity and robustness issues in the presence of noise.We clearly reveal the relationship among different objective functions, such as (normalized) epipolar constraints, reprojection error or triangulation, all of which can be unified in a new optimal triangulation procedure. Regardless of various choices of the objective function, the optimization problems all inherit the same unknown parameter space, the so-called essential manifold. Based on recent developments of optimization techniques on Riemannian manifolds, in particular on Stiefel or Grassmann manifolds, we propose a Riemannian Newton algorithm to solve the motion and structure recovery problem, making use of the natural differential geometric structure of the essential manifold.We provide a clear account of sensitivity and robustness of the proposed linear and nonlinear optimization techniques and study the analytical and practical equivalence of different objective functions. The geometric characterization of critical points and the simulation results clarify the difference between the effect of bas-relief ambiguity, rotation and translation confounding and other types of local minima. This leads to consistent interpretations of simulation results over a large range of signal-to-noise ratio and variety of configurations.     

Discourse Particles and Discourse Functions

Spoken language, especially spoken German, is rich in particles thatdo not contribute to the propositional content of utterances, but playimportant roles in steering the flow of the dialogue and inconveying various attitudes and expectations of the speaker. Languagesdiffer widely in their conventions on particle usage, and thereforethese words pose significant problems for translation. As a solution,we propose an inventory of discourse functions that characterizethe pragmatic impact of particles. These functions are to be assignedto particles in the analysis phase, so that the translation step canuse the abstract information to decide on the best way of renderingthe same effect in the target-language utterance.     

Elderly Japanese computer users: assessing changes in usage,attitude, and skill transfer over a one-year period

Changes and interrelations among computer usage, computer attitude, and skill transfer of elderly Japanese computer users were investigated over a one-year period. Each participant, aged 60 to 76 years, was provided with one touchscreen-based computer specialized for e-mail handling for 12 months. Participants usage of the computer, mouse and/or keyboard, and computer attitudes were investigated. The results showed that the Liking factor of the computer attitude scale was a possible predictor of computer usage. The results suggested the existence of four different types of users adaptation to computers, according to a combination of the Liking and Confidence dimensions of computer attitude.     

On Some Vagaries of Vagueness and Information

The presence of vagueness in scientific theories (in particular, to those related to and connected with the management of information) is briefly analyzed. We consider, firstly, the problem whether vague predicates can be adequately represented by existing formal theories. A negative answer to this question produces, as a by-product, the suggestion that a good semantics for fuzzy sets can be offered by the notion of distance from idealized items. Secondly, some questions connected with the adequacy of theories of information to the multifaceted informal notion of information suggest to afford this problem within an enlarged dynamical setting.     

Translating VHDL into functional symbolic finite-state models

In this paper we present a method to translate VHDL into symbolic finite-state models. Our method can handle those aspects of VHDL which have a finite representation obtaining the semantics defined in the IEEE statndard. We describe an intermediate representation based on finite automata and its translation into a BDD-based reperesentation. Our model interfaces VHDL with a BDD-based functional symbolic model checker.The work of these authors is supported by ESPRIT project 6128 FORMAT.The work of this author is supported by the Volkswagenstiftung project Informatiksysteme.     

Modelling default and likelihood reasoning as probabilistic reasoning

This paper presents a probabilistic analysis of plausible reasoning about defaults and about likelihood. Likely and by default are in fact treated as duals in the same sense as possibility and necessity. To model these four forms probabilistically, a logicQDP and its quantitative counterpartDP are derived that allow qualitative and corresponding quantitative reasoning. Consistency and consequence results for subsets of the logics are given that require at most a quadratic number of satisfiability tests in the underlying prepositional logic. The quantitative logic shows how to track the propagation error inherent in these reasoning forms. The methodology and sound framework of the system highlights their approximate nature, the dualities, and the need for complementary reasoning about relevance.Much of this research was done while at the University of Technology, Sydney, Broadway, NSW, Australia, and some at the Turing Institute, 36 Nth. Hanover Str., Glasgow, Scotland.     

Comparing text editions with the aid of the computer

The aim of this paper is to reveal the limitations of relying on fingerprint formulas or signature positions to identify printed editions, in the manner of the STCN project. The paper proposes that scanned images of texts be used to identify editions.Ben J. P. Salemans is a philologist with special interest in the use of the computer as a scientific tool in literary, philological and cultural-historical research. His Ph.D. project is a study of automated text-genealogical research. He works as a computer consultant at the UCI computer centre of the University of Nijmegen.Dedicated to the memory of Marcel te Wilt ( 1993).     

Local determinacy of abstract local dynamical systems

O. Hájek proved in his book Dynamical Systems in the Plane (Chapter III) that there isat most one abstract local dynamical system which is locally equivalent to, or equivalently an extension of, a given elementary dynamical system, and suggested a question of finding reasonable conditions on the latter for the existence ofat least one such abstract local dynamical system. An elementary dynamical system is said to satisfy the No-Intersection Axiom and is called an abstract germ if(x ₁, t) = (x ₂,t) impliesx ₁ =x ₂. We show that is (uniquely) extendable to an abstract local dynamical system if and only if is an abstract germ, and hence the question is completely answered. After introducing various kinds of isomorphisms of abstract germs and abstract local dynamical systems corresponding to those of continuous germs and continuous local dynamical systems, we obtain some sufficient conditions for extendability of isomorphisms and possibility of restriction of them, and thus establish the local determinacy of abstract local dynamical systems up to isomorphisms in some wider categories.Dedicated to Professor Yusuke HAGIHARA in Commemoration of His Seventy-Seventh Anniversary     

Statistical Properties of a Time-Series-Complexity Measure Applied to Stock Returns

We review a complexity measure () and its statistical properties, then apply it to four stock returns. Theta is a ratio of two correlation integral estimates, one taken before and one after shuffling the series to investigate. For random processes 1 while approaches zero for data with low complexity. Sixteen artificially generated series with different dynamical characteristics – each represented by three sample sizes – were employed to investigate 's statistical properties. Its distribution approaches normality as the sample size is increased. When applied to stock returns, those computed at every price change proved less complex than lower frequency one- and five-minute returns, implying that information is being lost by increasingly less frequent sampling.     

A priori Probability That Two Qubits Are Unentangled

In a previous study (P. B. Slater, Eur. Phys. J. B. 17, 471 (2000)), several remarkably simple exact results were found, in certain specialized m-dimensional scenarios (m 4), for the a priori probability that a pair of qubits is unentangled/separable. The measure used was the volume element of the Bures metric (identically one-fourth the statistical distinguishability [SD] metric). Here, making use of a newly-developed (Euler angle) parameterization of the 4 × 4 density matrices of Tilma, Byrd and Sudarshan, we extend the analysis to the complete 15-dimensional convex set (C) of arbitrarily paired qubits—the total SD volume of which is known to be ⁸ / 1680 = ⁸/2⁴ 3 5 7 5.64794. Using advanced quasi-Monte Carlo procedures (scrambled Halton sequences) for numerical integration in this high-dimensional space, we approximately (5.64851) reproduce that value, while obtaining an estimate of 0.416302 for the SD volume of separable states. We conjecture that this is but an approximation to ⁶/2310 = ⁶ / (2 3 5 7 11) 0.416186. The ratio of the two volumes, 8/11²2 .0736881, would then constitute the exact Bures/SD probability of separability. The SD area of the 14-dimensional boundary of C is 142⁷/12285 = 2 71⁷/3³ 5 7 13 34.911, while we obtain a numerical estimate of 1.75414 for the SD area of the boundary of separable states. PACS: 03.67.-; 03.65.Ud; 02.60.Jh; 02.40.Ky     

Grid-Computing

Grid-Computing, ein Mitte der 90er-Jahre eingeführter Begriff [1,2], bezeichnet eine Architektur für verteilte Systeme, die auf dem World Wide Web aufbaut und die Web-Vision erweitert. Mit dem Grid-Computing werden die Ressourcen einer Gemeinschaft, einer so genannten virtuellen Organisation, integriert. Die Hoffnung ist, dass hierdurch rechen- und/oder datenintensiven Aufgaben, die eine einzelne Organisation nicht lösen kann, handhabbar werden. Ein Grid bezeichnet eine nach dem Grid-Computing-Ansatz aufgebaute Rechner-, Netzwerk- und Software-Infrastruktur zur Teilung von Ressourcen mit dem Ziel, die Aufgaben einer virtuellen Organisation zu erledigen. * Vorschläge an Prof.Dr. Frank Puppe <puppe@informatik.uni-wuerzburg.de> oder Dieter Steinbauer <dieter.steinbauer@schufa.de>Alle Aktuellen Schlagwörter seit 1988 finden Sie unter: www.ai-wuerzburg.de/as     

On two families of forests

An alphabetic cone is a family of forests stable under alphabetic tree transductions, whereas we call REC-closed each family of forests closed under the operations of union, top-catenation,a-product anda-star; the sheaves are families having both the above properties.For a given sheaf of forests , both the families of languages () and yield () (of branches and yields of respectively) constitute full AFL's.Further we show that the familyK-REC of forests supporting recognizable formal power series on trees is a sheaf and so is the family OCF of behaviors of one counter treeautomata.On the contrary, restricted one counter forests (ROCF) constitute an alphabetic cone which fails to be a sheaf; ROCF _N (restricted one counter forests over alphabets with degree N) is alphabetically principal generated by the Lukasiewicz forest of rankN.