End-to-end communications management using TMN “X” interfaces

The ongoing integration of LANs and WANs to support global communications and businesses and the emergence of integrated broadband communication services has created an increased demand for cooperation between customers, network and service providers to achieve end-to-end service management. Such a cooperation between autonomous authorities, each defining their own administrative management domains, requires the application of an open standardized framework to facilitate and regulate interworking. Such a framework is given by the ITU-T recommendations on TMN, where the so-called X interface is of particular importance for inter-domain management. In this paper, we explain the role of the TMN X interface within an inter-domain TMN architecture supporting end-to-end communications management. We identify the important issues that need to be addressed for the definition and realization of TMN X interfaces and report about our practical experiences with the implementation of TMN X interfaces in the PREPARE project.     

Logic Based Abstractions of Real-Time Systems

When verifying concurrent systems described by transition systems, state explosion is one of the most serious problems. If quantitative temporal information (expressed by clock ticks) is considered, state explosion is even more serious. We present a notion of abstraction of transition systems, where the abstraction is driven by the formulae of a quantitative temporal logic, called qu-mu-calculus, defined in the paper. The abstraction is based on a notion of bisimulation equivalence, called , n-equivalence, where is a set of actions and n is a natural number. It is proved that two transition systems are , n-equivalent iff they give the same truth value to all qu-mu-calculus formulae such that the actions occurring in the modal operators are contained in , and with time constraints whose values are less than or equal to n. We present a non-standard (abstract) semantics for a timed process algebra able to produce reduced transition systems for checking formulae. The abstract semantics, parametric with respect to a set of actions and a natural number n, produces a reduced transition system , n-equivalent to the standard one. A transformational method is also defined, by means of which it is possible to syntactically transform a program into a smaller one, still preserving , n-equivalence.     

Data encodings and their costs

Summary This paper is devoted to developing and studying a precise notion of the encoding of a logical data structure in a physical storage structure, that is motivated by considerations of computational efficiency. The development builds upon the notion of an encoding of one graph in another. The cost of such an encoding is then defined so as to reflect the structural compatibility of the two graphs, the (externally specified) costs of implementing the host graph, and the (externally specified) set of intended usage patterns of the guest graph. The stability of the constructed framework is demonstrated in terms of a number of results; the faithfulness of the formalism is argued in terms of a number of examples from the literature; and the tractability of the model is hinted at by several results and by further references to the literature.     

A Generalization of Jumps and Labels

This paper describes a new language feature that is a hybrid of labels and procedures. It is closely related to jumping out of a functional subroutine, and includes conventional labels and jumping as a special, but probably not most useful, case. It is independent of assignment, ie., it can be added to a purely-functional (non-imperative) system (such as LISP without pseudo-functions or program feature). Experiments in purely functional programming suggest that its main use will be in success/failure situations, and failure actions. This innovation is incorporated in the projected experimental system, ISWIM.     

System Embedding. Linear Control with Observation

Linear control in the object-state observer-controller loop was considered. The matrix equations defining the general solution to this problem based on the desirable matrix transfer function were obtained using the technology of system embedding. In contrast to the traditional concept of separation of linear observation and control, the unknown auxiliary matrix appearing in these equations was shown to reflect their integration. An algorithm to design the united state observer-controller system from the desirable closed-loop matrix transfer functions was proposed. The paper was illustrated by examples.     

A Full Bayesian Approach to Curve and Surface Reconstruction

When interpolating incomplete data, one can choose a parametric model, or opt for a more general approach and use a non-parametric model which allows a very large class of interpolants. A popular non-parametric model for interpolating various types of data is based on regularization, which looks for an interpolant that is both close to the data and also smooth in some sense. Formally, this interpolant is obtained by minimizing an error functional which is the weighted sum of a fidelity term and a smoothness term.The classical approach to regularization is: select optimal weights (also called hyperparameters) that should be assigned to these two terms, and minimize the resulting error functional.However, using only the optimal weights does not guarantee that the chosen function will be optimal in some sense, such as the maximum likelihood criterion, or the minimal square error criterion. For that, we have to consider all possible weights.The approach suggested here is to use the full probability distribution on the space of admissible functions, as opposed to the probability induced by using a single combination of weights. The reason is as follows: the weight actually determines the probability space in which we are working. For a given weight , the probability of a function f is proportional to exp(– f² _uu du) (for the case of a function with one variable). For each different , there is a different solution to the restoration problem; denote it by f. Now, if we had known , it would not be necessary to use all the weights; however, all we are given are some noisy measurements of f, and we do not know the correct . Therefore, the mathematically correct solution is to calculate, for every , the probability that f was sampled from a space whose probability is determined by , and average the different f's weighted by these probabilities. The same argument holds for the noise variance, which is also unknown.Three basic problems are addressed is this work: Computing the MAP estimate, that is, the function f maximizing Pr(f/D) when the data D is given. This problem is reduced to a one-dimensional optimization problem. Computing the MSE estimate. This function is defined at each point x as f(x)Pr(f/D) f. This problem is reduced to computing a one-dimensional integral.In the general setting, the MAP estimate is not equal to the MSE estimate. Computing the pointwise uncertainty associated with the MSE solution. This problem is reduced to computing three one-dimensional integrals.     

The Origins of the Translator's Workstation

The first proposals for various component tools of what is now called the translator's workstation or translator's workbench are traced back to the 1970s and early 1980s in various, often independent, proposals at different stages in the development of computers and in their use by translators.     

BPL: A set-based language for distributed system prototyping

Rapid prototyping of software and hardware is recognized as a very important step in timely, cost-effective system development. The complexity inherent in designing distributed computing systems and distributed problem solutions emphasizes the need for effective rapid prototyping tools. ADL/ADS is a testbed user interface tool for experimentation with critical research and design issues pertaining to distributed data processing (DDP). The experimenter expresses a candidate distributed system in terms of experiment objects, along with attributes and relationships. The experiment objects represent hardware, software, and behavior. This paper provides a brief overview of ADL/ADS, and gives especial emphasis to the Behavior Prototyping Language (BPL) within ADL/ADS. BPL is designed for expressing Behavior Modules (B_MODULEs)—the most versatile of the behavior objects. BPL incorporates set-theoretical approaches, and provides syntax designed for effectively describing manipulations of experiment objects, and their attributes and relationships.     

A formal model of atomicity in asynchronous systems

Summary We propose a generalisation of occurrence graphs as a formal model of computational structure. The model is used to define the atomic occurrence of a program, to characterise interference freeness between programs, and to model error recovery in a decentralised system.     

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 .     

Complexity and computability of solutions to linear programming systems

Through key examples and constructs, exact and approximate, complexity, computability, and solution of linear programming systems are reexamined in the light of Khachian's new notion of (approximate) solution. Algorithms, basic theorems, and alternate representations are reviewed. It is shown that the Klee-Minty example hasnever been exponential for (exact) adjacent extreme point algorithms and that the Balinski-Gomory (exact) algorithm continues to be polynomial in cases where (approximate) ellipsoidal centered-cutoff algorithms (Levin, Shor, Khachian, Gacs-Lovasz) are exponential. By model approximation, both the Klee-Minty and the new J. Clausen examples are shown to be trivial (explicitly solvable) interval programming problems. A new notion of computable (approximate) solution is proposed together with ana priori regularization for linear programming systems. New polyhedral constraint contraction algorithms are proposed for approximate solution and the relevance of interval programming for good starts or exact solution is brought forth. It is concluded from all this that the imposed problem ignorance of past complexity research is deleterious to research progress on computability or efficiency of computation.This research was partly supported by Project NR047-071, ONR Contract N00014-80-C-0242, and Project NR047-021, ONR Contract N00014-75-C-0569, with the Center for Cybernetic Studies, The University of Texas at Austin.     

Fuzzy probabilities for web planning

We apply our new approach to modeling uncertain probabilities to queuing theory and the optimal design of web servers. This involves using fuzzy, finite, regular Markov chains to determine the fuzzy steady state probabilities and then computing the fuzzy numbers for system performance. We first ignore revenues and costs in determining an optimal system and then we incorporate these factors for optimal design. Then we add two new phenomena associated with the web in our optimization models: burstiness and long tailed distributions.     

Thiele Rational Interpolation for the Numerical Computation of the Reversible Randles–Sevcik Function in Electrochemistry

This paper uses Thiele rational interpolation to derive a simple method for computing the Randles–Sevcik function ^1/2(x), with relative error at most 1.9 × 10^–5 for – < x < . We develop a piecewise approximation method for the numerical computation of ^1/2(x) on the union (–, –10) [–10, 10] (10, ). This approximation is particularly convenient to employ in electrochemical applications where four significant digits of accuracy are usually sufficient. Although this paper is primarily concerned with the approximation of the Randles–Sevcik function, some examples are included that illustrate how Thiele rational interpolation can be employed to generate useful approximations to other functions of interest in scientific work.     

Personalized and Adaptive Services on Board a Car: An Application for Tourist Information

Personalization and adaptation techniques are an interesting opportunity to design new services on-board vehicles. In this context, in fact, the need of an individual user to receive the right service at the right time and in the right way is more critical than in other cases, where personalization and adaptation already showed interesting advantages. At the same time, this context of application can provide new interesting insights for user modeling and adaptation. In the paper we present an architecture for providing personalized services on-board vehicles and we discuss an application to the case of tourist information. We focus on the choices we made to design an on-board system which was as less intrusive and distracting as possible and that could adapt its recommendations, the way it presents them and its own behavior to the user's preferences/interests and to the context of interaction (especially the driving conditions).     

An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

We give an O(^k · n²) fixed parameter tractable algorithm for the 1-Sided Crossing Minimization. The constant in the running time is the golden ratio = (1+5)/2 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.     

The Objective Conception of Context and Its Logic

In this paper, an objective conception of contexts based loosely upon situation theory is developed and formalized. Unlike subjective conceptions, which take contexts to be something like sets of beliefs, contexts on the objective conception are taken to be complex, structured pieces of the world that (in general) contain individuals, other contexts, and propositions about them. An extended first-order language for this account is developed. The language contains complex terms for propositions, and the standard predicate ist that expresses the relation that holds between a context and a proposition just in case the latter is true in the former. The logic for the objective conception features a global classical predicate calculus, a local logic for reasoning within contexts, and axioms for propositions. The specter of paradox is banished from the logic by allowing ist to be nonbivalent in problematic cases: it is not in general the case, for any context c and proposition p, that either ist(c,p) or ist(c, ¬ p). An important representational capability of the logic is illustrated by proving an appropriately modified version of an illustrative theorem from McCarthy's classic Blocks World example.     

Uniformization based sensitivity estimation for a class of discrete-event systems

Infinitestimal Perturbation Analysis (IPA) estimators are based on particular couplings of parameteric families of discrete event systems where small changes in the parameter value, typically, cause small changes in the timing of events and, for finite horizons, the sequence of states visisted remains the same. We consider another coupling approach based on the uniformization procedure and a simple generalization of it. In our case any small change in the parameter value causes a change in the state of the system; our parameterization of trajectories keeps them highly synchronized, hence the effect of such changes can be estimated, sometimes efficiently. In this framework, we define three tupes of performance sensitivity estimators for a broad class of performance measures and with respect to a range of parameter values. Performance measures on finite deterministic horizons are considered and it is shown that they are unbiased under mild conditions. We show that for some systems the derivative estimators can be calculated from a nominal sample path of the system.     

On the number of Eulerian orientations of a graph

An Eulerian orientation of an undirected Eulerian graph is an orientation of the edges of the graph such that for every vertex the in-degree is equal to the out-degree. Eulerian orientations are natural flow-like structures, and Welsh has pointed out that computing their number corresponds to evaluating the Tutte polynomial at the point (0, –2) [JVW], [Wl], and is further equivalent to evaluating ice-type partition functions in statistical physics [W2]. In this paper we resolve the complexity of counting the number of Eulerian orientations of an arbitrary Eulerian graph.We give an efficient randomized approximation algorithm for counting Eulerian orientations of any Eulerian graph. Our algorithm is based on a reduction to counting perfect matchings for a class of graphs for which the methods of Broder [B], Jerrum and Sinclair [JS1], and others [DL] [DS] apply. A crucial step of the reduction is the Monotonicity Lemma (Lemma 3.1) which is of independent combinatorial interest. Roughly speaking, the Monotonicity Lemma establishes the intuitive fact that increasing the number of constraints applied on a flow problem cannot increase the number of solutions. The proof of the lemma involves a new decomposition technique which decouples problematically overlapping structures (a recurrent obstacle in handling large combinatorial populations) and allows detailed enumeration arguments. As a by-product, we exhibit a class of graphs for which perfect and near-perfect matchings are polynomially related, and hence the permanent can be approximated, for reasons other than short augmenting paths (previously the only known approach).We also give the complementary hardness result, namely, that counting exactly Eulerian orientations is #P-complete. Finally, we provide some connections with counting Euler tours.     

Supporting the sense of presence in control environments

This paper proposes a notion of presence which overcomes its strict interpretation in terms of physical projection and perception, and interprets the sense of being there as the understanding of the meaning of what is going on there. The domain of control environments is considered to illustrate this point and to propose technological solutions combining principles and techniques taken from Artificial Intelligence and Computer Supported Cooperative Work to enhance the interpretation and cooperation capabilities of the involved actors.     

PDAs and shared public displays: Making personal information public, and public information personal

We are investigating how people move from individual to group work through the use of both personal digital assistants (PDAs) and a shared public display. Our scenario of this work covers the following activities. First, mobile individuals can create personal notes on their PDAs. Second, when individuals meet in real time, they can selectively publicise notes by moving them to a shared public display. Third, the group can manipulate personal and public items in real time through both PDAs and the shared public display, where the notes contained on both PDAs and public display are automatically synchronised. Finally, people leave a meeting with a common record of their activity. We describe our SharedNotes system that illustrates how people move through this scenario. We also highlight a variety of problematic design issues that result from having different devices and from having the system enforce a rigid distinction between personal and public information.