waashk/dblp huggingface dataset:
polynomials, fragments of temporal logic and the variety da over traces. we show that some language-theoretic and logical characterizations of recognizable word languages whose syntactic monoid is in the variety da also hold over traces. to this end we give algebraic characterizations for the language operations of generating the polynomial closure and generating the unambiguous polynomial closure over traces. we also show that there exist natural fragments of local temporal logic that describe this class of languages corresponding to da. all characterizations are known to hold for words.
on critical exponents in fixed points of non-erasing morphisms. let @s be an alphabet of size t, let f:@s^*->@s^* be a non-erasing morphism, let w be an infinite fixed point of f, and let e(w) be the critical exponent of w. we prove that if e(w) is finite, then for a uniform f it is rational, and for a non-uniform f it lies in the field extension q[r,@l"1,...,@l"@?], where r,@l"1,...,@l"@? are the eigenvalues of the incidence matrix of f. in particular, e(w) is algebraic of degree at most t. under certain conditions, our proof implies an algorithm for computing e(w).
the multi-multiway cut problem. in this paper, we define and study a natural generalization of the multicut and multiway cut problems: the minimum multi-multiway cut problem. the input to the problem is a weighted undirected graph g=(v,e) and k sets s"1,s"2,...,s"k of vertices. the goal is to find a subset of edges of minimum total weight whose removal completely disconnects each one of the sets s"1,s"2,...,s"k, i.e., disconnects every pair of vertices u and v such that u,v@?s"i, for some i. this problem generalizes both the multicut problem, when |s"i|=2, for 1@?i@?k, and the multiway cut problem, when k=1. we present an approximation algorithm for the multi-multiway cut problem with an approximation ratio which matches that obtained by garg, vazirani, and yannakakis on the standard multicut problem. namely, our algorithm has an o(logk) approximation ratio. moreover, we consider instances of the minimum multi-multiway cut problem which are known to have an optimal solution of light weight. we show that our algorithm has an approximation ratio substantially better than o(logk) when restricted to such ''light'' instances. specifically, we obtain an o(loglp)-approximation algorithm for the problem when all edge weights are at least 1 (here lp denotes the value of a natural linear programming relaxation of the problem). the latter improves the o(loglplogloglp) approximation ratio for the minimum multicut problem (implied by the work of seymour and even et al.).
turing's unpublished algorithm for normal numbers. in an unpublished manuscript, alan turing gave a computable construction to show that absolutely normal real numbers between 0 and 1 have lebesgue measure 1; furthermore, he gave an algorithm for computing instances in this set. we complete his manuscript by giving full proofs and correcting minor errors. while doing this, we recreate turing's ideas as accurately as possible. one of his original lemmas remained unproved, but we have replaced it with a weaker lemma that still allows us to maintain turing's proof idea and obtain his result.
bernstein-bezoutian matrices and curve implicitization. a new application of bernstein-bezoutian matrices, a type of resultant matrices constructed when the polynomials are given in the bernstein basis, is presented. in particular, the approach to curve implicitization through sylvester and bezout resultant matrices and bivariate interpolation in the usual power basis is extended to the case in which the polynomials appearing in the rational parametric equations of the curve are expressed in the bernstein basis, avoiding the basis conversion from the bernstein to the power basis. the coefficients of the implicit equation are computed in the bivariate tensor-product bernstein basis, and their computation involves the bidiagonal factorization of the inverses of certain totally positive matrices.
paging with connections: fifo strikes again. we continue the study of the integrated document and connection caching problem. we focus on the case where the connection cache has a size of one and show that this problem is not equivalent to standard paging, even if there are only two locations for the pages, by giving the first lower bound that is strictly higher than k for this problem. we then give the first upper bound below the trivial value of 2k for this problem. our upper bound is k+4@? where @? is the number of locations where the requested pages in a phase come from. this algorithm groups pages by location. in each phase, it evicts all pages from one location before moving on to the next location. in contrast, we show that the lru algorithm is not better than 2k-competitive. we also examine the resource augmented model and show that the plain fifo algorithm is optimal for the case h=2 and all k>=2, where h is the size of the offline document cache. we show that also in this case fifo is better than lru, although this is not true for standard paging.
digital lines with irrational slopes. how to construct a digitization of a straight line and how to be able to recognize a straight line in a set of pixels are very important topics in computer graphics. the aim of the present paper is to give a mathematically exact and consistent description of digital straight lines according to rosenfeld's definition. the digitizations of lines with slopes 0
randomized algorithm for the sum selection problem. let a be a sequence of n real numbers a"1,a"2,...,a"n. we consider the sum selection problem as that of finding the segment a(i^*,j^*) such that the rank of s(i^*,j^*)=@?"t"="i"^"*^j^^^*a"t over all possible feasible segments is k, where a feasible segment a(i,j)=a"i,a"i"+"1,...,a"j is a consecutive subsequence of a, and its width j-i+1 satisfies @?@?j-i+1@?u for some given integers @? and u, and @?@?u. it is a generalization of two well-known problems: the selection problem in computer science for which @?=u=1, and the maximum sum segment problem in bioinformatics for which the rank k is the total number of possible feasible segments. we will give a randomized algorithm for the sum selection problem that runs in expected o(nlog(u-@?)) time. it matches the optimal o(n) time randomized algorithm for the selection problem. we can also solve the k maximum sums problem, to enumerate the k largest sums, in expected o(nlog(u-@?)+k) time. the previously best known result was an algorithm that solves this problem for the case when @?=1, u=n and runs in o(nlog^2n+k) time in the worst case.
self-improved gaps almost everywhere for the agnostic approximation of monomials. given a learning sample, we focus on the hardness of finding monomials having low error, inside the interval bounded below by the smallest error achieved by a monomial (the best rule), and bounded above by the error of the default class (the poorest rule). it is well-known that when its lower bound is zero, it is an easy task to find, in linear time, a monomial with zero error. what we prove is that when this bound is not zero, regardless of the location of the default class in (0,1/2), it becomes a huge complexity burden to beat significantly the default class. in fact, under some complexity-theoretical assumptions, it may already be hard to beat the trivial approximation ratios, even when relaxing the time complexity constraint to be quasi-polynomial or sub-exponential. our results also hold with uniform weights over the examples.
ranking k maximum sums. given a sequence of n real numbers and an integer parameter k, the problem studied in this paper is to compute k subsequences of consecutive elements with the sums of their elements being the largest, the second largest, ..., and the kth largest among all possible range sums of the input sequence. for any value of k, 1@?k@?n(n+1)/2, we design a fast algorithm that takes o(n+klogn) time in the worst case to compute and rank all such subsequences. we also prove that our algorithm is optimal for k=o(n) by providing a matching lower bound. moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined). furthermore, given the fact that we have computed the @?th largest sums, our algorithm retrieves the (@?+1)th largest sum in o(logn) time, after o(n) time of preprocessing.
semi-online scheduling problems on two identical machines with inexact partial information. in semi-online scheduling problems, we always assume that some partial additional information is exactly known in advance. this may not be true in some applications. this paper considers semi-online scheduling problems on two identical machines with inexact partial information. three versions are considered, where we know in advance that the total size of all jobs, the optimal value, and the largest job size are in given intervals, respectively, while their exact values are unknown. we give both lower bounds of the problems and competitive ratios of algorithms as functions of a so-called disturbance parameter r@?[1,~). we establish for which r the inexact partial information is useful to improve the performance of a semi-online algorithm with respect to its pure online problem. optimal or near optimal algorithms are then obtained.
acknowledged broadcasting and gossiping in ad hoc radio networks. a radio network is a collection of transmitter-receiver devices (referred to as nodes). acknowledged radio broadcasting (arb) means transmitting a message from one special node called the source to all other nodes and informing the source about its completion. in our model, each node takes a synchronization per round and performs transmission or reception at one round. each node does not have a collision detection capability, and knows only its own id. in [b.s. chlebus, l. ga@?sieniec, a.m. gibbons, a. pelc, w. rytter, deterministic broadcasting in ad hoc radio networks, distributed computing 15 (2002) 27-38], it is proved that no arb algorithm exists in the model without collision detection. in this paper, we show that if n>=2, where n is the number of nodes in the network, we can construct arb algorithms in o(n) rounds for bidirectional graphs and in o(n^4^/^3log^1^0^/^3n) rounds for strongly connected graphs and construct acknowledged radio gossiping (arg) algorithms in o(nlog^3n) rounds for bidirectional graphs and in o(n^4^/^3log^1^0^/^3n) rounds for strongly connected graphs without collision detection.
defect particle kinematics in one-dimensional cellular automata. let a^z be the cantor space of bi-infinite sequences in a finite alphabet a, and let @s be the shift map on a^z. a cellular automaton is a continuous, @s-commuting self-map @f of a^z, and a @f-invariant subshift is a closed, (@f,@s)-invariant subset s@?a^z. suppose a@?a^z is s-admissible everywhere except for some small region we call a defect. it has been empirically observed that such defects persist under iteration of @f, and often propagate like 'particles'. we characterize the motion of these particles, and show that it falls into several regimes, ranging from simple deterministic motion, to generalized random walks, to complex motion emulating turing machines or pushdown automata. one consequence is that some questions about defect behaviour are formally undecidable.
an extremal graph with given bandwidth. the graph bandwidth problem is a well-known np-complete problem. the relation between size of a graph and bandwidth is very interesting. the minimum size required in g with bandwidth b is denoted as m(n,b) while the graph g of order n and bandwidth b with size m(n,b) is called an extremal graph. this paper provides the minimum size for a graph of odd order n, n>=9, and bandwidth (n+1)/2, and shows that k"2","n"-"2 is the only extremal graph of m(n,(n+1)/2).
coordinating team players within a noisy iterated prisoner's dilemma tournament. in this paper, we present our investigation into the use of a team of players within a noisy iterated prisoner's dilemma (ipd) tournament. we show that the members of such a team are able to use a pre-arranged sequence of moves that they make at the start of each interaction in order to recognise one another, and that by coordinating their actions they can increase the chances that one of the team members wins the round-robin style tournament. we consider, in detail, the factors that influence the performance of this team and we show that the problem that the team members face, when they attempt to recognise one another within the noisy ipd tournament, is exactly analogous to the problem, studied in information theory, of communicating reliably over a noisy channel. thus we demonstrate that we can use error-correcting codes to implement this recognition, and by doing so, further optimise the performance of the team.
classes of representable disjoint np-pairs. for a propositional proof system p we introduce the complexity class dnpp(p) of all disjoint np-pairs for which the disjointness of the pair is efficiently provable in the proof system p. we exhibit structural properties of proof systems which make canonical np-pairs associated with these proof systems hard or complete for dnpp(p). moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for dnpp(p) and the reductions between the canonical pairs exist.
algorithms for long paths in graphs. we obtain a polynomial algorithm in o(nm) time to find a long path in any graph with n vertices and m edges. the length of the path is bounded by a parameter defined on neighborhood condition of any three independent vertices of the path. an example is given to show that this bound is better than several classic results.
faster and simpler approximation algorithms for mixed packing and covering problems. we propose an algorithm for approximately solving the mixed packing and covering problem; given a convex compact set 0@?=(1-@e)b or decide that {x@?b|f(x)@?a,g(x)>=b}=0@?. here f,g:b->r"+^m are vectors whose components are m non-negative convex and concave functions, respectively, and a,b@?r"+"+^m are constant positive vectors. our algorithm requires an efficient feasibility oracle or block solver which, given vectors c,d@?r"+^m and @a@?r"+, computes x@?@?b such that c^tf(x@?)-d^tg(x@?)@?@a or correctly decides that no such x@?@?b exists. our algorithm, which is based on the lagrangian or price-directive decomposition method, generalizes the result from [k. jansen, approximation algorithm for the mixed fractional packing and covering problem, in: proceedings of 3rd ifip conference on theoretical computer science, ifip tcs 2004, kluwer, 2004, pp. 223-236; siam journal on optimization 17 (2006) 331-352] and needs only o(m(lnm+@e^-^2ln@e^-^1)) iterations or calls to the feasibility oracle. furthermore we show that a more general block solver can be used to obtain a more general approximation within the same runtime bound.
panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements. in this paper, we deal with the graph g"0@?g"1 obtained from merging two graphs g"0 and g"1 with n vertices each by n pairwise nonadjacent edges joining vertices in g"0 and vertices in g"1. the main problems studied are how fault-panconnectivity and fault-pancyclicity of g"0 and g"1 are translated into fault-panconnectivity and fault-pancyclicity of g"0@?g"1, respectively. many interconnection networks such as hypercube-like interconnection networks can be represented in the form of g"0@?g"1 connecting two lower dimensional networks g"0 and g"1. applying our results to a class of hypercube-like interconnection networks called restricted hl-graphs, we show that in a restricted hl-graph g of degree m(>=3), each pair of vertices are joined by a path in g@?f of every length from 2m-3 to |v(g@?f)|-1 for any set f of faulty elements (vertices and/or edges) with |f|@?m-3, and there exists a cycle of every length from 4 to |v(g@?f)| for any fault set f with |f|@?m-2.
well quasi-orders generated by a word-shuffle rewriting. given a set i of words, the set l"@?"""i^@e of all words obtained by the shuffle of (copies of) words of i is naturally provided with a partial order: for u,v in l"@?"""i^@e, u@?"i^*v if and only if v is the shuffle of u and another word of l"@?"""i^@e. in [f. d'alessandro, s. varricchio, well quasi-orders, unavoidable sets and derivation systems, in: word avoidability complexity and morphisms (wacam), rairo theoretical informatics and applications 40 (3) (2006) 407-426 (special issue)], the authors have opened the problem of the characterization of the finite sets i such that @?"i^* is a well quasi-order on l"@?"""i^@e. in this paper we give an answer in the case when i consists of a single word w.
improved algorithms for quantum identification of boolean oracles. the oracle identification problem (oip) was introduced by ambainis et al. [a. ambainis, k. iwama, a. kawachi, h. masuda, r.h. putra, s. yamashita, quantum identification of boolean oracles, in: proc. of stacs'04, in: lncs, vol. 2996, 2004, pp. 105-116]. it is given as a set s of m oracles and a blackbox oracle f. our task is to figure out which oracle in s is equal to the blackbox f by making queries to f. oip includes several problems such as the grover search as special cases. in this paper, we improve the algorithms in [a. ambainis, k. iwama, a. kawachi, h. masuda, r.h. putra, s. yamashita, quantum identification of boolean oracles, in: proc. of stacs'04, in: lncs, vol. 2996, 2004, pp. 105-116] by providing a mostly optimal upper bound of query complexity for this problem: (i) for any oracle set s such that |s|@?2^n^^^d(d
closure properties for the class of behavioral models. hidden k-logics can be considered as the underlying logics of program specification. they constitute natural generalizations of k-deductive systems and encompass deductive systems as well as hidden equational logics and inequational logics. in our abstract algebraic approach, the data structures are sorted algebras endowed with a designated subset of their visible parts, called filter, which represents a set of truth values. we present a hierarchy of classes of hidden k-logics. the hidden k-logics in each class are characterized by three different kinds of conditions, namely, properties of their leibniz operators, closure properties of the class of their behavioral models, and properties of their equivalence systems. using equivalence systems, we obtain a new and more complete analysis of the axiomatization of the behavioral models. this is achieved by means of the leibniz operator and its combinatorial properties.
sos formats and meta-theory: 20 years after. in 1981 structural operational semantics (sos) was introduced as a systematic way to define operational semantics of programming languages by a set of rules of a certain shape [g.d. plotkin, a structural approach to operational semantics, technical report daimi fn-19, computer science department, aarhus university, aarhus, denmark, september 1981]. subsequently, the format of sos rules became the object of study. using so-called transition system specifications (tss's) several authors syntactically restricted the format of rules and showed several useful properties about the semantics induced by any tss adhering to the format. this has resulted in a line of research proposing several syntactical rule formats and associated meta-theorems. properties that are guaranteed by such rule formats range from well-definedness of the operational semantics and compositionality of behavioral equivalences to security-, time- and probability-related issues. in this paper, we provide an overview of sos rule formats and meta-theorems formulated around them.
an auction-based market equilibrium algorithm for a production model. we present an auction-based algorithm for computing market equilibrium prices in a production model, in which producers have a single linear production constraint, and consumers have linear utility functions. we provide algorithms for both the fisher and arrow-debreu versions of the problem.
a primal-dual algorithm for computing fisher equilibrium in the absence of gross substitutability property. we provide the first strongly polynomial time exact combinatorial algorithm to compute fisher equilibrium for the case when utility functions do not satisfy the gross substitutability property. the motivation for this comes from the work of kelly, maulloo, and tan [f.p. kelly, a.k. maulloo, d.k.h. tan, rate control for communication networks: shadow prices, proportional fairness and stability, journal of operational research (1998)] and kelly and vazirani [f.p. kelly, vijay v. vazirani, rate control as a market equilibrium (2003) (in preparation)] on rate control in communication networks. we consider a tree like network in which root is the source and all the leaf nodes are the sinks. each sink has got a fixed amount of money which it can use to buy the capacities of the edges in the network. the edges of the network sell their capacities at certain prices. the objective of each edge is to fix a price that can fetch the maximum money for it, and the objective of each sink is to buy capacities on edges in such a way that it can facilitate the sink to pull maximum flow from the source. in this problem, the edges and the sinks play precisely the role of sellers and buyers, respectively, in fisher's market model. the utility of a buyer (or sink) takes the form of a leontief function which is known for not satisfying gross substitutability property. we develop an o(m^3) exact combinatorial algorithm for computing equilibrium prices of the edges. the time taken by our algorithm is independent of the values of sink money and edge capacities. a corollary of our algorithm is that equilibrium prices and flows are rational numbers. although there are algorithms to solve this problem they are all based on convex programming techniques. to the best of our knowledge, ours is the first strongly polynomial time exact combinatorial algorithm for computing equilibrium prices of fisher's model under the case when buyers' utility functions do not satisfy gross substitutability property.
colored visual cryptography without color darkening. in a visual cryptography scheme a secret image is encoded into n shares, in the form of transparencies. the shares are then distributed to n participants. qualified subsets of participants can recover the secret image by superimposing their transparencies. non-qualified subsets of participants have no information about the secret image. in this paper we consider the case when the secret image is a colored image. most of the previous work on colored visual cryptography allows the superposition of pixels having the same color assuming that the resulting pixel still has the same color. this is not what happens in reality since when superimposing two pixels of the same color one gets a darker version of that color, which effectively is a different color. superimposing many pixels of the same color might result in a so dark version of the color that the resulting pixel might not be distinguishable from a black pixel. in this paper we propose a model where the reconstruction has to guarantee that the reconstructed secret pixel has the exact same color of the original one and not a darker version of it. we consider (k,n)-threshold schemes where a qualified set of participants consists of any k participants. we provide a general construction for any k, 2@?k@?n and a construction for the special case k=2. we also prove lower bounds on the pixel expansion (which is a measure of the goodness of the scheme) for the cases k=2 and k=n. the lower bounds match the pixel expansion of the schemes provided in these two cases, thus proving that our schemes are optimal with respect to the pixel expansion. we also provide an upper bound on the contrast of (k,n)-threshold schemes and (2,n)-threshold schemes with optimal contrast.