waashk/dblp huggingface dataset:
efficiently computing succinct trade-off curves. trade-off (aka pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in papadimitriou and yannakakis [on the approximability of trade-offs and optimal access of web sources, in: proc. 41st ieee symp. on foundations of computer science, 2000] that there exist polynomial size ε approximations for any ε > 0, and that under certain general conditions, such approximate ε-pareto curves can be constructed in polynomial time. in this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. in the case of two objectives, we present a general algorithm that efficiently computes an ε-pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. if we relax ε to any ε' > ε, then we can efficiently construct an ε'-curve that uses no more points than the smallest ε-curve. with three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger ε value. we present an algorithm that is 4-competitive for any ε' > (1 + ε)2 - 1. we explore the problem in high dimensions and give hardness proofs showing that (unless p=np) no constant approximation factor can be achieved efficiently even if we relax ε by an arbitrary constant.
on the descriptional complexity of some rewriting mechanisms regulated by context conditions. we improve the upper bounds of certain descriptional complexity measures of two types of rewriting mechanisms regulated by context conditions. we prove that scattered context grammars having two context sensing productions and five nonterminals are sufficient to generate all recursively enumerable languages and we also show that the same power can be reached by simple semi-conditional grammars having 10 conditional productions with conditions of the length two or eight conditional productions with conditions of length three. the results are based on the common idea of using the so called geffert normal forms for phrase structure grammars.
random 2-sat: results and problems. in the random 2-sat problem, we are given a set c of m disjunctions of two literals chosen at random within the ( 2n2 ) pairs of distinct literals coming from n logical variables. the basic problem is to /nd out for which values of the ratio _=m=n the disjunctions in c are almost surely simultaneously satisfiable (or almost surely not simultaneously satisfiable) as n tends to infinity. the purpose of this paper is to review the main steps in the solution of this problem, starting with the location of the asymptotic critical ratio around 8 years ago and ending with the recent almost complete solution due to bollob4as et al. thus, this paper is not a review in the usual sense of the word, i.e., it does not include all the known results about random 2-sat. we will also make a few comments concerning the behaviour of the number of satisfying assignments of random instances of 2-sat below the critical ratio, a problem relevant to theoretical physics.
the first order definability of graphs with separators via the ehrenfeucht game. we say that a first order formula φ defines a graph g if φ is true on g and false on every grap g' non-isomorphic with g. let d(g) be the minimum quantifier rank of a such formula. we prove that, if g is a tree of bounded degree or a hamiltonian (equivalently, 2-connected) outerplanar graph, then d(g) = o (log n), where n denotes the order of g. this bound is optimal up to a constant factor. if h is a constant, for connected graphs with no minor kh and degree o (√nlog n), we prove the bound d(g) = o (√n). this result applies to planar graphs and, more generally, to graphs of bounded genus.our proof techniques are based on the characterization of the quantifier rank as the length of the ehrenfeucht game on non-isomorphic graphs. we use the separator theorems to design a winning strategy for spoiler in this game.
kolmogorov complexity conditional to large integers. the main result of the paper states that the following two values coincide for any string x: limsupnk(x|n) and the minimum length of a program that producesx given all sufficiently large integers. previously it was known that the latter value is equal to the kolmogorov complexity of x relativized by 0. (all equalities hold up to a constant additive term.)
independent minimum length programs to translate between given strings. a string p is called a program to compute y given x if u(p,x)=y, where u denotes universal programming language. kolmogorov complexity k(y|x) of y relative to x is defined as minimum length of a program to compute y given x. let k(x) denote k(x|emptystring) (kolmogorov complexity of x) and let i(x:y)=k(x)+k(y)-k(x,y) (the amount of mutual information in x,y). in the present paper, we answer in the negative the following question posed in bennett et al., ieee trans. inform. theory 44 (4) (1998) 1407-1423. is it true that for any strings x,y there are independent minimum length programs p,q to translate between x,y, that is, is it true that for any x,y there are p,q such that u(p,x)=y, u(q,y)=x, the length of p is k(y|x), the length of q is k(x|y), and i(p:q)=0 (where the last three equalities hold up to an additive o(log(k(x|y)+k(y|x))) term)?
a lower bound on the competitivity of memoryless algorithms for a generalization of the cnn problem. we consider the cnn problem in arbitrary dimension, and over any metric space containing the integers. we prove that, in every dimension at least 2, no memoryless online algorithm can achieve a constant competitive ratio, under a weak symmetry constraint on the algorithm. this generalizes in several aspects the lower bounds obtained by koutsoupias and taylor [the cnn problem and other k-server variants, theoret. comput. sci. 324 (2004) 347-359] for the original problem. the proof consists in the analysis of carefully selected random walks, which appear naturally in the framework of memoryless algorithms.
a boundary result on enhanced time-varying distributed h systems with parallel computations. enhanced time-varying distributed h systems (etvdh systems) are a variant of time-varying distributed h systems (tvdh systems), which is a well-known theoretical model of dna computing based on splicing. we show that etvdh systems with 2 components, i.e., having two sets of rules which act periodically, may generate all recursively enumerable languages by simulating type-0 grammars. we also present a new approach to control the computations that can be used in other models of dna computing based on splicing.
on the computational complexity of 2-interval pattern matching problems. the focus of this paper is on the computational complexity of pattern matching problems over set of 2-intervals. these problems occur in the context of molecular biology when a structured pattern, i.e., a rna secondary structure given in the form of a 2-interval pattern, has to be found in a sequence database. we show that finding a 2-interval pattern in a set of 2-intervals is a np-complete problem even if no 2-interval of the pattern precedes the other, but can be solved in polynomial time for several interesting special cases. in particular, it is shown that the pseudo-knot free rna secondary structure case is polynomial time solvable in our 2-interval formalism. also, we investigate the computational complexity of finding the longest 2-interval pattern in a set of 2-intervals and prove several np-completeness results as well as polynomial time solvable special cases.
entailment systems for stably locally compact locales. the category scfru of stably continuous frames and preframe homomorphisms (preserving finite meets and directed joins) is dual to the karoubi envelope of a category ent whose objects are sets and whose morphisms x → y are upper closed relations between the finite powersets fx and fy. composition of these morphisms is the "cut composition" of jung et al. that interfaces disjunction in the codomains with conjunctions in the domains, and thereby relates to their multi-lingual sequent calculus. thus stably locally compact locales are represented by "entailment systems" (x, ⊢) in which ⊢, a generalization of entailment relations, is idempotent for cut composition. some constructions on stably locally compact locales are represented in terms of entailment systems: products, duality and powerlocales. relational converse provides ent with an involution, and this gives a simple treatment of the duality of stably locally compact locales. if a and b are stably continuous frames, then the internal preframe hom aψb is isomorphic to ã ⊗ b where ã is the hofmann-lawson dual. for a stably locally compact locale x, the lower powerlocale of x is shown to be the dual of the upper powerlocale of the dual of x.
a universal characterization of the double powerlocale. the double powerlocale p(x) (found by composing, in either order, the upper and lower powerlocale constructions pu and pl) is shown to be isomolphic in [locop, set] to the double exponential ssx where s is the sierpinski locale. further pu(x) and pl(x) are shown to be the subobjects of p(x) comprising, respectively, the meet semilattice and join semilattice homomorphisms. a key lemma shows that, for any locales x and y, natural transformations from sx (the presheaf loc(_ × x, s)) to sy (i.e. loc(_ × y, s)) are equivalent to dcpo morphisms (scott continuous maps) from the flame ωx to ωy. it is also shown that sx has a localic reflection in [locop, set] whose frame is the scott topology on ωx.the reasoning is constructive in the sense of topos validity.
a note on the circuit complexity of pp. in this short note, we show that for any integer k, there are languages in the complexity class pp that do not have boolean circuits of size nk.
equational rules for rewriting logic. in addition to equations and rules, we introduce equational rules that are oriented while having an equational interpretation. correspondence between operational behavior and intended semantics is guaranteed by a property of coherence, which can be checked by examination of critical pairs and linearity conditions. we present applications of this theory to three examples where the rewrite relation is interpreted, respectively, as equality, transition and deduction.
a constructive theory of point-set nearness. an axiomatic constructive development of the theory of nearness and apartness of a point and a set is introduced as a setting for topology.
on the number of hexagonal polyominoes. a combination of the refined finite lattice method and transfer matrices allows a radical increase in the computer enumeration of polyominoes on the hexagonal lattice (equivalently, site clusters on the triangular lattice), pn with n hexagons. we obtain pn for n ≤ 35. we prove that pn=τn+o(n), obtain the bounds 4.8049 ≤ τ ≤ 5.9047, and estimate that τ=5.1831478(17). finally, we provide compelling numerical evidence that the generating function σ pnzn ≈ a(z)log(1-τz), for z → (1/τ)- with a(z) holomorphic in a cut plane, estimate a(1/τ) and predict the sub-leading asymptotic behaviour, identifying a non-analytic correction-to-scaling term with exponent δ=3/2. on the basis of universality and previous numerical work we argue that the mean-square radius of gyration 〈rg2〉n of polyominoes of size n grows as n2v, with v = 0.64115(5).
efficiency of asynchronous systems, read arcs, and the mutex-problem. two solutions to the mutex-problem are compared w.r.t. their temporal efficiency. for this, a formerly developed efficiency testing for asynchronous systems is adapted to petri nets with so-called read arcs. furthermore, a compositional semantics for fair behaviour (in the sense of the progress assumption) is presented. on the one hand, this semantics is related to efficiency testing. on the other hand, it is used to specify formally what a solution to the mutex-problem is. it is shown that one of our solutions indeed satisfies this specification and that ordinary nets without read arcs cannot solve the mutex-problem.
probability theory for the brier game. the usual theory of prediction with expert advice does not differentiate between good and bad "experts": its typical results only assert that it is possible to efficiently merge not too extensivepools of experts, no matter how good or how bad they are. on the other hand, it is natural toexpect that good experts' predictions will in some way agree with the actual outcomes (e.g., theywill be accurate on the average). in this paper we show that, in the case of the brier predictiongame (also known as the square-loss game), the predictions of a good (in some weak andnatural sense) expert must satisfy the law of large numbers (both strong and weak) and the lawof the iterated logarithm; we also show that two good experts' predictions must be in asymtoticagreement. to help the reader's intuition, we give a kolmogorov-complexity interpretation ofour results. finally, we briefly discuss possible extensions of our results to more general games;the limit theorems for sequences of events in conventional probability theory correspond to thelog-loss game.
information distance and conditional complexities. c.h. bennett, p. g&aacute;cs, m. li, p.m.b. vit&aacute;nyi, and w.h. zurek have defined information distance between two strings x, y as d(x,y)= maxk (x|y), where" k(x|y) is conditional kolmogorov complexity. it is easy to see that for any string x and any integer n there is a string y such that d(x,y)=n+o(1). in this paper we prove the following (stronger) result: for any n and for any string x such that k(x)&ge;2n+o(1) there exists a string y such that both k(x|y) and k(y|x) are equal to n+o(1).
does snooping help? one of the most efficient way of improving the performance of learning algorithms is "snooping", i.e. using some information about the data to be predicted for choosing the parameters of the learning algorithm or the learning algorithm itself. allowing different degrees of snooping makes it possible to attain a better performance lossp(x) of a prediction strategy p on the given data set x. we study the "snooping curves" lx()=infk(p)lossp(x), where k(p) is the kolmogorov complexity of the prediction strategy p. we prove that every non-increasing function can be approximated with arbitrary precision by some snooping function lx. our framework is that of on-line prediction; for simplicity we assume that sequences x are binary.
induction in the timed interval calculus. the timed interval calculus, a timed-trace formalism based on set theory, is introduced. it is extended with an induction law and a unit for concatenation, which facilitates the proof of properties over trace histories. the effectiveness of the extended timed interval calculus is demonstrated via a benchmark case study, the mine pump. specifically, a safety property relating to the operation of a mine shaft is proved, based on an implementation of the mine pump and assumptions about the environment of the mine.
a property of random context picture grammars. we use random context picture grammers to generate pictures through successive refinement. the productions of such a grammar are context free, but their application is regulated by context randomly distributed in the developing picture. grammars using this relatively weak context often succeed where context-free grammars fail, e.g., in generating the typical iteration sequence of the sierpiński carpet. on the other hand, it proved possible to develop iteration theorems for three subclasses of these grammars; finding necessary conditions is problematic in the case of most models of context-free picture grammars with context-sensing ability, since they consider a variable and its context as a connected unit.we present a property of all picture sets generated with random context picture grammers, and then construct a picture set that does not belong to this class.
the customizable fault/error model for dependable distributed systems. dependability is a qualitative term referring to a system's ability to meet its service requirements in the presence of faults. the types and number of faults covered by a system play a primary role in determining the level of dependability which that system can potentially provide. given the variety and multiplicity of fault types, to simplify the design process, the system algorithm design often focuses on specific fault types, resulting in either over-optimistic (all fault permanent) or over-pessimistic (all faults malicious) dependable system designs.a more practical and realistic approach is to recognize that faults of varied severity levels and of differing occurrence probabilities may appear as combinations rather than the assumed single fault type occurrences. the ability to allow the user to select/customize a particular combination of fault types of varied severity characterizes the proposed customizable fault/error model (cfem). the cfem organizes diverse fault categories into a cohesive framework by classifying faults according to the effect they have on the required system services rather than by targeting the source of the fault condition. in this paper, we develop (a) the complete framework for the cfem fault classification, (b) the voting functions applicable under the cfem, and (c) the fundamental distributed services of consensus and convergence under the cfem on which dependable distributed functionality can be supported.
monadic second-order logic on tree-like structures. an operation m* which constructs from a given structure m a tree-like structure whose domain consists of the finite sequences of elements of m is considered. a notion of automata running on such tree-like structures is defined. it is shown that automata of this kind characterise expressive power of monadic second-order logic (msol) over tree-like structures. using this characterisation it is proved that msol theory of a tree-like structure is effectively reducible to that of the original structure. as another application of the characterisation it is shown that msol on trees of arbitrary degree is equivalent to first-order logic extended with unary least fixpoint operator.
algorithms for computing lengths of chains in integral partition lattices. let pl,n denote the partition lattice of l with n parts, ordered by hardy-littlewood-polya majorization. for any two comparable elements x and y of pl,n, we denote by m(x, y), m(x, y), f(x, y), and f(x, y), respectively, the sizes of four typical chains between x and y: the longest chain, the shortest chain, the lexicographic chain, and the counter-lexicographic chain. the covers u=(u1..., un) ≻ v =(v1...,vn) in pl,n , are of two types: n-shift (nearby shift) where vi=ui- 1, vi+1 = ui+1 + 1 for some i; and d-shift (distant shift) where ui - 1 = vi = vi+1 =...= vj = uj + 1 for some i and j. an n-shift (a d-shift) is pure if it is not a d-shift (an n-shift). we develop linear algorithms for calculating m(x, y), m(x, y), f(x, y), and f(x, y), using the leftmost pure n-shift first search, the rightmost pure d-shift first search, the leftmost n-shift first search, and the rightmost d-shift first search, respectively. those algorithms have significant applications in complexity analysis of biological sequences.
a comparison of two approaches to pseudorandomness. the concept of pseudorandomness plays an important role in cryptography. in this note, we contrast the notions of complexity-theoretic pseudorandom strings (from algorithmic information theory) and pseudorandom strings (from cryptography). for example, we show that we can easily distinguish a complexity-theoretic pseudorandom ensemble from the uniform ensemble. both notions of pseudorandom strings are uniformly unpredictable; in contrast with pseudorandom strings, complexity-theoretic pseudorandom strings are not polynomial-time unpredictable.
on the complexity of finding emerging patterns. emerging patterns have been studied as a useful type of pattern for the diagnosis and understanding of diseases based on the analysis of gene expression profiles. they are useful for capturing interactions among genes (or other biological entities), for capturing signature patterns for disease subtypes, and deriving potential disease treatment plans, etc. in this paper we study the complexity of finding emerging patterns (with the highest frequency). we first show that the problem is max snp-hard. this implies that polynomial time approximation schemes do not exist for the problem unless p = np. we then prove that for any constant δ < 1, the emerging pattern problem cannot be approximated within ratio 2logδn in polynomial time unless np ⊆ dtime[2polylog n], where n is the number of positions in a pattern.
sequential sampling techniques for algorithmic learning theory. a sequential sampling algorithm or adaptive sampling algorithm is a sampling algorithm that obtains instances sequentially one by one and determines from these instances whether it has already seen enough number of instances for achieving a given task. in this paper, we present two typical sequential sampling algorithms. by using simple estimation problems for our example, we explain when and how to use such sampling algorithms for designing adaptive learning algorithms.
function-dependent teams in eco-grammar systems. in this paper, we investigate simple eco-grammar systems with n agents. the number of agents which are active at each derivation step depends on the number of steps which have already been carried out since the beginning of the development. this dependency is expressed by a function f. for each pair of n and f, corresponding language families are defined. these families are compared with each other according to the different values of n and f.
pspace has constant-round quantum interactive proof systems. in this paper we introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. it is proved that every language in pspace has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. it follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.
a new regular grammar pattern matching algorithm. this paper presents a boyer-moore type algorithm for regular grammar pattern matching, answering a variant of an open problem posed by aho (pattern matching in strings, academic press, new york, 1980, p. 342). the new algorithm handles patterns specified by regular (left linear) grammars--a generalization of the boyer-moore (single keyword) and commentz-walter (multiple keyword) algorithms.like the boyer-moore and commentz-walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. the precomputation functions are derived, and it is shown that they can be obtained from commentz-walter's d1 and d2 shift functions.in most cases, the boyer-moore (respectively, commentz-walter) algorithm has greatly outperformed the knuth-morris-pratt (respectively, aho-corasick) algorithm. in practice, an earlier version of the algorithm presented in this paper also frequently outperforms the regular grammar generalization of the aho-corasick algorithm.