Outlier Detection under Interval Uncertainty: Algorithmic Solvability and Computational Complexity

In many application areas,it is important to detect outliers. The traditional engineering approach to outlier detection is that we start with some normal values x₁, ...,x_n, compute the sample average E, the sample standard variation , and then mark a value x as an outlier if x is outside the k₀-sigma interval [E – k₀ , E + k₀ ] (for some pre-selected parameter k₀).In real life,we often have only interval ranges [ ] for the normal values x₁, ...,x_n. In this case,we only have intervals of possible values for the bounds and . We can therefore identify outliers as values that are outside all k₀-sigma intervals.Once we identify a value as an outlier for a fixed k₀, it is also desirable to find out to what degree this value is an outlier, i.e., what is the largest value k₀ for which this value is an outlier.In this paper,we analyze the computational complexity of these outlier detection problems, provide efficient algorithms that solve some of these problems (under reasonable conditions), and list related open problems.     

Deterministic sequential functions

The simple rational partial functions accepted by generalized sequential machines are shown to coincide with the compositions _P ^–1 , where _P consists of the prefix codings. The rational functions accepted by generalized sequential machines are proved to coincide with the compositions _P ^–1 , where is the family of endmarkers and is the family of removals of endmarkers. (The compositions are read from left to right). We also show that _P ^–1 is the family of the subsequential functions.This work was partially supported by the Esprit Basic Research Action Working Group No. 3166 ASMICS, the CNRS and the Academy of Finland     

Space-efficient recognition of sparse self-reducible languages

Mahaney and others have shown that sparse self-reducible sets have time-efficient algorithms, and have concluded that it is unlikely that NP has sparse complete sets. Mahaney's work, intuition, and a 1978 conjecture of Hartmanis notwithstanding, nothing has been known about the density of complete sets for feasible classes until now. This paper shows that sparse self-reducible sets have space-efficient algorithms, and in many cases, even have time-space-efficient algorithms. We conclude that NL, NC ^k , AC ^k , LOG(DCFL), LOG(CFL), and P lack complete (or even Turing-hard) sets of low density unless implausible complexity class inclusions hold. In particular, if NL (respectively P, _k , or NP) has a polylog-sparse logspace-hard set, then NLSC (respectively PSC, _k , or PHSC), and if P has subpolynomially sparse logspace-hard sets, then PPSPACE.     

A semidynamic construction of higher-order voronoi diagrams and its randomized analysis

Thek-Delaunay tree extends the Delaunay tree introduced in [1], and [2]. It is a hierarchical data structure that allows the semidynamic construction of the higher-order Voronoi diagrams of a finite set ofn points in any dimension. In this paper we prove that a randomized construction of thek-Delaunay tree, and thus of all the orderk Voronoi diagrams, can be done inO(n logn+k ³n) expected time and O(k²n) expected storage in the plane, which is asymptotically optimal for fixedk. Our algorithm extends tod-dimensional space with expected time complexityO(k ^(d+1)/2+1 n ^(d+1)/2) and space complexityO(k ^(d+1)/2 n ^(d+1)/2). The algorithm is simple and experimental results are given.This work has been supported in part by the ESPRIT Basic Research Action No. 3075 (ALCOM).     

Unextendible Product Bases and Locally Unconvertible Bound Entangled States

Mutual convertibility of bound entangled states under local quantum operations and classical communication (LOCC) is studied. We focus on states associated with unextendible product bases (UPB) in a system of three qubits. A complete classification of such UPBs is suggested. We prove that for any pair of UPBs S and T the associated bound entangled states _S and _T cannot be converted to each other by LOCC, unless S and T coincide up to local unitaries. More specifically, there exists a finite precision (S,T) > 0 such that for any LOCC protocol mapping _S into a probabilistic ensemble (p, ), the fidelity between _T and any possible final state satisfies F(_T, ) = 1 - (S,T).PACS: 03.65.Bz; 03.67.-a; 89.70+c.     

Specification and verification of database dynamics

Summary A framework is proposed for the structured specification and verification of database dynamics. In this framework, the conceptual model of a database is a many sorted first order linear tense theory whose proper axioms specify the update and the triggering behaviour of the database. The use of conceptual modelling approaches for structuring such a theory is analysed. Semantic primitives based on the notions of event and process are adopted for modelling the dynamic aspects. Events are used to model both atomic database operations and communication actions (input/output). Nonatomic operations to be performed on the database (transactions) are modelled by processes in terms of trigger/reaction patterns of behaviour. The correctness of the specification is verified by proving that the desired requirements on the evolution of the database are theorems of the conceptual model. Besides the traditional data integrity constraints, requirements of the form Under condition W, it is guaranteed that the database operation Z will be successfully performed are also considered. Such liveness requirements have been ignored in the database literature, although they are essential to a complete definition of the database dynamics.

Notation

Classical Logic Symbols (Appendix 1) for all (universal quantifier) - exists at least once (existential quantifier) - ¬ no (negation) - implies (implication) - is equivalent to (equivalence) - and (conjunction) - or (disjunction) Tense Logic Symbols (Appendix 1) G always in the future - G ₀ always in the future and now - F sometime in the future - F ₀ sometime in the future or now - H always in the past - H ₀ always in the past and now - P sometime in the past - P ₀ sometime in the past or now - X in the next moment - Y in the previous moment - L always - M sometime Event Specification Symbols (Sects. 3 and 4.1) (x) means immediately after the occurrence of x - (x) means immediately before the occurrence of x - (x) means x is enabled, i.e., x may occur next - { } ({w ₁} x{w ₂}) states that if w ₁ holds before the occurrence of x, then w ₂ will hold after the occurrence of x (change rule) - [ ] ([oa₁, ..., oa_n]x) states that only the object attributes oa₁, ..., oa _n are modifiable by x (scope rule) - {{ }} ({{w}}x) states that if x may occur next, then w holds (enabling rule) Process Specification Symbols (Sects. 5.3 and 5.4) :: for causal rules - for behavioural rules Transition-Pattern Composition Symbols (Sects. 5.2 and 5.3) ; sequential composition - ¦ choice composition - parallel composition - :| guarded alternative composition Location Predicates (Sect. 5.2) (z) means immediately after the occurrence of the last event of z (after) - (z) means immediately before the occurrence of the first event of z (before) - (z) means after the beginning of z and before the end of z (during) - ( z) means before the occurrence of an event of z (at)     

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.     

Quantum Algorithms for Highly Structured Search Problems

We consider the problem of identifying a base k string given an oracle which returns information about the number of correct components in a query, specifically, the Hamming distance between the query and the solution, modulo r = max{2, 6 – k}. Classically this problem requires (nlog _r k) queries. For k {2, 3, 4}, we construct quantum algorithms requiring only a single quantum query. For k > 4, we show that O(k) quantum queries suffice. In both cases the quantum algorithms are optimal. PACS: 03.67.Lx     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

Iterated linear control and iterated one-turn pushdowns

For a class of languages, an-controlled linear grammarK consists of a linear context-free grammarG and a control languageH in, where the terminals ofH are interpreted as the labels of rules ofG. The language generated byK is obtained by derivations ofG such that the corresponding strings of labels of the rules applied are control strings inH. The control of linear grammars can be iterated by starting with and by taking the result of thekth step as class of control languages for the (k + 1)st step. The language class obtained by thekth step is denoted by CTRL_k(). Denote by(S) the language class accepted by nondeterministic one-wayS automata, whereS is a storage type. We prove that for anyS, CTRL_k((S)) = (P _1t ^k (S)), whereP _1t ^k (S) is the storage type the configurations of which consist ofk-iterated one-turn pushdowns ofS-configurations. We establish a strong connection between iterated linear control and iterated one-turn pushdowns. In particular, we characterize CTRL _k ( _CF), where _CF is the class of context-free languages, by iterated one-turn pushdown automata in which the innermost pushdown is unrestricted.The work of the author has been supported by the Netherlands Organization for the advancement of pure research (Z.W.O.).     

A note on classes of complements and the LBA problem

Summary The complements of an AFL form an AFL if and only if is closed under length-preserving universal quantification. The complements of the context-sensitive languages form a principal AFL with a hardest set L ₁. The context-sensitive languages are closed under complementation if and only if L ₁ is context-sensitive.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and DCR74-15091     

Gradually intractable problems and nondeterministic log-space lower bounds

The paper places five different problems (thek-pebble game problem, two problems aboutk finite automata, the reachability problem for Petri nets withk tokens, and the teachability problem for graphs whose k-dimensional edge sets are described by Cartesian products ofk factors) into the hierarchyNL _k of problems solvable by nondeterministic Turing machines ink-log₂ n space (and binary tape alphabet, to avoid tape speed-up). The results, when combined with the conjecture thatNL _i contains problems that requireO(n ^k ) deterministic time, show that these problems, while inP for every fixed value ofk, have polynomial deterministic time complexities with the degree of the polynomial growing linearly with the parameterk, and hence are, in this sense, gradually intractable.     

Inverse problems for granulometries by erosion

Let us associate to any binary planar shape X the erosion curve _X defined by _X: r IR^XA(XrB), where A(X) stands for the surface area of X and XrB for the eroded set of X with respect to the ball rB of size r. Note the analogy to shape quantification by granulometry. This paper describes the relationship between sets X and Y verifying _X = _Y. Under some regularity conditions on X, _X is expressed as an integral on its skeleton of the quench function q _X(distance to the boundary of X). We first prove that a bending of arcs of the skeleton of X does not affect _X: quantifies soft shapes. We then prove, in the generic case, that the five possible cases of behavior of the second derivative _X characterize five different situations on the skeleton Sk(X) and on the quench function q _X: simple points of Sk(X) where q _Xis a local minimum, a local maximum, or neither, multiple points of Sk(X) where q _Xis a local maximum or not. Finally, we give infinitesimal generators of the reconstruction process for the entire family of shapes Y verifying _X = _Y for a given X.     

Mesh Selection for a Nearly Singular Boundary Value Problem

In this paper, we investigate the numerical solution of a model equation u _xx = exp(– ) (and several slightly more general problems) when 1 using the standard central difference scheme on nonuniform grids. In particular, we are interested in the error behaviour in two limiting cases: (i) the total mesh point number N is fixed when the regularization parameter 0, and (ii) is fixed when N. Using a formal analysis, we show that a generalized version of a special piecewise uniform mesh 12 and an adaptive grid based on the equidistribution principle share some common features. And the optimal meshes give rates of convergence bounded by |log()| as 0 and N is given, which are shown to be sharp by numerical tests.     

The Kreisel length-of-proof problem

A first-order system F has theKreisel length-of-proof property if the following statement is true for all formulas(x): If there is ak1 such that for alln0 there is a proof of(¯n) in F with at mostk lines, then there is a proof of x(x) in F. We consider this property for Parikh systems, which are first-order axiomatic systems that contain a finite number of axiom schemata (including individual axioms) and a finite number of rules of inference. We prove that any usual Parikh system formulation of Peano arithmetic has the Kreisel length-of-proof property if the underlying logic of the system is formulated without a schema for universal instantiation in either one of two ways. (In one way, the formula to be instantiated is built up in steps, and in the other way, the term to be substituted is built up in steps.) Our method of proof uses techniques and ideas from unification theory.     

Size of the Largest Antichain in a Partition Poset

Partitions {(k ₁,..., k )} of a given set are considered as a partially ordered set (poset) with a natural partial ordering with respect to inclusion. Asymptotics for the size of the largest antichain in this poset is found for fixed.     

Transformation of programs for fault-tolerance

In this paper we describe how a program constructed for afault-free system can be transformed into afault-tolerant program for execution on a system which is susceptible to failures. A program is described by a set of atomic actions which perform transformations from states to states. We assume that a fault environment is represented by a programF. Interference by the fault environmentF on the execution of a programP can then be described as afault-transformation which transformsP into a program (P). This is proved to be equivalent to the programPP _F , whereP _F is derived fromP andF, and defines the union of the sets of actions ofP andF _P . A recovery transformation transformsP into a program (P) =PR by adding a set ofrecovery actions R, called arecovery program. If the system isfailstop and faults do not affect recovery actions, we have ((P))=(P)R=PP _F R We illustrate this approach to fault-tolerant programming by considering the problem of designing a protocol that guarantees reliable communication from a sender to a receiver in spite of faults in the communication channel between them.     

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.     

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.     

The Postal Network: A Recursive Network for Parameterized Communication Model

The postal network is an interconnection network that possesses many desirable properties in networking applications. It includes hypercubes and Fibonacci cubes as its special cases. Basically, the postal network forms a series (with series number ) that is based on the sequence N (n)=N (n–1)+N (n–), where n is the dimension and N (n) represents the number of nodes in an n-dimensional postal network in series . In this paper, we study topological properties of postal networks and relationships between different postal networks. One application of postal networks is also shown in implementing barrier synchronization using a special spanning tree called a postal tree. The postal network can also be considered as a flexible version of the hypercube by relaxing the restriction on the number of nodes, and hence, makes it possible to construct multicomputers with arbitrary sizes.