A toolbox of algorithmic techniques is presented for creating a variety of novel, visually engaging, sculptural forms that express a mathematical aesthetic embodied within a plausibly organic organization. Hyperbolic tessellations in the Poincare plane are transformed in several ways to three-dimensional networks of edges. Then these edge networks are thickened to solid struts with a simple robust "strut algorithm". By the use of different transformations and adjustable parameters in the algorithms, a variety of high-genus forms result. The techniques are robust enough to produce watertight boundary representations to be built with solid freeform fabrication equipment. The final physical sculptures satisfy the "coolness criterion," that passers by will pick them up and say "Wow, that's cool!"

We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlap-linebreak ping, connected planar layout in linear time. The manifold is cut only along its edges. The resulting layout is connected, but it may have a disconnected interior; the triangles are connected at vertices, but not necessarily joined along edges. We extend our algorithm to establish a similar result for simplicial manifolds of arbitrary dimension.

This presentation illustrates examples of my geometric sculpture and o utlines certain design techniques. I apply methods from the field of computational geometry to the creation of forms which are aesthetic objects.

Efficiently managing the history of a time-evolving system is one of the central problems in many database environments, like database systems that incorporate versioning, or object-oriented databases that implicitly or explicitly maintain the history of persistent objects. In this paper we propose algorithms that reconstruct past states of an evolving system for two general cases, i.e., when the system's state is represented by a set or by a hierarchy (a forest of trees). Sets are widely used as a canonical form of representing information in databases or program states. For more complex applications, like schema evolution in object-oriented databases, it becomes necessary to manage the history of data structures that have the form of forests or even graphs. The proposed algorithms use minimal space (proportional to the number of changes occurring in the evolution) and have the advantage of being on-line (in the amortized sense). Any past system state s(t) is reconstructed in time O.>

This paper addresses the problem of identifying a probabilistic FSM from its output. The authors propose a formal description of the FSM and its output, using a regular phrase-structured grammar. This description is associated with a cost measuring its information content. The authors then state the inference problem as a combinatorial optimization problem with an objective function define as the cost of the description of the FSM and its output. A heuristic algorithm is proposed which processes the output "on line" and yields a local minimum of the authors' criterion. At each step (i.e. as new data is observed and processed), the procedure searches locally through the space of non-probabilistic FSMs, i.e., the transitions are initially regarded as being only present or absent. When a non-probabilistic model has been generated, the transition probabilities are determined from their relative frequencies given the behavior indicated by the data. This yields maximum likelihood estimates of the probabilities. The costs of the obtained probabilistic FSMs are then computed, and the K minimum cost FSMs are kept as starting points for the next step search. At each step, the generation of the FSMs is done via a local search through the neighborhoods of the K best FSMs obtained at the previous step. This algorithm is compared with similar algorithms proposed previously, and tested on a range of examples. It is found to work for a wider range of FSMs than the previous methods, and it is much more practical for large problems than previously proposed exhaustive search techniques.>

Some of today's telecommunications networks have the ability to superimpose some form of logical connectivity, or virtual topology, on top of the underlying physical infrastructure. According to the degree of independence between the logical connectivity and the physical topology, the network can dynamically adapt its virtual topology to track changing traffic conditions, and cope with failure of network equipment. This is particularly true for lightwave networks, where a logical connection diagram is achieved by assignment of transmitting and receiving wavelengths to the network stations that tap into, and communicate over, an infrastructure of fiber glass. Use of tunable transmitters and/or receivers allow the logical connectivity to be optimized to prevailing traffic conditions. With rearrangeability having thus emerged as a powerful network attribute, this paper discusses the reconfiguration phase which is the transition between the current logical connection diagram and a target diagram. We consider here an approach where the network reaches some target connectivity graph through a sequence of intermediate connection diagrams, so that two successive diagrams differ by a single branch-exchange operation. This is an attempt at logically reconfiguring the network in a way that is minimally disruptive to the traffic. We propose and compare three polynomial-time algorithms that search for "short" sequences of branch-exchange operations, so as to minimize the overall reconfiguration time. For networks made of up to 40 stations, theoretical and simulation results show that, when a randomly selected diagram is to be changed to another randomly chosen diagram, the average number of branch-exchange operations required grows linearly with the size of the network.>

A formal method used to repair discrete-event systems consisting of communicating processes is described. Two mechanisms of repairing faulty systems are proposed: the first inserts a new "compensator module" into the communication channel between the faulty process and one or more of its neighbors; the second modifies a neighbor of the faulty process in a compensating manner. The two mechanisms fall under a class of methods in which faults are not fixed by replacement of a faulty unit with a fault-free one, but where changes to the non-faulty parts of the system repair the system. A finite-state model is used to describe processes, and the problem is solved for two models of communication: the symmetric (or the handshake) model and, an asymmetric model. The algorithm is described, and examples are presented, including an indication of how the approach may be applied as part of a sophisticated fault management system for communication networks.>

The problem of minimum cost identification of a finite state machine (FSM) using a trace of its event history is addressed. The motivation is fault identification in communication systems, although other applications are possible as well. The event history used for the identification is partially observed, i.e., it is known to be a member of a regular language. Any string which belongs in this regular language is a possible trace of the FSM's event history. Furthermore, the event history is assumed to be corrupted with deletions, additions, and changes of symbols. The FSM to be estimated is related to a known FSM by performing an unknown number of additions and changes of arcs. An identification algorithm based on a fast algorithm that can correct corrupted data strings generated by a known finite state machine is developed. Examples of the method are provided, including one based on the IEEE 802.2 logical link control protocol.>

A new channel model and channel inversion algorithm are presented for correcting symbol sequences that have been corrupted by an unknown combination of known fault mechanisms. The algorithm is similar to the Viterbi algorithm in that it is suitable for situations in which the uncorrupted data string is generated by a known finite-state process, but it is more versatile in that it can correct a much broader class of errors. Of particular importance is the fact that the algorithm corrects common context-sensitive errors, such as symbol changes, transpositions, mergers, splits, insertions, and deletions, which may be assigned different probabilities depending on the context of preceeding and subsequent symbols. As many communication channels can be modeled in this way, this algorithm is a significant extension over the Viterbi algorithm and previous decoding techniques. The notion of channel rules is introduced to provide a framework for the user to specify the channel operation. The algorithm is given in both an off-line form and a recursive form suitable for sequentially presented data streams. In most applications, the recursive form has computational complexity only a constant times that of the Viterbi algorithm.>

The authors propose a minimally disruptive approach that transitions the network through a sequence of branch exchange operations, so that only two links are disrupted at any given time. It is shown that the problem of finding the shortest sequence, so as to minimize the duration of the reconfiguration phase, is equivalent to the problem of finding a decomposition of an auxiliary graph into the largest number of vertex-disjoint cycles. The authors then propose and compare three different polynomial-time greedy algorithms, on the basis of performance and time complexity. Noticing that the length of a sequence increases at most linearly with the size of the network, the authors derived the average rate of growth from simulation results.>

The authors address the problem of identifying the topology of a network from data collected at a designated node (possibly one of the network nodes). The data considered are descriptions of the local neighborhood about each node, which specify the identities of the node and of its neighbors. These data are neither required to be correct nor complete. The authors propose a model that describes and relates the network topology and the data. They define costs associated with this model, and reduce the identification problem to a combinational optimization problem with and an objective function based on these costs. A pseudo-polynomial-time algorithm is derived, which yields a local minimum of the objective function. The local minimum appears to be a reasonable solution, as shown by a range of examples.>

Emerging networks such as multihop radio networks or reconfigurable lightwave networks have a dynamically changing topology as part of their normal operation. In such networks, a precise and timely knowledge of the topology becomes critical for network management and control.If every network node could instantly provide reliable information about itself and its neighbors, it would be relatively easy to assemble this information and derive the overall network topology. However, both the assumptions of correctness and instantaneous delivery of the information do not hold in practice. We address the problem of identifying the topology of a network from possibly incorrect and/or incomplete data collected at a designated node (possibly one of the network nodes). We propose a model that describes and relates the network topology and the data, define costs associated with this model, and reduce the identification problem to a combinatorial optimization problem with an objective function based on these costs. A pseudo polynomial-time algorithm is derived, which yields a local minimum of our objective function. This local minimum appears to be a reasonable solution, as shown by a range of examples

A nonintrusive appliance load monitor that determines the energy consumption of individual appliances turning on and off in an electric load, based on detailed analysis of the current and voltage of the total load, as measured at the interface to the power source is described. The theory and current practice of nonintrusive appliance load monitoring are discussed, including goals, applications, load models, appliance signatures, algorithms, prototypes field-test results, current research directions, and the advantages and disadvantages of this approach relative to intrusive monitoring.>

This work provides a framework for approaching the problem of fault detection in communication processes. Communication processes are modeled as finite state machines (FSMs), and the authors' model consists of two FSMs, one observing part of the behavior of the other. The authors prove that specific classes of faults are detectable, and give a procedure for constructing detectors, but the design of the minimum alphabet detector is NP-complete. An example applicable to the 802.2 protocol is provided.>

It is known that, under any sharing policy, the state describing the number of calls established for each class of traffic in steady state has a product-form distribution when the connection time distribution has a rational Laplace transform. The product-form property further holds for arbitrary holding time distribution under coordinate convex sharing policies. For the complete sharing policy case, an aggregate state describing the number of occupied circuits is shown to maintain the product-form property under asymptotic behavior, when the capacity and traffic intensities go to infinity on a comparable scale. Two theorems relative to the asymptotic behavior of the blocking probabilities which provide some insight into the nature of the blocking phenomenon are given. An approximation which reduces the numerical complexity of evaluating the blocking probabilities for the different classes of service to the computation of a single Erlang formula and the determination of the root of a monotonous polynomial function is proposed.>

The problem of minimum-cost correction of a corrupted set of data that has been generated by a known finite state machine (FSM) is examined. The Viterbi algorithm is modified to correct insertions and deletions as well as errors, still using a trellis diagram that has the same number of states as the FSM that generates the uncorrupted data. Two problems are examined. In the first problem the data is given in the traditional form of a string so the novel aspect is that insertions and deletions are now corrected. In the second problem, a unique string need not be given, but a regular language is given, and any string belonging to the regular language is a possible data string. Again, deletion addition, and changes of symbols are corrected. A direct generalization of the Viterbi decoding algorithm is thus proved to be an efficient technique for solving a much wider class of problems.>

The problem of identifying a general memoryless input/output system from measurements of inputs and the corresponding outputs is considered. The measured output is sought to be represented as the linear combination of known functions of the input with some additive noise. The choice of model order to be used to fit the data is the main issue addressed, and a cost function involving the prediction error and the model order is derived. The cost function under certain approximations is shown to be similar to one obtained by H. Akaike (1969, 1970). If there is a real system generating the data, it is shown that the expected value of this cost function is always minimized at the true value of the order as long as the noise variance satisfies certain conditions. Asymptotic results for some cases are derived. An efficient algorithm is proposed for identifying the model order. Some simulation results using the proposed algorithm are also presented.>

This paper is concerned with performance models and approximations for very large, multi-media networks. Blocking is the traditional performance measure in circuit-switched networks, and will remain as such in multi-rate circuit-switched networks. It is also considered a likely performance measure candidate for resource management and dimensioning in broadband fast packet-switched networks, operated under virtual circuit mode.