A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.     

‘Use’ discourses in system development: Can communication be improved?

This paper aims to provide a basis for renewed talk about use in computing. Four current discourse arenas are described. Different intentions manifest in each arena are linked to failures in translation, different terminologies crossing disciplinary and national boundaries non-reflexively. Analysis of transnational use discourse dynamics shows much miscommunication. Conflicts like that between the Scandinavian System Development School and the usability approach have less current salience. Renewing our talk about use is essential to a participatory politics of information technology and will lead to clearer perception of the implications of letting new systems becoming primary media of social interaction.     

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 “explicit-implicit” distinction

Much of traditional AI exemplifies the explicit representation paradigm, and during the late 1980's a heated debate arose between the classical and connectionist camps as to whether beliefs and rules receive an explicit or implicit representation in human cognition. In a recent paper, Kirsh (1990) questions the coherence of the fundamental distinction underlying this debate. He argues that our basic intuitions concerning explicit and implicit representations are not only confused but inconsistent. Ultimately, Kirsh proposes a new formulation of the distinction, based upon the criterion ofconstant time processing.The present paper examines Kirsh's claims. It is argued that Kirsh fails to demonstrate that our usage of explicit and implicit is seriously confused or inconsistent. Furthermore, it is argued that Kirsh's new formulation of the explicit-implicit distinction is excessively stringent, in that it banishes virtually all sentences of natural language from the realm of explicit representation. By contrast, the present paper proposes definitions for explicit and implicit which preserve most of our strong intuitions concerning straightforward uses of these terms. It is also argued that the distinction delineated here sustains the meaningfulness of the abovementioned debate between classicists and connectionists.     

Context-free text grammars

A text is a triple=(, ₁, ₂) such that is a labeling function, and ₁ and ₂ are linear orders on the domain of ; hence may be seen as a word (, ₁) together with an additional linear order ₂ on the domain of . The order ₂ is used to give to the word (, ₁) itsindividual hierarchical representation (syntactic structure) which may be a tree but it may be also more general than a tree. In this paper we introducecontext-free grammars for texts and investigate their basic properties. Since each text has its own individual structure, the role of such a grammar should be that of a definition of a pattern common to all individual texts. This leads to the notion of ashapely context-free text grammar also investigated in this paper.     

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 Model-Theoretic Approach for Recovering Consistent Data from Inconsistent Knowledge Bases

One of the most significant drawbacks of classical logic is its being useless in the presence of an inconsistency. Nevertheless, the classical calculus is a very convenient framework to work with. In this work we propose means for drawing conclusions from systems that are based on classical logic, although the information might be inconsistent. The idea is to detect those parts of the knowledge base that cause the inconsistency, and isolate the parts that are recoverable. We do this by temporarily switching into Ginsberg/Fitting multivalued framework of bilattices (which is a common framework for logic programming and nonmonotonic reasoning). Our method is conservative in the sense that it considers the contradictory data as useless and regards all the remaining information unaffected. The resulting logic is nonmonotonic, paraconsistent, and a plausibility logic in the sense of Lehmann.     

The singularities and dynamics of a Stewart platform manipulator

The Stewart platform manipulator is a fully parallel kinematic linkage system that has major mechanical differences over typical serial link robots. Its closed kinematic chain and parallel linkage structure give it great rigidity and a high force-to-weight ratio. In this paper, based on the forward and inverse kinematic analysis, the Jacobian matrix and the dynamic equations of the six-degree-of-freedom Stewart platform are derived. The singularities of the Stewart platform are also studied. Four singular positions are proved and some other conditions under which the possible singular positions may occur are given. These results provide us with the necessary information to avoid passing through singular points. The dynamic equations in Cartesian space appear in a very simple form. Especially in some applications if there is no rotation about the fixed X-axis, then the inertia matrix reduces to a constant, diagonal matrix and the Coriolis and centrifugal matrix goes to zero, which makes the Stewart platform become a decoupled, linear system in Cartesian space.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

Representing and using legal knowledge in integrated decision support systems: DataLex WorkStations

There is more to legal knowledge representation than knowledge-bases. It is valuable to look at legal knowledge representation and its implementation across the entire domain of computerisation of law, rather than focussing on sub-domains such as legal expert systems. The DataLex WorkStation software and applications developed using it are used to provide examples. Effective integration of inferencing, hypertext and text retrieval can overcome some of the limitations of these current paradigms of legal computerisation which are apparent when they are used on a stand-alone basis. Effective integration of inferencing systems is facilitated by use of a (quasi) natural language knowledge representation, and the benefits of isomorphism are enhanced. These advantages of integration apply to all forms of inferencing, including document generation and casebased inferencing. Some principles for development of integrated legal decision support systems are proposed.     

A CUCH-machine: The automatic treatment of bound variables

This paper describes a machine for reducing a -formula (explicitly given or implicitly by a system of recursive equations) to principal --normal form, with particular attention to the memory structures needed for the purpose, and with some important features: (1) any kind of collision is permitted; (2) the processing of subformulas which will be thrown away [e.g., ((xy)x) in ((yz)(xy)x)] is avoided; (3) there is no need to introduce any fixed point operator like , etc. The machine structure entails: (1) some store to memorize as side-effects assignment statements with the r.h.s. of a given shape. (2) a number of stacks, one for every in the initial formula, partitioned naturally in classes (chains). These stacks admit as entries only words representing variables and they are peculiar in that the operations admitted on the top arewriting anderasing and the operations admitted on the pseudo-top arereading,read-protecting, andresetting readability (the last two operations are chain operations). This structure is critically motivated. (3) A workstack. (4) A pointerstack. The computation runs through four phases: -generation, -run, -generation, -run. Every generation- (run-) phase is rather recognition- (transformation-) oriented, but we found it more stimulating to emphasize technical similarities rather than methodological differences. Every phase is described and four examples are extensively developed.     

Efficient Solution of Multi-Term Fractional Differential Equations Using P(EC)<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>E Methods

We investigate strategies for the numerical solution of the initial value problem with initial conditions where 0<₁<₂<<. Here y ⁽ _j ) denotes the derivative of order _j >0 (not necessarily _j ) in the sense of Caputo. The methods are based on numerical integration techniques applied to an equivalent nonlinear and weakly singular Volterra integral equation. The classical approach leads to an algorithm with very high arithmetic complexity. Therefore we derive an alternative that leads to lower complexity without sacrificing too much precision. Mathematics Subject Classification: Primary 65L05; Secondary 65L06, 65L20     

On the valuedness of finite transducers

Summary We investigate the valuedness of finite transducers in connection with their inner structure. We show: The valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet is at most the maximum of (1-1/#) · (2 ^k ₁ · k ₃ ) ⁿ · n ⁿ ·# ^{n 3 ·k} ₄ / ³ and 1/#·(2 ^k ₂ ·k ₃ ·(1+k ₄ )) ⁿ ·n ⁿ where k ₁6.25 and k ₂11.89 are constants and k ₃1 and k ₄0 are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, # > 1 and # = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.     

Modular Control and Coordination of Discrete-Event Systems

In the supervisory control of discrete-event systems based on controllable languages, a standard way to handle state explosion in large systems is by modular supervision: either horizontal (decentralized) or vertical (hierarchical). However, unless all the relevant languages are prefix-closed, a well-known potential hazard with modularity is that of conflict. In decentralized control, modular supervisors that are individually nonblocking for the plant may nevertheless produce blocking, or even deadlock, when operating on-line concurrently. Similarly, a high-level hierarchical supervisor that predicts nonblocking at its aggregated level of abstraction may inadvertently admit blocking in a low-level implementation. In two previous papers, the authors showed that nonblocking hierarchical control can be guaranteed provided high-level aggregation is sufficiently fine; the appropriate conditions were formalized in terms of control structures and observers. In this paper we apply the same technique to decentralized control, when specifications are imposed on local models of the global process; in this way we remove the restriction in some earlier work that the plant and specification (marked) languages be prefix-closed. We then solve a more general problem of coordination: namely how to determine a high level coordinator that forestalls conflict in a decentralized architecture when it potentially arises, but is otherwise minimally intrusive on low-level control action. Coordination thus combines both vertical and horizontal modularity. The example of a simple production process is provided as a practical illustration. We conclude with an appraisal of the computational effort involved.     

Almost surely continuous solutions of a nonlinear stochastic integral equation

A nonlinear stochastic integral equation of the Hammerstein type in the formx(t; ) = h(t, x(t; )) + _s k(t, s; )f(s, x(s; ); )d(s) is studied wheret S, a measure space with certain properties, , the supporting set of a probability measure space (,A, P), and the integral is a Bochner integral. A random solution of the equation is defined to be an almost surely continuousm-dimensional vector-valued stochastic process onS which is bounded with probability one for eacht S and which satisfies the equation almost surely. Several theorems are proved which give conditions such that a unique random solution exists. AMS (MOS) subject classifications (1970): Primary; 60H20, 45G99. Secondary: 60G99.     

Single axioms for groups

We study equations of the form (=x) which are single axioms for group theory. Earlier examples of such were found by Neumann and McCune. We prove some lower bounds on the complexity of these , showing that McCune's examples are the shortest possible. We also show that no such can have only two distinct variables. We do produce an with only three distinct variables, refuting a conjecture of Neumann. Automated reasoning techniques are used both positively (searching for and verifying single axioms) and negatively (proving that various candidate (=x) hold in some nongroup and are, hence, not single axioms).     

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.     

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.     

Type inference with non-structural subtyping

We present an O(n³) time type inference algorithm for a type system with a largest type, a smallest type , and the usual ordering between function types. The algorithm infers type annotations of least shape, and it works equally well for recursive types. For the problem of typability, our algorithm is simpler than the one of Kozen, Palsberg, and Schwartzbach for type inferencewithout . This may be surprising, especially because the system with is strictly more powerful.     

Symbols and Computation A Critique of the Computational Theory of Mind

Over the past several decades, the philosophical community has witnessed the emergence of an important new paradigm for understanding the mind.¹ The paradigm is that of machine computation, and its influence has been felt not only in philosophy, but also in all of the empirical disciplines devoted to the study of cognition. Of the several strategies for applying the resources provided by computer and cognitive science to the philosophy of mind, the one that has gained the most attention from philosophers has been the Computational Theory of Mind (CTM). CTM was first articulated by Hilary Putnam (1960, 1961), but finds perhaps its most consistent and enduring advocate in Jerry Fodor (1975, 1980, 1981, 1987, 1990, 1994). It is this theory, and not any broader interpretations of what it would be for the mind to be a computer, that I wish to address in this paper. What I shall argue here is that the notion of symbolic representation employed by CTM is fundamentally unsuited to providing an explanation of the intentionality of mental states (a major goal of CTM), and that this result undercuts a second major goal of CTM, sometimes refered to as the vindication of intentional psychology. This line of argument is related to the discussions of derived intentionality by Searle (1980, 1983, 1984) and Sayre (1986, 1987). But whereas those discussions seem to be concerned with the causal dependence of familiar sorts of symbolic representation upon meaning-bestowing acts, my claim is rather that there is not one but several notions of meaning to be had, and that the notions that are applicable to symbols are conceptually dependent upon the notion that is applicable to mental states in the fashion that Aristotle refered to as paronymy. That is, an analysis of the notions of meaning applicable to symbols reveals that they contain presuppositions about meaningful mental states, much as Aristotle's analysis of the sense of healthy that is applied to foods reveals that it means conducive to having a healthy body, and hence any attempt to explain mental semantics in terms of the semantics of symbols is doomed to circularity and regress. I shall argue, however, that this does not have the consequence that computationalism is bankrupt as a paradigm for cognitive science, as it is possible to reconstruct CTM in a fashion that avoids these difficulties and makes it a viable research framework for psychology, albeit at the cost of losing its claims to explain intentionality and to vindicate intentional psychology. I have argued elsewhere (Horst, 1996) that local special sciences such as psychology do not require vindication in the form of demonstrating their reducibility to more fundamental theories, and hence failure to make good on these philosophical promises need not compromise the broad range of work in empirical cognitive science motivated by the computer paradigm in ways that do not depend on these problematic treatments of symbols.