waashk/dblp huggingface dataset:
skew and infinitary formal power series. we investigate finite-state systems with weights. departing from the classical theory, in this paper the weight of an action does not only depend on the state of the system, but also on the time when it is executed; this reflects the usual human evaluation practices in which later events are considered less urgent and carry less weight than close events. we first characterize the terminating behaviors of such systems in terms of rational formal power series. this generalizes a classical result of schützenberger. secondly, we deal with nonterminating behaviors and their weights. this includes an extension of the büchi-acceptance condition from finite automata to weighted automata and provides a characterization of these nonterminating behaviors in terms of ω-rational formal power series. this generalizes a classical theorem of büchi.
weighted tree automata and weighted logics. we define a weighted monadic second order logic for trees where the weights are taken from a commutative semiring. we prove that a restricted version of this logic characterizes the class of formal tree series which are accepted by weighted bottom-up finite state tree automata. the restriction on the logic can be dropped if additionally the semiring is locally finite. this generalizes corresponding classical results of thatcher, wright, and doner for tree languages and it extends recent results of droste and gastin [weighted automata and weighted logics, in: automata, languages and programrning--32nd international colloquium, icalp 2005, lisbon, portugal, 2005, proceedings, lecture notes in computer science, vol. 3580, springer, berlin, 2005, pp. 513-525, full version in theoretical computer science, to appear.] from formal power series on words to formal tree series.
object grammars and bijections. a new systematic approach for the specification of bijections between sets of combinatorial objects is presented. it is based on the notion of object grammars. object grammars give recursive descriptions of objects and generalize context-free grammars. the study of a particular substitution in these object grammars confirms once more the key role of dyck words in the domain of enumerative and bijective combinatorics.
linear-time computation of local periods. we present a linear-time algorithm for computing all local periods of a given word. this subsumes (but is substantially more powerful than) the computation of the (global) period of the word and on the other hand, the computation of a critical factorization, implied by the critical factorization theorem.
upper bounds on the satisfiability threshold. we present a survey of upper bounds which has been established up to now on the satisfiability threshold of random k-sat formulae. the ideas which led to these bounds and the techniques used to obtain them, are explained. a companion paper in this volume present a survey of the lower bounds.
on the support of graph lie algebras. we deal with the support of graph lie algebras and we characterize the set of independence alphabets for which the noncommutative result can naturally be extended. we also provide an algorithm which decides if an independence alphabet fulfills the preceding condition.
from object grammars to eco systems. in this paper we make a comparison between two methods for the enumeration of combinatorial objects, namely the eco method and object grammars, both based on a recursive description for the examined class of objects. in particular, we study the problem of passing from an object grammar to an "equivalent" eco system. first, we solve this problem for any unidimensional, unambiguous, and complete object grammar, with any linear parameter. then we treat the more complex cases of q-linear parameters, and of multidimensional object grammars, giving some explanatory examples. in particular, we determine a new eco system for the class of directed convex polyominoes.
dominance constraints with boolean connectives: a model-eliminative treatment. dominance constraints are a language of tree descriptions. tree descriptions are widely used in computational linguistics for talking and reasoning about trees. while previous research has focused on the conjunctive fragment, we now extend the account to all boolean connectives and propose a new formalism that combines dominance constraints with a feature tree logic.although the satisfiability problem in the conjunctive fragment is known to be np-complete, we have previously demonstrated that it can be addressed very effectively by constraint propagation: we developed an encoding that transforms a dominance constraint into a constraint satisfaction problem on finite sets solvable by constraint programming. we present a generalization of this encoding for our more expressive formalism, and prove soundness and completeness. our main contribution is a treatment of disjunction suitable for constraint propagation.
could any graph be turned into a small-world? in addition to statistical graph properties (diameter, degree, clustering, etc.), kleinberg [the small-world phenomenon: an algorithmic perspective, in: proc. 32nd acm symp. on theory of computing (stoc), 2000, pp. 163-170] showed that a small-world can also be seen as a graph in which the routing task can be efficiently and easily done in spite of a lack of global knowledge. more precisely, in a lattice network augmented by extra random edges (but not chosen uniformly), a short path of polylogarithmic expected length can be found using a greedy algorithm with a local knowledge of the nodes. we call such a graph a navigable small-world since short paths exist and can be followed with partial knowledge of the network. in this paper, we show that a wide class of graphs can be augmented into navigable small-worlds.
a geometric approach to leveraging weak learners. adaboost is a popular and effective leveraging procedure for improving the hypotheses generated by weak learning algorithms. adaboost and many other leveraging algorithms can be viewed as performing a constrained gradient descent over a potential function. at each iteration the distribution over the sample given to the weak learner is proportional to the direction of steepest descent. we introduce a new leveraging algorithm based on a natural potential function. for this potential function, the direction of steepest descent can have negative components. therefore, we provide two techniques for obtaining suitable distributions from these directions of steepest descent. the resulting algorithms have bounds that are incomparable to adaboost's. the analysis suggests that our algorithm is likely to perform better than adaboost on noisy data and with weak learners returning low confidence hypotheses. modest experiments confirm that our algorithm can perform better than adaboost in these situations.
open and closed scopes for constrained genericity. constrained genericity is an extension of parametric polymorphism, that allows type parameters in polymorphic procedures to be constrained to have certain operations defined over them. it is realized in the ada and haskell programming languages, as exemplified by type classes in haskell. type classes only allow a single global scope for instances of type classes. this article introduces a type system and a semantics that allows both dynamic and static scoping of such operations to be mixed in a program. applications include overcoming scoping problems with constrained genericity, enabling program optimizations, and programming with dynamic data structures. type classes with "open" scope obey the usual semantics for haskell type classes, based on call-site "type dictionaries". type classes with "closed" scope use run-time type descriptions to dispatch to instances. the type system to support this combines operator kinds, refinement kinds and singleton kinds. the system is extended to allow overlapping specialized instance types, in order to support specialized representations for data structures (for example, arrays of integers, arrays of floats and arrays of boxed values). this extension requires the combination of both type dictionaries and run-time type information for type class dispatching.
a combinatorial error bound for t-point-based sampling. the method of two-point-based sampling using orthogonal arrays (inform. process. lett. 60 (1996) 91) is extended to consider t-wise independent sampling using orthogonal arrays of higher strength t. using combinatorial considerations, an error bound is calculated which agrees with the previously known result when t = 2, and has the advantage of exponentially decreasing in t. the result is shown to be strictly sharper than that arising from the generalized chebyshev inequality. finally, the behavior of the family of error bounds we obtain for increasing values of t is analyzed.
rna secondary structure comparison: exact analysis of the zhang-shasha tree edit algorithm. we are interested in rna secondary structure comparison, using an approach which consists to represent these structures by labeled ordered trees. following the problem considered, this tree representation can be rough (considering only the structural patterns), or refined until an exact coding of the structure is obtained. after some preliminary definitions and the description of the zhang-shasha (siam j. comput. 18 (6) (1989) 1245) tree edit algorithm, which is on the one hand the reference when dealing with ordered labeled trees comparison, and on the other hand the starting point of our work, this article will present an exact analysis of its complexity. the purpose of this work is also to lead us to a better comprehension of the parameters of this algorithm, in order to be able to modify it more easily without changing its time complexity to take into account biological constraints that occur when comparing rna secondary structures.
a halfliar's game. in ulam's game paul tries to find one of n possibilities with q yes-no questions, while responder carole is allowed to lie a fixed number k of times. we consider an asymmetric variant in which carole must say yes when that is the correct answer (whence the halflie). we show that this variation allows paul to distinguish between roughly 2k as many possibilities as in ulam's game.
mining for empty spaces in large data sets. many data mining approaches focus on the discovery of similar (and frequent) data values in large data sets. we present an alternative, but complementary approach in which we search for empty regions in the data. we consider the problem of finding all maximal empty rectangles in large, two-dimensional data sets. we introduce a novel, scalable algorithm for finding all such rectangles. the algorithm achieves this with a single scan over a sorted data set and requires only a small bounded amount of memory. we extend the algorithm to find all maximal empty hyper-rectangles in a multi-dimensional space. we consider the complexity of this search problem and present new bounds on the number of maximal empty hyper-rectangles. we briefly overview experimental results obtained by applying our algorithm to real and synthetic data sets and describe one application of empty-space knowledge to query optimization.
polynomial time algorithms for three-label point labeling. in this paper, we present an o(n2 log n) time solution for the following multi-label map labeling problem: given a set s of n distinct sites in the plane, place at each site a triple of uniform squares of maximum possible size such that all the squares are axis-parallel and a site is on the boundaries of its three labeling squares. we also study the problem under the discrete model, i.e., a site must be at the corners of its three label squares. we obtain an optimal θ(n log n) time algorithm for the latter problem.
on representations of positive integers in the fibonacci base. we exhibit and study various regularity properties of the sequence (r(n))n ≥ 1 which counts the number of different representations of the positive integer n in the fibonacci numeration system. the regularity properties in question are observed by representing the sequence as a two-dimensional array consisting of an infinite number of rows l1, l2, l3 .... where each lk contains fk-1 (the k - 1st fibonacci number) entries of the sequence (r(n)). we give a purely combinatorial recursive algorithm for generating each row lk from previous rows lj with j < k. we then show that for each positive integer m, and for all k ≥ 2m, the number of occurrences of m in lk is a constant rk(m) depending only on m. the function rk(m) has many interesting number theoretic properties and is intimately connected to the euler φ-function.
approximation schemes for scheduling and covering on unrelated machines. we examine the problem of assigning n independent jobs to m unrelated parallel machines, so that each job is processed without interruption on one of the machines, and at any time, every machine processes at most one job. we focus on the case where m is a fixed constant, and present a new rounding approach that yields approximation schemes for multi-objective minimum makespan scheduling with a fixed number of linear cost constraints. the same approach gives approximation schemes for covering problems like maximizing the minimum load on any machine, and for assigning specific or equal loads to the machines.
exponentiation using canonical recoding. the canonical bit recoding technique can be used to reduce the average number of multiplications required to compute $x^e$ provided that $x^{-1}$ is supplied along with $x$. we model the generation of the digits of the canonical recoding $d$ of an $n$-bit long exponent $e$ as a markov chain, and show that binary, quaternary, and octal methods applied to $d$ require $\frac{4}{3}\,n$, $\frac{4}{3}\,n$, and $ \frac{23}{18}\,n $ multiplications, compared to $\frac{3}{2} \, n$, $\frac{11}{8} \, n$, and $\frac{31}{24}n$ required by these methods applied to $e$. we show that in general the canonically recoded $m$-ary method for constant $m$ requires fewer multiplications than the standard $m$-ary method. however, when $m$ is picked optimally for each method for a given $n$, then the average number of multiplications required by the standard method is fewer than those required by the recoded version.
formal systems for gene assembly in ciliates. dna processing in ciliates, a very ancient group of organisms, is among the most sophisticated dna processing in living organisms. it has a quite clear computational structure and even uses explicitly the linked list data structure! particularly interesting from the computational point of view is the process of gene assembly from its micronuclear to its macronuclear form. we investigate here the string rewriting and the graph rewriting models of this process, involving three molecular operations, which together form a universal set of operations in the sense that they can assembly any macronuclear gene from its micronuclear form. in particular we prove that although the graph rewriting system is more "abstract" than the string rewriting system, no "essential information" is lost, in the sense that one can translate assembly strategies from one system into the other.
on the sequential access theorem and deque conjecture for splay trees. we give a new, simple proof for the sequential access theorem for splay trees. for an n-node splay tree, our bound on the number of rotations is 4.5n, with a smaller constant than the bound of 10.8n concluded by tarjan. we extend our proof to prove the deque conjecture for output-restricted deques. our proofs provide additional insights into the workings of splay trees.
gene assembly through cyclic graph decomposition. we present in this paper a graph theoretical model of gene assembly, where (segments of) genes are distributed over a set of circular molecules. this model is motivated by the process of gene assembly in ciliates, but it is more general. in this model a set of circular dna molecules is represented by a bicoloured and labelled graph consisting of cyclic graphs, and the recombination takes place in two stages: first, by folding *p with respect to a set p of pairs of vertices of the graph (representing pointers in the micronuclear genes of the ciliate), and secondly, by unfolding the so obtained graph to p with respect to vertices of higher valency. the final graph p is again a set of bicoloured cyclic graphs, where the genes are present as maximal monochromatic paths. thus, the process of gene assembly corresponds to the dynamic process of changing cyclic graph decompositions. we show that the operation is well behaved in many respects, and that there is a sequence of pointer sets p1,...,pm consisting of one or two pairs such that p=(((p1)p2)pm) and each intermediate step i=(((p1)p2)pi) is intracyclic, that is, the segments of a gene that lie in the same connected component of i, will lie in the same connected component of the successor graph i+1.
the bounded eight-vertex model. the bounded version of the eight-vertex model of statistical mechanics is investigated. we study square, diamond and general finite domains on the square lattice and give exact characterizations to legal boundary conditions and number of fill-ins. the sets of legal configurations with a given boundary turn out always to have the graph topology of a hypercube with a particularly simple edge action. this enables a simple probabilistic description of the configurations as well as an efficient configuration generation using a cellular automaton. finally, by invoking height functions we study restricted edge action which leads to ice-model as well as to lesser know vertex models, some subsets of the eight-vertex model, some not.
two undecidability results for chain code picture languages. it is undecidable whether or not two 1-retreat-bounded regular languages describe exactly the same set of pictures or they describe a picture in common.
sparse topologies with small spectrum size. one of the fundamental properties of a graph is the number of distinct eigenvalues of its adjacency or laplace matrix. determining this number is of theoretical interest as well as of practical impact. sparse graphs with small spectra exhibit excellent structural properties and can act as interconnection topologies. in this paper, for any n we present graphs, for which the product of their vertex degree and the number of different eigenvalues is small. it is known that load balancing can be performed on such graphs in a small number of steps.
on groups whose word problem is solved by a~counter automaton. we prove that a group g has a word problem that is accepted by a deterministic counter automaton with a weak inverse property if and only if g is virtually abelian. we extend this result to larger classes of groups by considering a generalization of finite state automata, counter automata and pushdown automata. natural corollaries of our general result include a restricted version of herbst's classification of groups for which the word problem is a one counter language and a new classification of automata that accept context-free word problems.
forbidding-enforcing systems. this paper presents a model of molecular computing that is based on two kinds of "boundary conditions": forbidding and enforcing. forbidding conditions require that a contradictory (or conflicting) group of components (molecules) may not be present in a (molecular) system, as otherwise the system will "die". an enforcing condition requires that if a certain group of components (molecules) is present in a system, then eventually other components will be present in the system -- hence such an enforcing condition models a molecular reaction. thus the evolution of a system is determined by the enforcing conditions, but it is constraint by the forbidding conditions. such forbidding-enforcing systems (fe systems) are investigated in this paper in the framework of strings--i.e., molecules are represented by strings. each fe system defines a family of languages (rather than just one language, which is standard in formal language theory)--each language in this family presents a set of molecules that satisfy both forbidding and enforcing constraints. in this paper we investigate basic computational properties of fe systems operating on strings.
scale-free aggregation in sensor networks. sensor networks are distributed data collection systems, frequently used for monitoring environments in which "nearby" data have a high degree of correlation. this induces opportunities for data aggregation, that are crucial given the severe energy constraints of the sensors. thus, it is very desirable to take advantage of data correlations in order to avoid transmitting redundancy. in our model, we formalize a notion of correlation, that can vary according to a parameter k. then we relate the expected collision time of "nearby" walks on the grid to the optimum cost of scale-free aggregation.we also propose a very simple randomized algorithm for routing information on a grid of sensors that satisfies the appropriate collision time condition. thus, we prove that this simple scheme is a constant factor approximation (in expectation) to the optimum aggregation tree simultaneously for all correlation parameters k. the key contribution in our randomized analysis is to bound the average expected collision time of non-homogeneous random walks on the grid, i.e. the next hop probability depends on the current position.
towards optimal lower bounds for clique and chromatic number. it was previously known that neither max clique nor min chromatic number can be approximated in polynomial time within n1-ε, for any constant ε > 0, unless np = zpp. in this paper, we extend the reductions used to prove these results and combine the extended reductions with a recent result of samorodnitsky and trevisan to show that unless np ⊆ zptime(2o(log n(log log n)3/2)), neither max clique nor min chromatic number can be approximated in polynomial time within n1-ε(n) where ε ∈ o((log log n)-1/2). since there exists polynomial time algorithms approximating both problems within n1-ε(n) where ε(n) ∈ ω(log log n/log n), our result shows that the best possible ratio we can hope for is of the form n1-o(1), for some--yet unknown--value of o(1) between o((log log n)-1/2) and ω(log log n/log n).
inapproximability results for equations over finite groups. an equation over a finite group g is an expression of form w1w2...wk = 1g, where each wi is a variable, an inverted variable, or a constant from g; such an equation is satisfiable if there is a setting of the variables to values in g so that the equality is realized. we study the problem of simultaneously satisfying a family of equations over a finite group g and show that it is np-hard to approximate the number of simultaneously satisfiable equations to within |g|-ε for any ε > 0. this generalizes results of håstad (j. acm 48 (4) (2001) 798), who established similar bounds under the added condition that the group g is abelian.
complexity of learning in artificial neural networks. some basic issues in the statistical mechanics of learning from examples are reviewed. the approach of statistical physics is contrasted with the analysis of learning within the framework of mathematical statistics and the question of the algorithmic complexity of explicit learning prescriptions is addressed. even in very simple learning scenarios, the typical properties of which can be analyzed in great quantitative detail by methods from statistical mechanics, the determination of a suitable hypothesis approximating the target rule may be an np-complete problem. some special learning setups are suggested as model systems for the comparison between the approaches of statistical mechanics and computer science to the theory of computationally hard problems.