An efficient parallel algorithm for computing a large independent set in a planar graph

Let (G) denote the independence number of a graphG, that is the maximum number of pairwise independent vertices inG. We present a parallel algorithm that computes in a planar graphG = (V, E), an independent set such that ¦I¦ (G)/2. The algorithm runs in timeOlog² n) and requires a linear number of processors. This is achieved by denning a new set of reductions that can be executed locally and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.Joseph Naor was supported by Contract ONR N00014-88-K-0166. Most of this work was done while he was a post-doctoral fellow at the Department of Computer Science, University of Southern California, Los Angeles, CA 90089-0782, USA.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Two and three-quarter dimensional meshing facilitators

This paper presents generated enhancements for robust two and three-quarter dimensional meshing, including: (1) automated interval assignment by integer programming for submapped surfaces and volumes, (2) surface submapping, and (3) volume submapping. An introduction to the simplex method, an optimization technique of integer programming, is presented. Simplification of complex geometry is required for the formulation of the integer programming problem. A method of i-j unfolding is defined which explains how irregular geometry can be realigned into a simplified form that is suitable for submap interval assignment solutions. Also presented is the processes by which submapping eliminates the decomposition of surface geometry, through a pseudodecomposition process, producing suitable mapped meshes. The process of submapping involves the creation of interpolated virtual edges, user defined vertex types and i-j-k space traversals. The creation of interpolated virtual edges is the method by which submapping automatically subdivides surface geometry. The interpolated virtual edge is formulated according to an interpolation scheme using the node discretization of curves on the surface. User defined vertex types allow direct user control of surface decomposition and interval assignment by modifying i-j-k space traversals. Volume submapping takes the geometry decomposition to a higher level by using mapped virtual surfaces to eliminate decomposition of complex volumes.     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Eine bedingte Form der Integral-Ungleichung von Gronwall,leichte Verallgemeinerung eines Stabilitätssatzes von Perron und überlauffreie Skalierung von Analogrechenschaltungen

Zusammenfassung Es geht in dieser Arbeit in der Hauptsache darum, ein vorgelegtes Differentialgleichungssystem so zu skalieren, daß in der zugehörigen Analogrechnerschaltung die Spannungen an den Ausgängen der Integratoren die durch die Referenzspannung einerseits und durch das Auflösevermögen andererseits gesetzten Schranken nicht über- bzw. unterschreiten. Es werden Abschätzungssätze hergeleitet, die diese Frage im Apriori-Sinn, also ohne die Lösung des Differentialgleichungssystems zu kennen, zu lösen gestatten. Zur Abschätzung werden zunächst Normen, dannKamke-Normen verwendet. Der im Titel erwähnte Satz vonPerron ergibt sich durch spezielle Normengebung und Verzicht auf Abschätzung nach unten. Erschwert werden die Betrachtungen durch die relative Schwäche der Forderung, daß die rechte Seite des Systemsdx/dt=f(x,t) der Bedingung aus xa folgt f(x,t)v(t)x genüge (...:=Norm,a positiv reell). Dadurch scheint es bei Abschätzungen mitKamke-Normen nicht mehr möglich, von den in der Literatur über Existenzbeweise und Abschätzungssätze üblichen Methoden Gebrauch zu machen. Zur Lösung dieser Frage wird eine bedingte Form des bekannten Satzes vonGronwall (auch Satz vonBellman genannt) entwickelt.

---

A conditional version of the integral inequality of gronwall, a slight generalization of a stability theorem of perron, and overflow-free scaling of analogue computer set-ups

Summary The main subject of this paper is the scaling of a given set of differential equations in such a way that the output voltages of the integrators of the associated analogue computer set-up do not exceed certain upper and lower bounds imposed by the reference voltage and the limited power of resolution of the elements of the analogue computer. The paper gives a priori bounds on the solution of the differential set. Some of these bounds work with norms, others withKamke-norms.Perron's stability theorem mentioned in the title of this paper results by inserting special norms and neglecting lower bounds. A difficulty arises by the relative weakness of the condition xa implies f(x,t)v(t)x on the right hand side of the setdx/dt=f(x,t), where ... is any norm anda is a positive real constant. As a consequence of this, it seems no longer possible to use the usual techniques known from the literature on existence theorems and bounds for the solution of differential equations. To cope with this situation, a conditional version of the well-known theorem ofGronwall (also known by the name of Lemma ofBellman) will be derived.

---

Diese Arbeit ist Teil einer am Institut für Angewandte Mathematik der Technischen Hochschule München unter Anleitung von Herrn o. Prof. Dr. rer. nat. habil.J. Heinhold angefertigten Dissertation.     

Definability of Polyadic Lifts of Generalized Quantifiers

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type < 1 >.We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.     

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     

Formalizing Strong Normalization Proofs of Explicit Substitution Calculi in ALF

The past decade has given rise to a number of explicit substitution calculi. An important question of explicit substitution calculi is that of the termination of the underlying calculus of substitution. Proofs of termination of substitutions fall in two categories: those that are easy because a decreasing measure can be established and those that are difficult because such a decreasing measure is not easy to establish. This paper considers two styles of explicit substitution: and s, for which different termination proof methods apply. The termination of s is guaranteed by a decreasing weight, while a decreasing weight for showing the termination of has not yet been found. These termination methods for and s are formalized in the proof checker ALF. During our process of formally checking the termination of and s we comment on what is needed to make a proof formally checkable.     

How to Pass a Turing Test

I advocate a theory of syntactic semantics as a way of understanding how computers can think (and how the Chinese-Room-Argument objection to the Turing Test can be overcome): (1) Semantics, considered as the study of relations between symbols and meanings, can be turned into syntax – a study of relations among symbols (including meanings) – and hence syntax (i.e., symbol manipulation) can suffice for the semantical enterprise (contra Searle). (2) Semantics, considered as the process of understanding one domain (by modeling it) in terms of another, can be viewed recursively: The base case of semantic understanding –understanding a domain in terms of itself – is syntactic understanding. (3) An internal (or narrow), first-person point of view makes an external (or wide), third-person point of view otiose for purposes of understanding cognition.     

Shallow circuits and concise formulae for multiple addition and multiplication

A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several different representation standards.The construction of some new carry-save adders is described. Using these carry-save adders optimally, as prescribed by the above theory, we get {, , }-circuits of depth 3.48 log₂ n and {, , }-circuits of depth 4.95 log₂ n for the carry-save addition ofn numbers of arbitrary length. As a consequence we get multiplication circuits of the same depth. These circuits put out two numbers whose sum is the result of the multiplication. If a single output number is required then the depth of the multiplication circuits increases respectively to 4.48 log₂ n and 5.95 log₂ n.We also get {, , }-formulae of sizeO (n ^3.13) and {, }-formulae of sizeO (n ^4.57) for all the output bits of a carry-save addition ofn numbers. As a consequence we get formulae of the same size for the majority function and many other symmetric Boolean functions.     

Exact Linear Thermodynamic Evolution Equations from the Robertson Formalism

A linear evolution equation for a thermodynamic variable F, odd under time-reversal, is obtained from the exact equation derived by Robertson from the Liouville equation for the information-theoretic phase-space distribution. One obtains an exact expression for , the relaxation time for F. For very short , is time-independent for t > if C(t) F{exp(-i t)}Fo, the equilibrium time correlation, decays exponentially for t > . is the Liouville operator. So long as C(t) is such that decays rapidly to a steady-state value, the t limit of agrees with the fluctuation-dissipation theorem in applications to fluid transport.     

Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity

Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(₁... _N ) is attained, given the cost f( _i ) of a message ₁... _N . Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function f( _i ) – K(₁... _N ) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.     

Human–Machine Interaction in Intelligent Robotic Systems: A Unifying Consideration with Implementation Examples

In this paper, we propose a two-layer sensor fusion scheme for multiple hypotheses multisensor systems. To reflect reality in decision making, uncertain decision regions are introduced in the hypotheses testing process. The entire decision space is partitioned into distinct regions of correct, uncertain and incorrect regions. The first layer of decision is made by each sensor indepedently based on a set of optimal decision rules. The fusion process is performed by treating the fusion center as an additional virtual sensor to the system. This virtual sensor makes decision based on the decisions reached by the set of sensors in the system. The optimal decision rules are derived by minimizing the Bayes risk function. As a consequence, the performance of the system as well as individual sensors can be quantified by the probabilities of correct, incorrect and uncertain decisions. Numerical examples of three hypotheses, two and four sensor systems are presented to illustrate the proposed scheme.     

Defaults as restrictions on classical Hilbert-style proofs

Since the earliest formalisation of default logic by Reiter many contributions to this appealing approach to nonmonotonic reasoning have been given. The different formalisations are here presented in a general framework that gathers the basic notions, concepts and constructions underlying default logic. Our view is to interpret defaults as special rules that impose a restriction on the juxtaposition of monotonic Hubert-style proofs of a given logicL. We propose to describe default logic as a logic where the juxtaposition of default proofs is subordinate to a restriction condition . Hence a default logic is a pair (L, ) where properties of the logic , like compactness, can be interpreted through the restriction condition . Different default systems are then given a common characterization through a specific condition on the logicL. We also prove cumulativity for any default logic (L, ) by slightly modifying the notion of default proof. We extend, in fact, the language ofL in a way close to that followed by Brewka in the formulation of his cumulative default system. Finally we show the existence of infinitely many intermediary default logics, depending on and called linear logics, which lie between Reiter's and ukaszewicz' versions of default logic.Work carried out in the framework of the agreement between Italian PT Administration and FUBLaforia, Université Paris VI Pierre et Marie Curie, 4 Place Jussieu,Tour 46, 75252 Paris, France     

Unextendible Product Bases and Locally Unconvertible Bound Entangled States

Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a system of three qubits. A complete classification of such UPBs is suggested. We prove that for any pair of UPBs S and T the associated bound entangled states _S and _T cannot be converted to each other by LOCC, unless S and T coincide up to local unitaries. More specifically, there exists a finite precision (S,T) > 0 such that for any LOCC protocol mapping _S into a probabilistic ensemble (p, ), the fidelity between _T and any possible final state satisfies F(_T, ) = 1 - (S,T).PACS: 03.65.Bz; 03.67.-a; 89.70+c.     

Deterministic sequential functions

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions _P ^–1 , where _P consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions _P ^–1 , where is the family of endmarkers and is the family of removals of endmarkers. (The compositions are read from left to right). We also show that _P ^–1 is the family of the subsequential functions.This work was partially supported by the Esprit Basic Research Action Working Group No. 3166 ASMICS, the CNRS and the Academy of Finland     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

Reaping the whirlwind: Reply to Harnad's “other bodies,other minds”

Harnad's proposed robotic upgrade of Turing's Test (TT), from a test of linguistic capacity alone to a Total Turing Test (TTT) of linguisticand sensorimotor capacity, conflicts with his claim that no behavioral test provides even probable warrant for attributions of thought because there is no evidence of consciousness besides private experience. Intuitive, scientific, and philosophical considerations Harnad offers in favor of his proposed upgrade are unconvincing. I agree with Harnad that distinguishing real from as if thought on the basis of (presence or lack of) consciousness (thus rejecting Turing (behavioral) testing as sufficient warrant for mental attribution)has the skeptical consequence Harnad accepts — there is in factno evidence for me that anyone else but me has a mind. I disagree with hisacceptance of it! It would be better to give up the neo-Cartesian faith in private conscious experience underlying Harnad's allegiance to Searle's controversial Chinese Room Experiment than give up all claim to know others think. It would be better to allow that (passing) Turing's Test evidences — evenstrongly evidences — thought.     

Dynamic half-space range reporting and its applications

We consider the half-space range-reporting problem: Given a setS ofn points in ^d, preprocess it into a data structure, so that, given a query half-space , allk points ofS can be reported efficiently. We extend previously known static solutions to dynamic ones, supporting insertions and deletions of points ofS. For a given parameterm,n m n ^d/2 and an arbitrarily small positive constant , we achieveO(m ¹⁺) space and preprocessing time, O((n/m ^d/2 logn+k) query time, and O(m¹⁺n) amortized update time (d 3). We present, among others, the following applications: an O(n¹⁺)-time algorithm for computing convex layers in ³, and an output sensitive algorithm for computing a level in an arrangements of planes in ³, whose time complexity is O((b+n) n, whereb is the size of the level.Work by the first author has been supported by National Science Foundation Grant CCR-91-06514. A preliminary version of this paper appeared in Agarwalet al. [2], which also contains the results of [20] on dynamic bichromatic closest pair and minimum spanning trees.     

The informed neuron: Issues in the use of information theory in the behavioral sciences

The concept of information is virtually ubiquitous in contemporary cognitive science. It is claimed to be processed (in cognitivist theories of perception and comprehension), stored (in cognitivist theories of memory and recognition), and otherwise manipulated and transformed by the human central nervous system. Fred Dretske's extensive philosophical defense of a theory of informational content (semantic information) based upon the Shannon-Weaver formal theory of information is subjected to critical scrutiny. A major difficulty is identified in Dretske's equivocations in the use of the concept of a signal bearing informational content. Gibson's alternative conception of information (construed as analog by Dretske), while avoiding many of the problems located in the conventional use of signal, raises different but equally serious questions. It is proposed that, taken literally, the human CNS does not extract or process information at all; rather, whatever information is construed as locatable in the CNS is information only for an observer-theorist and only for certain purposes.Blood courses through our veins, andinformation through our central nervous system.— A Neuropsychology Textbook.