Constructing sets of functions which have a givenF-cardinality

The termF-cardinality of (=F-card()) is introduced whereF: ^{n n} is a partial function and is a set of partial functionsf: ^{n n} . TheF-cardinality yields a lower bound for the worst-case complexity of computingF if only functionsf can be evaluated by the underlying abstract automaton without conditional jumps. This complexity bound isindependent from the oracles available for the abstract machine. Thus it is shown that any automaton which can only apply the four basic arithmetic operations needs (n logn) worst-case time to sortn numbers; this result is even true if conditional jumps witharbitrary conditions are possible. The main result of this paper is the following: Given a total functionF: ^{n n} and a natural numberk, it is almost always possible to construct a set such that itsF-cardinality has the valuek; in addition, can be required to be closed under composition of functionsf,g . Moreover, ifF is continuous, then consists of continuous functions.     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.     

Design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems

This paper describes a unified variational theory for design sensitivity analysis of nonlinear dynamic response of structural and mechanical systems for shape, nonshape, material and mechanical properties selection, as well as control problems. The concept of an adjoint system, the principle of virtual work and a Lagrangian-Eulerian formulation to describe the deformations and the design variations are used to develop a unified view point. A general formula for design sensitivity analysis is derived and interpreted for usual performance functionals. Analytical examples are utilized to demonstrate the use of the theory and give insights for application to more complex problems that must be treated numerically.Derivatives The comma notation for partial derivatives is used, i.e. G,_u = G/u. An upper dot represents material time derivative, i.e. ü = ²u/t². A prime implies derivative with respect to the time measured in the reference time-domain, i.e. u = du/d.     

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.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.     

A predicate transformer for the progress property ‘to-always’

The temporal property to-always has been proposed for specifying progress properties of concurrent programs. Although the to-always properties are a subset of the leads-to properties for a given program, to-always has more convenient proof rules and in some cases more accurately describes the desired system behavior. In this paper, we give a predicate transformerwta, derive some of its properties, and use it to define to-always. Proof rules for to-always are derived from the properties ofwta. We conclude by briefly describing two application areas, nondeterministic data flow networks and self-stabilizing systems where to-always properties are useful.     

On parsing two-level grammars

Summary Making use of the fact that two-level grammars (TLGs) may be thought of as finite specification of context-free grammars (CFGs) with infinite sets of productions, known techniques for parsing CFGs are applied to TLGs by first specifying a canonical CFG G — called skeleton grammar — obtained from the cross-reference of the TLG G. Under very natural restrictions it can be shown that for these grammar pairs (G, G) there exists a 1 — 1 correspondence between leftmost derivations in G and leftmost derivations in G. With these results a straightforward parsing algorithm for restricted TLGs is given.     

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     

A New Implementation of Automath

This paper presents aut, a modern Automath checker. It is a straightforward re-implementation of the Zandleven Automath checker from the seventies. It was implemented about five years ago, in the programming language C. It accepts both the AUT-68 and AUT-QE dialects of Automath. This program was written to restore a damaged version of Jutting's translation of Landau's Grundlagen. Some notable features: It is fast. On a 1 GHz machine it will check the full Jutting formalization (736 K of nonwhitespace Automath source) in 0.6 seconds. Its implementation of -terms does not use named variables or de Bruijn indices (the two common approaches) but instead uses a graph representation. In this representation variables are represented by pointers to a binder. The program can compile an Automath text into one big Automath single line-style -term. It outputs such a term using de Bruijn indices. (These -terms cannot be checked by modern systems like Coq or Agda, because the -typed -calculi of de Bruijn are different from the -typed -calculi of modern type theory.)The source of aut is freely available on the Web at the address .     

Human intelligence and Turing Test

The Turing Test (TT) is criticised for various reasons, one being that it is limited to testing only human-like intelligence. We can read, for example, that TT is testing humanity, not intelligence, (Fostel, 1993), that TT is a test for human intelligence, not intelligence in general, (French, 1990), or that a perspective assumed by TT is parochial, arrogant and, generally, massively anthropocentric (Hayes and Ford, 1996). This limitation presumably causes a basic inadequacy of TT, namely that it misses a wide range of intelligence by focusing on one possibility only, namely on human intelligence. The spirit of TT enforces making explanations of possible machine intelligence in terms of what is known about intelligence in humans, thus possible specificity of the computer intelligence is ruled out from the oælset.This approach causes ire in some interpreters of the test and leads them to desire to create a theory of intelligence in general, thereby overcoming the limitations imposed by merely human intelligence. At times it is an emotion-laden discussion that does not hesitate to impute chauvinism in those limiting themselves to human-type intelligence.¹ This discussion is, by the way, not unlike the rhetoric used by some defenders of animal rights, who insist that an expression of superiority of men over animals is a token of speciesism, and speciesism is just a moral mistake of the same sort as racism and sexism.     

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.     

Relationships between pushdown automata with counters and complexity classes

In this paper a machine model is defined whose access to the storage cells is controlled by means of address registers. It is shown that every set acceptable by such a machine within time boundcn ^p,p , is accepted by a deterministic 2p-head two-way pushdown automaton which has additional counters of length log₂ n. On the other hand every set acceptable by a deterministicp-head two-way pushdown automaton can be accepted by this machine model within time boundcn ^plog₂ n. A result similar to one of the main theorems (theorem 4) of this paper has been proved also by S. A. Cook. Both proofs are based on the same idea but have been found independently.     

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).     

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.     

On computing Boolean connectives of characteristic functions

This paper is a study of the existence of polynomial time Boolean connective functions for languages. A languageL has an AND function if there is a polynomial timef such thatf(x,y) L x L andy L. L has an OR function if there is a polynomial timeg such thatg(x,y) xL oryL. While all NP complete sets have these functions, Graph Isomorphism, which is probably not complete, is also shown to have both AND and OR functions. The results in this paper characterize the complete sets for the classes D^p and p^SAT[O(logn)] in terms of AND and OR and relate these functions to the structure of the Boolean hierarchy and the query hierarchies. Also, this paper shows that the complete sets for the levels of the Boolean hierarchy above the second level cannot have AND or OR unless the polynomial hierarchy collapses. Finally, most of the structural properties of the Boolean hierarchy and query hierarchies are shown to depend only on the existence of AND and OR functions for the NP complete sets.The first author was supported in part by NSF Research Grants DCR-8520597 and CCR-88-23053, and by an IBM Graduate Fellowship.     

The Implications of an Externalist Theory of Rule-Following Behaviour for Robot Cognition

Given (1) Wittgensteins externalist analysis of the distinction between following a rule and behaving in accordance with a rule, (2) prima facie connections between rule-following and psychological capacities, and (3) pragmatic issues about training, it follows that most, even all, future artificially intelligent computers and robots will not use language, possess concepts, or reason. This argument suggests that AIs traditional aim of building machines with minds, exemplified in current work on cognitive robotics, is in need of substantial revision.     

Inferring Finite Automata with Stochastic Output Functions and an Application to Map Learning

It is often useful for a robot to construct a spatial representation of its environment from experiments and observations, in other words, to learn a map of its environment by exploration. In addition, robots, like people, make occasional errors in perceiving the spatial features of their environments. We formulate map learning as the problem of inferring from noisy observations the structure of a reduced deterministic finite automaton. We assume that the automaton to be learned has a distinguishing sequence. Observation noise is modeled by treating the observed output at each state as a random variable, where each visit to the state is an independent trial and the correct output is observed with probability exceeding 1/2. We assume no errors in the state transition function.Using this framework, we provide an exploration algorithm to learn the correct structure of such an automaton with probability 1 – , given as inputs , an upper bound m on the number of states, a distinguishing sequence s, and a lower bound > 1/2 on the probability of observing the correct output at any state. The running time and the number of basic actions executed by the learning algorithm are bounded by a polynomial in ^–l, m, |s|, and (1/2-)^–1.We discuss the assumption that a distinguishing sequence is given, and present a method of using a weaker assumption. We also present and discuss simulation results for the algorithm learning several automata derived from office environments.     

The plane with parallel coordinates

By means ofParallel Coordinates planar graphs of multivariate relations are obtained. Certain properties of the relationship correspond tothe geometrical properties of its graph. On the plane a point line duality with several interesting properties is induced. A new duality betweenbounded and unbounded convex sets and hstars (a generalization of hyperbolas) and between Convex Unions and Intersections is found. This motivates some efficient Convexity algorithms and other results inComputational Geometry. There is also a suprising cusp inflection point duality. The narrative ends with a preview of the corresponding results inR ^N .     

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.     

Separating complexity classes related to bounded alternating ω-branching programs

We develop a theory of communication within branching programs that provides exponential lower bounds on the size of branching programs that are bounded alternating. Our theory is based on the algebraic concept of -branching programs, : , a semiring homomorphism, that generalizes ordinary branching programs, -branching programs [M2] andMOD _p-branching programs [DKMW].Due to certain exponential lower and polynomial upper bounds on the size of bounded alternating -branching programs we are able to separate the corresponding complexity classesN _ba ,co-N _{ba ba} , andMOD _p - _ba ,p prime, from each other, and from that classes corresponding to oblivious linear length-bounded branching programs investigated in the past.