Learning multiple languages in groups

We consider a variant of Gold’s learning paradigm where a learner receives as input n$n$ different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more “coarse” classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed n$n$ different languages, can produce m$m$ grammars covering all input languages, but cannot produce k$k$ grammars covering input languages for any k>m$k>m$. We also consider a variant of this task, where each of the output grammars may not cover more than r$r$ input languages. Our main results indicate that the major factor affecting classification capabilities is the difference n−m$n-m$ between the number n$n$ of input languages and the number m$m$ of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n$n$ (the number of input languages), m$m$ (number of output grammars), and r$r$ (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters n,m,r$n,m,r$ of certain types.     

Paths and trails in edge-colored graphs

This paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s$s$ and t$t$ in an edge-colored graph from an algorithmic perspective. First we show that several versions of the s−t$s-t$ path/trail problem have polynomial solutions including the shortest path/trail case. We give polynomial algorithms for finding a longest properly edge-colored path/trail between s$s$ and t$t$ for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. Next, we prove that deciding whether there exist k$k$ pairwise vertex/edge disjoint properly edge-colored s−t$s-t$ paths/trails in a c$c$-edge-colored graph G^c$G^c$ is NP-complete even for k=2$k=2$ and c=Ω(n²)$c=\Omega \left(n^2\right)$, where n$n$ denotes the number of vertices in G^c$G^c$. Moreover, we prove that these problems remain NP-complete for c$c$-edge-colored graphs containing no properly edge-colored cycles and c=Ω(n)$c=\Omega \left(n\right)$. We obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.     

Claw finding algorithms using quantum walk

The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. Given two functions, f$f$ and g$g$, with domain sizes N$N$ and M$M$(N≤M)$(N\le M)$, respectively, and the same range, the goal of the problem is to find x$x$ and y$y$ such that f(x)=g(y)$f\left(x\right)=g\left(y\right)$. This problem has been considered in both quantum and classical settings in terms of query complexity. This paper describes an optimal algorithm that uses quantum walk to solve this problem. Our algorithm can be slightly modified to solve the more general problem of finding a tuple consisting of elements in the two function domains that has a prespecified property. It can also be generalized to find a claw of k$k$ functions for any constant integer k>1$k>1$, where the domain sizes of the functions may be different.     

The cell probe complexity of succinct data structures

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n$n$-bit data with s=n+r$s=n+r$ bits such that queries (of a certain type) about the data can be answered by reading at most t$t$ bits of the representation. Ideally, we would like to keep both s$s$ and t$t$ small, but there are tradeoffs between the values of s$s$ and t$t$ that limit the possibilities of keeping both parameters small.     

A note on the number of squares in a word

Fraenkel and Simpson [A.S. Fraenkel, J. Simpson, How many squares can a string contain? J. Combin. Theory Ser. A 82 (1998) 112–120] proved that the number of squares in a word of length n$n$ is bounded by 2n$2n$. In this note we improve this bound to 2n−Θ(logn)$2n-\Theta (logn)$. Based on the numerical evidence, the conjectured bound is n$n$.     

Faster algorithms for computing Hong’s bound on absolute positiveness

We show how to compute Hong’s bound for the absolute positiveness of a polynomial in d$d$ variables with maximum degree δ$\delta$ in O(nlog^dn)$O\left(n{log}^{d}n\right)$ time, where n$n$ is the number of non-zero coefficients. For the univariate case, we give a linear time algorithm. As a consequence, the time bounds for the continued fraction algorithm for real root isolation improve by a factor of δ$\delta$.     

Expanders and time-restricted branching programs

The replication number   of a branching program is the minimum number R$R$ such that along every accepting computation at most R$R$ variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0$0$ (read-once programs) and the total number n$n$ of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn)$R=o(n/logn)$. We improve this to R≤?n$R\le ?n$ for a constant ?>0$?>0$. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n$(1+?)n$ time branching programs for a constant ?>0$?>0$. We prove these lower bounds for quadratic functions of Ramanujan graphs.     

Conjunctive query evaluation by search-tree revisited

The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database D$D$, a conjunctive query Q$Q$, and a tuple a$a$, tests whether Q(a)$Q\left(a\right)$ holds in D$D$ in time bounded by a polynomial in (sn)^logk(sn)^loglogn${\left(sn\right)}^{logk}{\left(sn\right)}^{loglogn}$ and n^r$n^r$, where n$n$ is the size of the domain of the database, k$k$ is the number of bound variables of the conjunctive query, s$s$ is the size of the optimal search-tree, and r$r$ is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the n^O(k)$n^{O\left(k\right)}$ bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks.     

Gröbner bases with respect to several orderings and multivariable dimension polynomials

Let D=K[X]$D=K\left[X\right]$ be a ring of Ore polynomials over a field K$K$ and let a partition of the set of indeterminates into p$p$ disjoint subsets be fixed. Considering D$D$ as a filtered ring with the natural p$p$-dimensional filtration, we introduce a special type of reduction in a free D$D$-module and develop the corresponding Gröbner basis technique (in particular, we obtain a generalization of the Buchberger Algorithm). Using such a modification of the Gröbner basis method, we prove the existence of a Hilbert-type dimension polynomial in p$p$ variables associated with a finitely generated filtered D$D$-module, give a method of computation and describe invariants of such a polynomial. The results obtained are applied in differential algebra where the classical theorems on differential dimension polynomials are generalized to the case of differential structures with several basic sets of derivation operators.     

The number of roots of a lacunary bivariate polynomial on a line

We prove that a polynomial f∈R[x,y]$f\in \mathbb{R}[x,y]$ with t$t$ non-zero terms, restricted to a real line y=ax+b$y=ax+b$, either has at most 6t−4$6t-4$ zeros or vanishes over the whole line. As a consequence, we derive an alternative algorithm for deciding whether a linear polynomial y−ax−b∈K[x,y]$y-ax-b\in K[x,y]$ divides a lacunary polynomial f∈K[x,y]$f\in K[x,y]$, where K$K$ is a real number field. The number of bit operations performed by the algorithm is polynomial in the number of non-zero terms of f$f$, in the logarithm of the degree of f$f$, in the degree of the extension K/Q$K/\mathbb{Q}$ and in the logarithmic height of a$a$, b$b$ and f$f$.     

On the minimum of a positive polynomial over the standard simplex

We present a new positive lower bound for the minimum value taken by a polynomial P$P$ with integer coefficients in k$k$ variables over the standard simplex of R^k${\mathbb{R}}^k$, assuming that P$P$ is positive on the simplex. This bound depends only on the number of variables k$k$, the degree d$d$ and the bitsize τ$\tau$ of the coefficients of P$P$ and improves all the previous bounds for arbitrary polynomials which are positive over the simplex.     

Divergence bounded computable real numbers

A real x$x$ is called h$h$-bounded computable  , for some function h:N→N$h:\mathbb{N}\to \mathbb{N}$, if there is a computable sequence (_xs)$(x_s)$ of rational numbers which converges to x$x$ such that, for any n∈N$n\in \mathbb{N}$, at most h(n)$h(n)$ non-overlapping pairs of its members are separated by a distance larger than 2^-n$2^{-n}$. In this paper we discuss properties of h$h$-bounded computable reals for various functions h$h$. We will show a simple sufficient condition for a class of functions h$h$ such that the corresponding h$h$-bounded computable reals form an algebraic field. A hierarchy theorem for h$h$-bounded computable reals is also shown. Besides we compare semi-computability and weak computability with the h$h$-bounded computability for special functions h$h$.     

On integral generalized policy iteration for continuous-time linear quadratic regulations

This paper mathematically analyzes the integral generalized policy iteration (I-GPI) algorithms applied to a class of continuous-time linear quadratic regulation (LQR) problems with the unknown system matrix A$A$. GPI is the general idea of interacting policy evaluation and policy improvement steps of policy iteration (PI), for computing the optimal policy. We first introduce the update horizon ?$?$, and then show that (i) all of the I-GPI methods with the same ?$?$ can be considered equivalent and that (ii) the value function approximated in the policy evaluation step monotonically converges to the exact one as ?→∞$?\to \infty$. This reveals the relation between the computational complexity and the update (or time) horizon of I-GPI as well as between I-PI and I-GPI in the limit ?→∞$?\to \infty$. We also provide and discuss two modes of convergence of I-GPI; I-GPI behaves like PI in one mode, and in the other mode, it performs like value iteration for discrete-time LQR and infinitesimal GPI (?→0$?\to 0$). From these results, a new classification of the integral reinforcement learning is formed with respect to ?$?$. Two matrix inequality conditions for stability, the region of local monotone convergence, and data-driven (adaptive) implementation methods are also provided with detailed discussion. Numerical simulations are carried out for verification and further investigations.     

State-complexity hierarchies of uniform languages of alphabet-size length

We study the state complexity of certain simple languages. If A$A$ is an alphabet of k$k$ letters, then a k$k$-language   is a nonempty set of words of length k$k$, that is, a uniform language of length k$k$. We show that the minimal state complexity of a k$k$-language is k+2$k+2$, and the maximal, (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. We prove constructively that, for every i$i$ between the minimal and maximal bounds, there is a language of state complexity i$i$. We introduce a class of automata accepting sets of words that are permutations of A$A$; these languages define a complete hierarchy of complexities between k²−k+3$k^2-k+3$ and 2^k+1$2^k+1$. The languages of another class of automata, based on k$k$-ary trees, define a complete hierarchy of complexities between 2^k+1$2^k+1$ and (k^k−1−1)/(k−1)+2^k+1$(k^{k-1}-1)/(k-1)+2^k+1$. This provides new examples of uniform languages of maximal complexity.     

Liouvillian solutions of linear difference–differential equations

For a field k$k$ with an automorphism σ$\sigma$ and a derivation δ$\delta$, we introduce the notion of Liouvillian solutions of linear difference–differential systems {σ(Y)=AY,δ(Y)=BY}$\{\sigma \left(Y\right)=AY,\delta \left(Y\right)=BY\}$ over k$k$ and characterize the existence of Liouvillian solutions in terms of the Galois group of the systems. In the forthcoming paper, we will propose an algorithm for deciding if linear difference–differential systems of prime order have Liouvillian solutions.