Sentences over Integral Domains and Their Computational Complexities

LetRbe a Hilbertian domain and letKbe its fraction field. Letψ(x₁, …, x_n, y) be a quantifier free arithmetical formula overR. We may also takeψ(x₁, …, x_n, y) to be an arithmetical formula overK[x₁, …, x_n] and write it asψ(y). In this paper we show that ifRhas enough non-units and x₁…x_n y ψ(x₁, …, x_n, y), called an ⁿ  sentence, is true inR, then y ψ(y) is true inK[x₁, …, x_n]. Also, ifR=K[T], whereKis an infinite integral domain andx₁…x_n y ψ(x₁, …, x_n, y)is true inR, then y ψ(y) is true inR[x₁, …, x_n]. These results are applied to find the upper and lower bounds of the time complexities of various decision problems on diophantine equations with parameters and arithmetical sentences. Some of the results are: 1. The decision problem of sentences and diophantine equations with parameters over the ring of integers of a global field are co-NP-complete. 2. The decision problem of sentences over the ring of integers of a global field is NP-complete. 3. LetKbe an infinite domain, the time complexities of the decision problems of equations with parameters and sentences over the polynomial ringK[t] are polynomial time reducible to factoring polynomials overK. 4. The decision problem of sentences over all algebraic integer rings is in P. 5. The decision problem of sentences over all integral domains with characteristic 0 is in P. 6. The time complexity of the decision problem of sentences over all integral domains is polynomial time reducible to factoring integers overZand factoring polynomials over finite fields.     

Kernel nonnegative matrix factorization for spectral EEG feature extraction

Nonnegative matrix factorization (NMF) seeks a decomposition of a nonnegative matrix X0 into a product of two nonnegative factor matrices U0 and V0, such that a discrepancy between X and UV is minimized. Assuming U=XW in the decomposition (for W0), kernel NMF (KNMF) is easily derived in the framework of least squares optimization. In this paper we make use of KNMF to extract discriminative spectral features from the time–frequency representation of electroencephalogram (EEG) data, which is an important task in EEG classification. Especially when KNMF with linear kernel is used, spectral features are easily computed by a matrix multiplication, while in the standard NMF multiplicative update should be performed repeatedly with the other factor matrix fixed, or the pseudo-inverse of a matrix is required. Moreover in KNMF with linear kernel, one can easily perform feature selection or data selection, because of its sparsity nature. Experiments on two EEG datasets in brain computer interface (BCI) competition indicate the useful behavior of our proposed methods.     

Strongly Hamiltonian laceability of the even k-ary n-cube

The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n  2.     

Approximate fixed point sequence for a finite family of asymptotically pseudocontractive mappings

Let E be a real Banach space and K be a nonempty, closed, convex, and bounded subset of E. Let T_i:K→K, i=1,2,…,N, be N uniformly L-Lipschitzian, uniformly asymptotically regular with sequences {ε_n}, and asymptotically pseudocontractive mappings with sequences , where {ε_n} and , i=1,2,…,N, satisfy certain mild conditions. Let a sequence {x_n} be generated from x₁K by

for all integers n1, where T_n=T_n(modN), {u_n} be a sequence in K, and {λ_n}, {θ_n} and {μ_n} are three real sequences in [0,1] satisfying appropriate conditions; then x_n−T_lx_n→0 as n→∞ for each l{1,2,…,N}.     

Reduction of Permutation-Invariant Polynomials: A Noncommutative Case Study

Let R be a commutative ring with 1, let RX₁,…,X_n/I be the polynomial algebra in the n≥4 noncommuting variables X₁,…,X_n over R modulo the set of commutator relations I={(X₁+···+X_n)*X_i=X_i*(X₁+···+X_n)|1≤i≤n}. Furthermore, let G be an arbitrary group of permutations operating on the indeterminates X₁,…,X_n, and let RX₁,…,X_n/I^G be the R-algebra of G-invariant polynomials in RX₁,…,X_n/I. The first part of this paper is about an algorithm, which computes a representation for any fRX₁,…,X_n/I^G as a polynomial in multilinear G-invariant polynomials, i.e., the maximal variable degree of the generators of RX₁,…,X_n/I^G is at most 1. The algorithm works for any ring R and for any permutation group G. In addition, we present a bound for the number of necessary generators for the representation of all G-invariant polynomials in RX₁,…,X_n/I^G with a total degree of at most d. The second part contains a first but promising analysis of G-invariant polynomials of solvable polynomial rings.     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

To be fair or efficient or a bit of both

Introducing a new concept of (α,β)-fairness, which allows for a bounded fairness compromise, so that a source is allocated a rate neither less than 0α1, nor more than β1, times its fair share, this paper provides a framework to optimize efficiency (utilization, throughput or revenue) subject to fairness constraints in a general telecommunications network for an arbitrary fairness criterion and cost functions. We formulate a non-linear program (NLP) that finds the optimal bandwidth allocation by maximizing efficiency subject to (α,β)-fairness constraints. This leads to what we call an efficiency–fairness function, which shows the benefit in efficiency as a function of the extent to which fairness is compromised. To solve the NLP we use two algorithms. The first is a well-known branch-and-bound-based algorithm called Lipschitz Global Optimization and the second is a recently developed algorithm called Algorithm for Global Optimization Problems (AGOP).We demonstrate the applicability of the framework to a range of examples from sharing a single link to efficiency fairness issues associated with serving customers in remote communities.     

Long paths in hypercubes with a quadratic number of faults

A path between distinct vertices u and v of the n-dimensional hypercube Q_n avoiding a given set of f faulty vertices is called long if its length is at least 2ⁿ-2f-2. We present a function (n)=Θ(n²) such that if f(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q_n. Moreover, the bound provided by (n) is asymptotically optimal. Furthermore, we show that assuming f(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.     

Approximating the Minimum Chain Completion problem

A bipartite graph G=(U,V,E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77–79] if there is a bijection such that Γ(π(1))Γ(π(2))Γ(π(|U|)), where Γ is a function that maps a node to its neighbors.We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U,V,E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G^′=(U,V,E^′) (E^′=EF) is a chain graph.     

On Some Schützenberger Conjectures

In this paper we consider factorizing codes C over A, i.e., codes verifying the factorization conjecture by Schützenberger. Let n be the positive integer such that aⁿC, we show how we can construct C starting with factorizing codes C′ with a^n′C′ and n′ < n, under the hypothesis that all words aⁱza^j in C, with z(A\a)A*(A\a) (A\a), satisfy i, j, > n. The operation involved, already introduced by Anselmo, is also used to show that all maximal codes C=P(A−1)S+1 with P, SZA and P or S in Za can be constructed by means of this operation starting with prefix and suffix codes. Old conjectures by Schützenberger have been revised.     

Effect of numerical integration on meshless methods

In this paper, we present the effect of numerical integration on meshless methods with shape functions that reproduce polynomials of degree k1. The meshless method was used on a second order Neumann problem and we derived an estimate for the energy norm of the error between the exact solution and the approximate solution from the meshless method under the presence of numerical integration. This estimate was obtained under the assumption that the numerical integration scheme satisfied a form of Green’s formula. We also indicated how to obtain numerical integration schemes satisfying this property.     

A Logic for Reasoning about Generic Judgments

This paper presents an extension of a proof system for encoding generic judgments, the logic FOλ^Δ of Miller and Tiu, with an induction principle. The logic FOλ^Δ is itself an extension of intuitionistic logic with fixed points and a “generic quantifier”, , which is used to reason about the dynamics of bindings in object systems encoded in the logic. A previous attempt to extend FOλ^Δ with an induction principle has been unsuccessful in modeling some behaviours of bindings in inductive specifications. It turns out that this problem can be solved by relaxing some restrictions on , in particular by adding the axiom B≡x.B, where x is not free in B. We show that by adopting the equivariance principle, the presentation of the extended logic can be much simplified. Cut-elimination for the extended logic is stated, and some applications in reasoning about an object logic and a simply typed λ-calculus are illustrated.     

Complexity of Computing the Local Dimension of a Semialgebraic Set

The paper describes several algorithms related to a problem of computing the local dimension of a semialgebraic set. Let a semialgebraic set V be defined by a system of k inequalities of the formf  ≥  0 with f  R [ X₁, ,X_n ], deg(f)  < d , andx   V . An algorithm is constructed for computing the dimension of the Zariski tangent space to V at x in time (kd)^O(n). Let x belong to a stratum of codimension l_xin V with respect to a smooth stratification ofV . Another algorithm computes the local dimension dim_x(V) with the complexity (k(l_x +  1)d)^O(l_x2n). Ifl  = max_x  Vl_x, and for every connected component the local dimension is the same at each point, then the algorithm computes the dimension of every connected component with complexity (k(l +  1)d)^O(l2n). If V is a real algebraic variety defined by a system of equations, then the complexity of the algorithm is less thankd^O(l2n) , and the algorithm also finds the dimension of the tangent space to V at x in time kd^O(n). Whenl is fixed, like in the case of a smooth V , the complexity bounds for computing the local dimension are (kd)^O(n)andkd^O(n) respectively. A third algorithm finds the singular locus ofV in time (kd)^O(n2).     

Improved bounds on sorting by length-weighted reversals

We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ)=ℓ^α for all α0, where ℓ is the length of the reversed subsequence. We present tight or nearly tight upper and lower bounds on the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given input. Furthermore, we give polynomial-time algorithms to determine the optimal reversal sequence for a restricted but interesting class of sequences and cost functions. Our results have direct application in computational biology to the field of comparative genomics.     

Existence of set-interpolating and energy-minimizing curves

We consider existence of curves which minimize an energy of the form ∫c^(k)p (k=1,2,… , 1<p<∞) under side-conditions of the form G_j(c(t_1,j),…,c^(k−1)(t_k,j))M_j, where G_j is a continuous function, t_i,j[0,1], M_j is some closed set, and the indices j range in some index set J. This includes the problem of finding energy minimizing interpolants restricted to surfaces, and also variational near-interpolating problems. The norm used for vectors does not have to be Euclidean.It is shown that such an energy minimizer exists if there exists a curve satisfying the side conditions at all, and if among the interpolation conditions there are at least k points to be interpolated. In the case k=1, some relations to arc length are shown.     

Fast periodic graph exploration with constant memory

We consider the problem of periodic exploration of all nodes in undirected graphs by using a finite state automaton called later a robot. The robot, using a constant number of states (memory bits), must be able to explore any unknown anonymous graph. The nodes in the graph are neither labelled nor coloured. However, while visiting a node v the robot can distinguish between edges incident to it. The edges are ordered and labelled by consecutive integers 1,…,d(v) called port numbers, where d(v) is the degree of v. Periodic graph exploration requires that the automaton has to visit every node infinitely many times in a periodic manner. In this paper, we are interested in minimisation of the length of the exploration period. In other words, we want to minimise the maximum number of edge traversals performed by the robot between two consecutive visits of a generic node, in the same state and entering the node by the same port. Note that the problem is unsolvable if the local port numbers are set arbitrarily, see [L. Budach, Automata and labyrinths, Math. Nachr. 86 (1978) 195–282]. In this context, we are looking for the minimum function π(n), such that, there exists an efficient deterministic algorithm for setting the local port numbers allowing the robot to explore all graphs of size n along a traversal route with the period π(n). Dobrev et al. proved in [S. Dobrev, J. Jansson, K. Sadakane, W.-K. Sung, Finding short right-hand-on-the-wall walks in graphs, in: Proc. 12th Colloquium on Structural Information and Communication Complexity, SIROCCO 2005, in: Lecture Notes in Comput. Sci., vol. 3499, Springer, Berlin, 2005, pp. 127–139] that for oblivious robots π(n)10n. Recently Ilcinkas proposed another port labelling algorithm for robots equipped with two extra memory bits, see [D. Ilcinkas, Setting port numbers for fast graph exploration, in: Proc. 13th Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, in: Lecture Notes in Comput. Sci., vol. 4056, Springer, Berlin, 2006, pp. 59–69], where the exploration period π(n)4n−2. In the same paper, it is conjectured that the bound 4n−O(1) is tight even if the use of larger memory is allowed. In this paper, we disprove this conjecture presenting an efficient deterministic algorithm arranging the port numbers, such that, the robot equipped with a constant number of bits is able to complete the traversal period in π(n)<3.75n−2 steps hence decreasing the existing upper bound. This reduces the gap with the lower bound of π(n)2n−2 holding for any robot.     

Isolation concepts for efficiently enumerating dense subgraphs

In an undirected graph G=(V,E), a set of k vertices is called c-isolated if it has less than ck outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all c-isolated maximal cliques in O(4^cc⁴|E|) time. We extend this to enumerating all maximal c-isolated cliques (which are a superset) and improve the running time bound to O(2.89^cc²|E|), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation.     

A note on Rooted Survivable Networks

The (undirected) Rooted Survivable Network Design (Rooted SND) problem is: given a complete graph on node set V with edge-costs, a root sV, and (node-)connectivity requirements , find a minimum cost subgraph G that contains r(t) internally-disjoint st-paths for all tT. For large values of k=max_tTr(t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Y. Lando, Z. Nutov, Inapproximability of survivable networks, Theoret. Comput. Sci. 410 (21–23) (2009) 2122–2125]. For Rooted SND, [J. Chuzhoy, S. Khanna, Algorithms for single-source vertex-connectivity, in: FOCS, 2008, pp. 105–114] gave recently an approximation algorithm with ratio O(k²logn). Independently, and using different techniques, we obtained at the same time a simpler primal–dual algorithm with the same ratio.     

Inductive Synthesis of Recursive Processes from Logical Properties

This paper proposes an inductive synthesis algorithm for a recursive process. To synthesize a process, facts, which must be satisfied by the target process, are given to the algorithm one by one since such facts are infinitely many in general. When n facts are input to the algorithm, it outputs a process which satisfies the given n facts. And this generating process is repeated infinitely many times. To represent facts of a process, we adopt a subcalculus of μ-calculus. First, we introduce a new preorder _d on recursive processes based on the subcalculus to discuss its properties. p_d q means that pf implies qf, for all formulae f in the subcalculus. Then, its discriminative power and relationship with other preorders are also discussed. Finally, we present the synthesis algorithm. The correctness of the algorithm can be stated that the output sequence of processes by the algorithm converges to a process, which cannot be distinguished from the intended one (if we could know it) by a given enumeration of facts, in the limit. A prototype system based on the algorithm is stated as well.     

The Undecidability of the First-Order Theories of One Step Rewriting in Linear Canonical Systems

By reduction from the halting problem for Minsky's two-register machines we prove that there is no algorithm capable of deciding the -theory of one step rewriting of an arbitrary finite linear confluent finitely terminating term rewriting system (weak undecidability). We also present a fixed such system with undecidable *-theory of one step rewriting (strong undecidability). This improves over all previously known results of the same kind.