waashk/dblp huggingface dataset:
languages in general algebras this paper presents the results of recent investigations into the question of when the context-free (cf) languages of an algebra are all recognizable. first, it is shown (theorem 2.1.3) that phrase structure (ps) languages are the same as the cf languages in any (finitely generated) generic algebra. mezei & wright (mw) previously generalized the equality of cf and recognizable languages in generic monadic algebras to arbitrary generic algebras. thus it now follows that the ps, cf and recognizable languages are the same in any generic algebra. this result has the following consequence: let &rgr; be a congruence on a generic algebra a with the property that there exists a ps grammar g on a such that the language generated by g from any element x of a is the &rgr; congruence class of x. then in a/&rgr;, the cf languages (which are precisely the homomorphic images of the cf languages in a) are the same as the recognizable languages (which are precisely the inverse homomorphic images of subsets of finite algebras). any algebra with this latter property is called regular. the following is a more powerful sufficient condition for the regularity of an algebra: suppose a and b are regular algebras and that f1 and f2 are homomorphisms from a to b. let r be a recognizable language in a and define &rgr; b &times; b by &rgr; &equil; {(x,y) &brvbar; ( @@@@ z &egr; r) (f1 (z) &equil; x &lgr; f2 (z) &equil; y }. then if &rgr; is a congruence on b, b/&rgr; is regular. any relation &rgr; (not necessarily a congruence) defined in the above way is called an algebraic transduction. it is shown that the notion of algebraic transduction generalizes the notion of binary transduction as presented for generic monadic algebras by elgot and mezei (em). some proofs have been omitted below, especially when they are standard or straightforward. details can be found in [s].
space efficient dynamic stabbing with fast queries. in dynamic stabbing, we operate on a dynamic set of intervals. a stabbing query asks for an interval containing a given point. this basic problem encodes problems such as method look-up in object oriented programming languages and classification in ip firewalls. for such application, very fast, say constant, query time is extremely important, small space is very important, and fast updates are good but the least important. previous solutions traded space and update time for fast queries. we show here that space needs not be sacrificed. we get the same trade-off between update time and query time but using only the space necessary for locating a query point among the interval end-points. all our bounds are optimal or near-optimal.
tensor norms and the classical communication complexity of nonlocal quantum measurement. nonlocality is at the heart of quantum information processing. in this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. we derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.as a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. this implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. while some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. we give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.our upper bounds are expressed in terms of some tensor norms on the measurement operator. those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.
reference machines require non-linear time to maintain disjoint sets this paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. as an example of the use of the model, the paper shows that any such machine requires non-linear time in the worst case to compute unions of disjoint sets on-line. all set union algorithms known to the author are instances of the model and are thus subject to the derived bound. one of the known algorithms achieves the bound to within a constant factor.
the complexity of propositional linear temporal logics the complexity of satisfiability and determination of truth in a particular finite structure are considered for different propositional linear temporal logics. it is shown that these problems are np-complete for the logic with f and are pspace-complete for the logics with f, x, with u, with u, s, x operators and for the extended logic with regular operators given by wolper.
context-free error analysis by evaluation of algebraic power series optimal error analysis with respect to a context-free language may be viewed as the evaluation of an algebraic power series. by generalization of the nodal span context-free recognition algorithm, any algebraic power series is computable in o(n3) steps. the closure of algebraic power series under sequential transduction yields a generous class of reasonable error measures for which optimal analysis is o(n3). included is minimizing the number of symbol insertions, deletions and/or replacements needed for correction, a special case which has been studied separately.
sparse polynomial approximation in finite fields. we consider a polynomial analogue of the hidden number problem which has recently been introduced by boneh and venkatesan. namely we consider the sparse polynomial approximation problem of recovering an unknown polynomial f(x) \in \f_p[x] with at most $m$ non-zero terms from approximate values of f(t) at polynomially many points t \in \f_p selected uniformly at random. the case of a polynomial f(x) = &agr; x corresponds to the hidden number problem. the above problem is related to the noisy polynomial interpolation problem and to the sparse polynomial interpolation problem which have recently been considered in the literature. our results are based on a combination of some number theory tools such as bounds of exponential sums and the number of solutions of congruences with the lattice reduction technique.
an algorithm generating the decision table of a deterministic bottom up parser for a subset of context free grammars an algorithm is described, whose input is a context-free grammar g and whose output is, if g fulfils a set of conditions, a decision table for a deterministic bottom up parser yielding the syntactic structure of the terminal sentences that belong to l (g). the complexity of the decision table depends on the stringency of the conditions satisfied by g and corresponds to some subsets of context free grammars which are compared with previously defined subsets such as ll(k), brc (m,k)-i.e bounded right context -, lr(k).
derandomizing homomorphism testing in general groups. the main result of this paper is a near-optimal derandomization of the affine homomorphism test of blum, luby, and rubinfeld [j. comput. system sci., 47 (1993), pp. 549-595]. we show that for any groups g and &ggr;, and any expanding generating set s of g, the natural deramdomized version of the blr test in which we pick an element x randomly from g and y randomly from s and test whether $f(x)\cdot f(y)=f(x\cdot y)$, performs nearly as well (depending of course on the expansion) as the original test. moreover, we show that the underlying homomorphism can be found by the natural local &ldquo;belief propagation decoding.&rdquo; we note that the original blr test uses $2\log_2 |g|$ random bits, whereas the derandomized test uses only $(1+o(1))\log_2 |g|$ random bits. this factor of 2 savings in the randomness complexity translates to a near quadratic savings in the length of the tables in the related locally testable codes (and possibly probabilistically checkable proofs which may use them). our result is a significant generalization of recent results that either refer to the special case of the groups $g=z_p^m$ and $&ggr; =z_p$ or are nonconstructive. we use simple combinatorial arguments and the transitivity of cayley graphs (and this analysis gives optimal results up to constant factors). previous techniques used the fourier transform, a method which seems unextendable to general groups (and furthermore gives suboptimal bounds). finally, we provide a polynomial time (in $|g|$) construction of a (somewhat) small ($|g|^{\epsilon}$) set of expanding generators for every group $g$, which yield efficient testers of randomness $(1+\epsilon) \log |g|$ for $g$. this result follows from a simple derandomization of a known probabilistic construction.
transformations and translations from the point of view of generalized finite automata theory the objective of this work is to expand the study of generalized finite automata theory by introducing generalized finite state mappings (finite state mappings of trees). in the process, we hope to provide an algebraic framework in which to study formalizations of transformations (in the sense that linguists use the term) and translations of natural and artificial languages. the concepts, &ldquo;syntax directed translation&rdquo; [2,18,19, 22, 29] and &ldquo;transformation&rdquo; [11, 25] can be formulated quite neatly within this framework. sections 2 and 3 present basic concepts of generalized finite automata theory and its relationship to context-free languages. we provide some general notation for transformations in section 4 and in the following four sections, two basic kinds of transformations will be introduced and certain fundamental properties proved. in section 9, these definitions will be related to others in the literature and several areas for further investigation will be indicated.
data type specification: parameterization and the power of specification techniques this paper extends our earlier work on abstract data types by providing an algebraic treatment of parametrized data types (e.g., sets-of-(), stacks-of-(), etc.), as well as answering a number of questions on the power and limitations of algebraic specification techniques. in brief: we investigate the &ldquo;hidden function&rdquo; problem (the need to include operations in specifications which we want to be hidden from the user); we prove that conditional specifications are inherently more powerful than equational specifications; we show that parameterized specifications must contain &ldquo;side conditions&rdquo; (e.g., that finite-sets-of-d requires an equality predicate on d), and we compare the power of the algebraic approach taken here with the more categorical approach of lehman and smyth.
on feasible numbers (preliminary version) we study complexity problems associated with generation and manipulation of integers. we show that many such questions may be formulated as problems about random access machines (rams), and recent results about rams with special instructions sets can be used to give estimates about the complexity of the manipulations. finally we settle an open problem about rams (which becomes more interesting in this setting), namely the power of unrestricted vector machines, studied in [5] [6] [2]. we prove that allowing arbitrary shifts (instead of bounded shifts) gives at most a polynomial reduction in the time necessary to recognize languages by vector machines, thus solving the main problem left unanswered by the papers of pratt and stockmeyer [5], [6] and hartmanis and simon [2], [3]. equivalently, it is possible to compare two integers, each obtained by a sequence of at most n operations of shift, sum, and boolean vector operations, within tape polynomial in n.
space-bounded probabilistic turing machine complexity classes are closed under complement (preliminary version) for tape constructible functions s(n)&ge;log n, if a language l is accepted by an s(n) tape bounded probabilistic turing machine, then there is an s(n) tape bounded probabilistic turing machine that accepts &lmarc;, the complement of l.
area-time complexity for vlsi the complexity of the discrete fourier transform (dft) is studied with respect to a new model of computation appropriate to vlsi technology. this model focuses on two key parameters, the amount of silicon area and time required to implement a dft on a single chip. lower bounds on area (a) and time (t) are related to the number of points (n) in the dft: at2&ge; n2/16. this inequality holds for any chip design based on any algorithm, and is nearly tight when t &equil; &thgr;(n1/2) or t &equil; &thgr;(log n). a more general lower bound is also derived: atx &equil; &ohgr;(n1+x/2), for 0&le;&times;&le;2.
polynomial reducibilities and upward diagonalizations an open question of [lls] is whether polynomial time many-one reducibility &le;mp and polynomial time turing reducibility &le;tp differ on np. an affirmative answer to this question would yield p @@@@ np as a corollary, but it is possible that p @@@@ np even if the answer is negative. ladner, lynch, and selman [lls] conjecture that if p @@@@ np then &le;mp and &le;tp differ on np. one method that might prove helpful in settling this conjecture is to exhibit an efficient construction that builds from any nonpolynomial set a a set b such that a &le;tp b but a @@@@mp b. if such a construction were sufficiently efficient, then when applied to a set a in np - p it would yield a set b in np/
sorting on a mesh-connected parallel computer two algorithms for sorting n2 elements on an n&times;n mesh-connected processor array that require 0(n) routing and comparison steps are presented. the best previous algorithms take time 0(n log n). our algorithms are shown to be optimal in time within small constant factors.
on the complexity of ram with various operation sets we prove that polynomial time bounded rams with the instruction set [shift, +, x, boolean ] accept exactly the languages in pspace. this generalizes previous results: [5] showed the same for the instruction set that does not include multiplication, [5] and [7] proved the weaker theorems, that rams (and even prams) with this instruction set could be simulated in exptape. the pram result is a simple corollary to our theorems. we also introduce other powerful string-manipulating instructions for rams, show a nontrivial simulation of turing machines by these rams, and show that in a sense such simulations are optimal.
lower bounds on the size of sweeping automata establishing good lower bounds on the complexity of languages is an important area of current research in the theory of computation. however, despite much effort, fundamental questions such as p &equil;? np and l &equil;? nl remain open. to resolve these questions it may be necessary to develop a deep combinatorial understanding of polynomial time or log space computations, possibly a formidable task. one avenue for approaching these problems is to study weaker models of computation for which the analogous problems may be easier to settle, perhaps yielding insight into the original problems. sakoda and sipser [3] raise the following question about finite automata: is there a polynomial p, such that every n-state 2nfa (two-way nondeterministic finite automaton) has an equivalent p(n)-state 2dfa? they conjecture a negative answer to this. in this paper we take a step toward proving this conjecture by showing that 2nfa are exponentially more succinct than 2dfa of a certain restricted form.
fully-dynamic min-cut. we show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in $$\ifmmode\expandafter\tilde\else\expandafter\~\fi{o}{\left( {{\sqrt n }} \right)}$$ worst-case time per edge insertion or deletion. within logarithmic factors, this matches the best time bound for 1-edge connectivity. previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was o(n2/3), dating back to focs'92. our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in o(log n) time per edge. by dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in $$\ifmmode\expandafter\tilde\else\expandafter\~\fi{o}{\left( {{\sqrt n }} \right)}$$ time per edge insertion or deletion. this algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in o(log n) time per edge, the update time increases to $$\ifmmode\expandafter\tilde\else\expandafter\~\fi{o}{\left( {{\sqrt m }} \right)}$$.
borel sets and circuit complexity it is shown that for every k, polynomial-size, depth-k boolean circuits are more powerful than polynomial-size, depth-(k&minus;1) boolean circuits. connections with a problem about borel sets and other questions are discussed.
integer priority queues with decrease key in constant time and the single source shortest paths problem. we consider fibonacci heap style integer priority queues supporting find-rain, insert, and decrease key operations in constant time. we present a deterministic linear space solution that with n integer keys supports delete in o(log log n) time. if the integers are in the range [0,n), we can also support delete in o(log log n) time.even for the special case of monotone priority queues, where the minimum has to be non-decreasing, the best previous bounds on delete were o((log n)1/(3-ε)) and o((log n)1/(4-ε)). these previous bounds used both randomization and amortization. our new bounds are deterministic, worst-case, with no restriction to monotonicity, and exponentially faster.as a classical application, for a directed graph with n nodes and m edges with non-negative integer weights, we get single source shortest paths in o(m + n log log n) time, or o(m + n log log c) if c is the maximal edge weight. the latter solves an open problem of ahuja, mehlhorn, orlin, and tarjan from 1990.
worst-case update times for fully-dynamic all-pairs shortest paths. we present here the first solution to the fully-dynamic all pairs shortest path problem where every update is faster than a recomputation from scratch in ω(n3log ⁄n) time. this is for a directed graph with arbitrary non-negative edge weights. an update inserts or deletes a vertex with all incident edges. after each such vertex update, we update a complete distance matrix in õ(n2.75) time.
approximate distance oracles. let g=(v,e) be an undirected weighted graph with |v|=n and |e|=m. let k\ge 1 be an integer. we show that g=(v,e) can be preprocessed in o(kmn^{1/k}) expected time, constructing a data structure of size o(kn^{1+1/k}), such that any subsequent distance query can be answered, approximately, in o(k) time. the approximate distance returned is of stretch at most 2k-1, i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1. we show that a 1963 girth conjecture of erd{\h{o}}s, implies that &ohgr(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1. the space requirement of our algorithm is, therefore, essentially optimal. the most impressive feature of our data structure is its constant query time, hence the name ``oracle''. previously, data structures that used only o(n^{1+1/k}) space had a query time of &ohgr(n^{1/k}) and a slightly larger, non-optimal, stretch. our algorithms are extremely simple and easy to implement efficiently. they also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.}
minimax parametric optimization problems and multi-dimensional parametric searching. the parametric minimax problem, which finds the parameter value minimizing the weight of a solution of a combinatorial maximization problem, is a fundamental problem in sensitivity analysis. moreover, several problems in computational geometry can be formulated as parametric minimax problems. the parametric search paradigm gives an efficient sequential algorithm for a convex parametric minimax problem with one parameter if the original non-parametric problem has an efficient parallel algorithm. we consider the parametric minimax problem with d parameters for a constant d, and solve it by using multidimensional version of the parametric search paradigm. as a new feature, we give a feasible region in the parameter space in which the parameter vector must be located.typical results obtained as applications are: (1) efficient solutions for some geometric problems, including theoretically efficient solutions for the minimum diameter bridging problem in d-dimensional space between convex polytopes. (2) parametric polymatroid optimization, for example, o(n log n) time algorithm to compute the parameter vector minimizing k-largest linear parametric elements with d dimensions.
time-space tradeoffs for computing functions, using connectivity properties of their circuits recent research has investigated time-space tradeoffs for register allocation strategies of certain fixed sets of expressions. this paper is concerned with the time-space tradeoff for register allocation strategies of any set of expressions which compute given functions. time-space tradeoffs for pebbling superconcentrators and grates are developed. corollaries which follow include tradeoffs for any straight-line program which computes polynomial multiplication, polynomial convolution, the discrete fourier transform, oblivious merging, and most sets of linear forms.
an optimal solution to a wire-routing problem (preliminary version) a wire-routing problem which arises commonly in the layout of circuits for very large scale integration (vlsi) is discussed. given the coordinates of terminals u1, u2, ..., un of one component and v1, v2, ..., vn of another, the problem is to lay out n wires so that the ith wire connects ui to vi, and adjacent wires are separated at least by some fixed distance. the solution with minimum wire length is characterized, and an optimal algorithm which constructs it is presented.
two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations any boolean straight-line program which computes the transitive closure of an nxn boolean matrix by successive squaring requires time exceeding any polynomial in n if the space used is o(n). this is the first demonstration of a &ldquo;natural&rdquo; algorithm which (1) has a polynomial time implementation and (2) has a small (e.g., o(log2n)) space implementation, but (3) has no implementation running in polynomial time and small space simultaneously. it is also shown that any implementation of warshall's transitive closure algorithm requires &ohgr;(n) space.
deadlock- and livelock-free packet switching networks a controller for a packet switching network is an algorithm to control the flow of packets through the network. a local controller is a controller executed independently by each node in the network, using only local information available to these nodes. a controller is deadlock- and livelock-free if it guarantees that every packet in the network reaches its destination within a finite amount of time. we present a local controller which is proved to be deadlock- and livelock-free.