Splitting a configuration in a simplex

This paper presents a new method of partition, named-splitting, of a point set ind-dimensional space. Given a pointG in ad-dimensional simplexT, T(G;i) is the subsimplex spanned by G and the ith facet ofT. LetS be a set ofn points inT, and let be a sequence of nonnegative integers ₁, ..., n_d+1 satisfying _i=1 ^d+1 ₁=n The-splitter of (T, S) is a pointG inT such thatT(G;i) contains at least _i points ofS in its closure for everyi=1, 2, ...,d + 1. The associated dissection is the re-splitting.The existence of a-splitting is shown for any (T, S) and, and two efficient algorithms for finding such a splitting are given. One runs inO(d²n logn + d³n) time, and the other runs inO(n) time if the dimensiond can be considered as a constant. Applications of re-splitting to mesh generation, polygonal-tour generation, and a combinatorial assignment problem are given.     

Fitting a Step Function to a Point Set

We consider the problem of fitting a step function to a set of points. More precisely, given an integer k and a set P of n points in the plane, our goal is to find a step function f with k steps that minimizes the maximum vertical distance between f and all the points in P. We first give an optimal Θ(nlog n) algorithm for the general case. In the special case where the points in P are given in sorted order according to their x-coordinates, we give an optimal Θ(n) time algorithm. Then, we show how to solve the weighted version of this problem in time O(nlog ⁴ n). Finally, we give an O(nh ²log n) algorithm for the case where h outliers are allowed. The running time of all our algorithms is independent of k.     

Imagining a non-biological machine as a legal person

As non-biological machines come to be designed in ways which exhibit characteristics comparable to human mental states, the manner in which the law treats these entities will become increasingly important both to designers and to society at large. The direct question will become whether, given certain attributes, a non-biological machine could ever be viewed as a “legal person.” In order to begin to understand the ramifications of this question, this paper starts by exploring the distinction between the related concepts of “human,” “person,” and “property.” Once it is understood that person in the legal sense can apply to a non-biological entity such as a corporation, the inquiry then goes on to examine the folk psychology view of intentionality and the concept of autonomy. The conclusion reached is that these two attributes can support the view that a non-biological machine, at least in theory, can be viewed as a legal person.

---

Location of a boundary for a diffusion equation of a single server queue

A diffusion-equation model of the M/E_s/1 queue is derived from forward Kolmogorov equations for stages. The derivation results in a new boundary condition. Namely, it is established that an abscissa of a reflecting barrier equals minus squared variance coefficient of service time. That result is then obtained for E_r/M/1 and E_r/E_s/1 queues. Its validity is also illustrated for other systems.     

Searching a Polygonal Region by a Boundary Searcher

This paper considers the problem of planning the motion of a searcher in a polygonal region to eventually"see"an intruder that is unpredictable and capable of moving arbitrarily fast.A searcher is called the boundary searcher if he continuously moves on the polygon boundary and can see only along the rays of the flashlights he holds at a time. We present necessary and sufficient conditions for an n-sided polygon to be searchable by a boundary searcher.Based on our characterization,the equivalence of the ...     

Linking a CYBER76 to a 3600

In mid-1973, the Division of Computing Research, CSIKO, took delivery of a Control Data CVBER76 computer, which acts as the primary processing power of the CSIRO computer network (CSIRONET), replacing the Control Data 3600. The 3600, running under the DAD operating system, has been retained as a ‘front-end’ to the CYBER76 and continues to support the following functions:

• 1 An interactive system allowing both editing and CYBER76 job submission
• 2 Input of job files centrally from 3600 input devices, remotely from CSIRONET devices, or from interactive console users, and output of results similarly
• 3 A permanent file (document) system, with tape archiving

This paper describes the linking of the CYBER76 to the 3600. Software for a CYBER76 PPU has been written and some changes to the 3600 and CYBER76 operating systems have been required.     

Finding a maximum matching in a permutation graph

We present anO(n log logn) time algorithm for finding a maximum matching in a permutation graph withn vertices, assuming that the input graph is represented by a permutation.     

On a Homomorphism of a Component Petri Net

A reduced Petri net model of a parallel distributed system is considered as a component Petri net (a CN) with a view to determining the adequacy between two models, namely, a detailed Petri model N and a component Petri model (CN model) of this distributed system. The concepts of a component relation χ and a component relation domain are introduced. A surjective homomorphism between the N and CN models and an isomorphism between the N / χ net, i.e., the factor model of N with respect to the relation χ, and CN are established.     

Sharing a quantum secret without a trusted party

In a conventional quantum (k, n) threshold scheme, a trusted party shares a secret quantum state with n participants such that any k of those participants can cooperate to recover the original secret, while fewer than k participants obtain no information about the secret. In this paper we show how to construct a quantum (k, n) threshold scheme without the assistance of a trusted party, who generates and distributes shares among the participants. Instead, each participant chooses his private state and contributes the same to the determination of the final secret quantum state.     

Locating a tree in a phylogenetic network

Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete.     

Sorting a sequence of strong kings in a tournament

A king in a tournament is a player who beats any other player directly or indirectly. According to the existence of a king in every tournament, Wu and Sheng [Inform. Process. Lett. 79 (2001) 297-299] recently presented an algorithm for finding a sorted sequence of kings in a tournament of size n, i.e., a sequence of players u₁,u₂,…,u_n such that u_i→u_i+1 (u_i beats u_i+1) and u_i is a king in the sub-tournament induced by {u_i,u_i+1,…,u_n} for each i=1,2,…,n−1. With each pair u,v of players in a tournament, let b(u,v) denote the number of third players used for u to beat v indirectly. Then, a king u is called a strong king if the following condition is fulfilled: if v→u then b(u,v)>b(v,u). In the sequel, we will show that the algorithm proposed by Wu and Sheng indeed generates a sorted sequence of strong kings, which is more restricted than the previous one.     

Numerical modeling of interaction of a current with a circular cylinder near a rigid bed

The numerical modeling of 2D turbulent flow around a smooth horizontal circular cylinder near a rigid bed with gap ratio G/D = 0.3 at Reynolds number Re_D = 9500 is investigated. Ansys^® 10.0-FLOTRAN program package is used to solve the governing equations by FEM, and the performance of the standard k ? ε, standard k ? ω, and SST turbulence models are examined. A sensitivity study for the three turbulence models is carried out on three computational meshes with different densities near the cylinder surface. The computational velocity fields and the Strouhal numbers from the present simulations are compared with those obtained from the PIV measurement. It is found that the time-averaged velocity field of the flow in the proximity of the cylinder is closely affected by the mesh resolution near the cylinder surface, and the mesh refinement in radial direction improves the results of present simulations. The shedding of vortices in the cylinder wake is not predicted by k ? ε model on all the three meshes. The results for the time-averaged velocity field show that the numerical modeling using either of k ? ω and SST turbulence models on the finest mesh used on the cylinder surface is reasonably successful.     

On a Parametrization of Purifications of a Qubit

This work provides, constructively, explicit one–one parametrizations of all purifications of a mixed state in dimension 2 and all joint purifications, if any, of two mixed states in the same dimension. The former is parametrized by SO(3, R), while the latter is parametrized by SO(2, R), except when the state being purified is already pure. These parametrizations are derived without any passage to the spectral decompositions of the state(s) being purified. Using this, we show how to calculate certain measures of quantum information. The appendix considers an alternative one–one parametrization of mixed states in C² C², which provides a different explicit construction of joint purifications. PACS: 03.67-a; 03.67-Hk; 03.67-Lx     

Electing a leader in a ring with link failures

Summary We investigate the message complexity of electing a leader in a ring of asynchronous processors. Our work deviates from the previous works on electing a leader in that we consider the effect of link failures. A link is said to fail if some message sent through it never reaches its destination. We distinguish the case where n is known from the case n unknown. Our main result is a O(n · log n) algorithm for electing a leader on a n-processor ring (the case n is known).     

Designing a Controller for a Multi-Train Multi-Track System

The use of formal methods for analyzing and synthesizing a controller for a multi-train multi-track railway system is discussed. The research was motivated by a case study involving the Bay Area Rapid Transit (BART) system. The overall goal is to design a train acceleration control function that enables trains to be safely placed but also increases system throughput. The use of a modeling language for specifying safety properties and a control function is illustrated. The program transformation methodology supported in the HATS system is employed to generate an efficient implementation from a high-level specification of a controller. This implementation can then be used to simulate the controller behavior, thus further enhancing confidence in the design. Properties of optimization transformations can be verified using an rewrite-rule based induction theorem prover Rewrite Rule Laboratory (RRL).     

Adding a temporal dimension to a logic system

We introduce a methodology whereby an arbitrary logic system L can be enriched with temporal features to create a new system T(L). The new system is constructed by combining L with a pure propositional temporal logic T (such as linear temporal logic with Since and Until) in a special way. We refer to this method as adding a temporal dimension to L or just temporalising L. We show that the logic system T(L) preserves several properties of the original temporal logic like soundness, completeness, decidability, conservativeness and separation over linear flows of time. We then focus on the temporalisation of first-order logic, and a comparison is make with other first-order approaches to the handling of time.