waashk/dblp huggingface dataset:
asymptotic orbits of primitive substitutions. a primitive, aperiodic substitution on d letters has at most d2 asymptotic orbits; this bound is sharp. since asymptotic arc components in tiling spaces associated with substitutions are in 1-1 correspondence with asymptotic words, this provides a bound for those as well.
minimal change list for lucas strings and some graph theoretic consequences. we give a minimal change list for the set of order p length-n lucas strings, i.e., the set of length-n binary strings with no p consecutive 1's nor a 1l prefix and a 1m suffix with l+m ≥ p. the construction of this list proves also that the order p n-dimensional lucas cube has a hamiltonian path if and only if n is not a multiple of p + 1, and its second power always has a hamiltonian path.
reachability problems for sequential dynamical systems with threshold functions. a sequential dynamical system (sds) over a domain d is a triple (g, f, π), where (i) g(v,e) is an undirected graph with n nodes with each node having a state value from d, (ii) f = {f1, f2,..., fn} is a set of local transition functions with fi denoting the local transition function associated with node vi and (iii) π is a permutation of (i.e., a total order on) the nodes in v. a single sds transition is obtained by updating the states of the nodes in v by evaluating the function associated with each of them in the order given by π.we consider reachability problems for sdss with restricted local transition functions. our main intractability results show that the reachability problems for sdss are pspace-complete when either of the following restrictions hold: (i) f consists of both simple-threshold-functions and simple-inverted-threshold functions, or (ii) f consists only of threshold-functions that use weights in an asymmetric manner. moreover, the results hold even for sdss whose underlying graphs have bounded node degree and bounded pathwidth. our lower bound results also extend to reachability problems for hopfield networks and communicating finite state machines.on the positive side, we show that when f consists only of threshold functions that use weights in a symmetric manner, reachability problems can be solved efficiently provided all the weights are strictly positive and the ratio of the largest to the smallest weight is bounded by a polynomial function of the number of nodes.
gossiping in chordal rings under the line model. this paper is devoted to the gossip (or all-to-all) problem in the chordal ring under the one-port line model. the line model assumes long distance calls between non-neighboring processors. in this sense, the line model is strongly related to circuit-switched networks, wormhole routing, optical networks supporting wavelength division multiplexing, atm switching, and networks supporting connected mode routing protocols. since the chordal rings are competitors of networks as meshes or tori because of their short diameter and bounded degree, it is of interest to ask whether they can support intensive communications (typically all-to-all) as efficiently as these networks. we propose polynomial algorithms to derive optimal or near-optimal gossip protocols in the chordal ring.
on page migration and other relaxed task systems. this paper is concerned with the page migration (or file migration) problem (black and sleator, technical report cmu-cs-89-201, department of computer science, carnegie-mellon university, 1989) as part of a large class of on-line problems. the page migration problem deals with the management of pages residing in a network of processors. in the classical problem there is only one copy of each page which is accessed by different processors over time. the page is allowed to be migrated between processors. however a migration incurs higher communication cost than an access (proportionally to the page size). the problem is that of deciding when and where to migrate the page in order to lower access costs. a more general setting is the k-page migration problem where we wish to maintain k copies of the page. the page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. we deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (borodin et al., j. acm 39(4) (1992) 745-763). given a c-competitive algorithm for a task system we show how to obtain a deterministic o(c2) and randomized o(c) competitive algorithms for the corresponding relaxed task system. the result implies deterministic algorithms for k-page migration by using k-server (manasse et al., j. algorithms 11(2) (1990) 208-230) algorithms, and for network leasing by using generalized steiner tree algorithms (awerbuch et al., proc 7th ann. acm-siam symp. on discrete algorithms, january 1996, pp. 68-74), as well as providing solutions for natural generalizations of other problems (e.g. storage rearrangement (fiat et al., proc. 36th ann. ieee symp. on foundations of computer science, october 1995, pp. 392-403)). we further study some special cases of the k-page migration problem and get optimal deterministic algorithms. for the classical page migration problem we present a deterministic algorithm that achieves a competitive ratio of ~ 4:086, improving upon the previously best competitive ratio of 7 (awerbuch et al., proc. 25th acm symp. on theory of computing, may 1993, pp. 164-173). (the current lower bound on the problem is ~ 3:148 (chrobak et al., j. algorithms 24(1) (1997) 124-157). copyright 2001 elsevier science b.v.
on the competitive ratio of the work function algorithm for the k-server problem. the k-server problem is one of the most fundamental online problems. the problem is to schedule k mobile servers to visit a sequence of points in a metric space with minimum total mileage. the k-server conjecture of manasse, mcgeogh, and sleator states that there exists a k-competitive online algorithm. the conjecture has been open for over 15 years. the top candidate online algorithm for settling this conjecture is the work function algorithm (wfa) which was shown to have competitive ratio at most 2k - 1. in this paper, we lend support to the conjecture that wfa is in fact k-competitive by proving that it achieves this ratio in several special metric spaces: the line, the star, and all metric spaces with k + 2 points.
a hierarchy of probabilistic system types. we arrange various classes of probabilistic systems studied in the literature in an expressiveness hierarchy. our expressiveness criterion is the existence of a system translation, from the less expressive type into the more expressive type, that preserves and reflects probabilistic bisimilarity. we model the different system types as coalgebras of suitable behaviour functors and argue that the corresponding coalgebraic bisimilarity coincides with probabilistic bisimilarity for the classes for which the latter notion has been proposed in the literature. the theory of coalgebras provides a unified framework for the presentation of the different classes and the system translations we needed to establish the hierarchy. all these translations arise in a standard way from natural transformations between the two behaviour functors involved. such a translation generally preserves coalgebraic bisimilarity. we exploit a new result that, under mild assumptions on the behaviour functors, a system translation induced by a natural transformation with injective components also reflects bisimilarity.
structuring the elementary components of graphs having a perfect internal matching. graphs with perfect internal matchings are decomposed into elementary components, and these components are given a structure reflecting the order in which they can be reached by external alternating paths. it is shown that the set of elementary components can be grouped into pairwise disjoint families determined by the "two-way accessible" relationship among them. a family free is established by which every family member, except the root, has a unique father and mother identified as another elementary component and one of its canonical classes, from which the given member is two-way accessible. it is proved that every member of the family is only accessible through a distinguished canonical class of the root by external alternating paths. the families themselves are arranged in a partial order according to the order they can be covered by external alternating paths, and a complete characterization of the graph's forbidden and impervious edges is elaborated.
an induction principle for pure type systems. we present an induction principle for pure type systems and use that principle to define cps translations and to solve the problem of expansion postponement for a large class of pure type systems. our principle strengthens and generalises similar principles by dowek et al. [12] and barthe et al. [6], which have been respectively used to define &eegr;-long normal forms and cps translations for the systems of barendregt's λ-cube [2; 3]. copyright 2001 elsevier science b.v.
hardness results for neural network approximation problems. we consider the problem of efficiently learning in two-layer neural networks. we investigate the computational complexity of agnostically learning with simple families of neural networks as the hypothesis classes. we show that it is np-hard to find a linear threshold network of a fixed size that approximately minimizes the proportion of misclassified examples in a training set, even if there is a network that correctly classifies all of the training examples. in particular, for a training set that is correctly classified by some two-layer linear threshold network with k hidden units, it is np-hard to find such a network that makes mistakes on a proportion smaller than c/k2 of the examples, for some constant c. we prove a similar result for the problem of approximately minimizing the quadratic loss of a two-layer network with a sigmoid output unit.
prime normal form and equivalence of simple grammars. a prefix-free language is prime if it cannot be decomposed into a concatenation of two prefix-free languages. we show that we can check in polynomial time if a language generated by a simple context-free grammar is prime. our algorithm computes a canonical representation of a simple language, converting its arbitrary simple grammar into prime normal form (pnf); a simple grammar is in pnf if all its nonterminals define primes. we also improve the complexity of testing the equivalence of simple grammars. the best previously known algorithm for this problem worked in o(n13) time. we improve it to o(n7 log2 n) and o(n5 polylog v) time, where n is the total size of the grammars involved, and v is the length of a shortest string derivable from a nonterminal, maximized over all nonterminals.
compositional analysis for verification of parameterized systems. many safety-critical systems that have been considered by the verification community are parameterized by the number of concurrent components in the system, and hence describe an infinite family of systems. traditional model checking techniques can only be used to verify specific instances of this family. in this paper, we present a technique based on compositional model checking and program analysis for automatic verification of infinite families of systems. the technique views a parameterized system as an expression in a process algebra (ccs) and interprets this expression over a domain of formulas (modal mu-calculus), considering a process as a property transformer. the transformers are constructed using partial model checking techniques. at its core, our technique solves the verification problem by finding the limit of a chain of formulas. we present a widening operation to find such a limit for properties expressible in a subset of modal mu-calculus. we describe the verification of a number of parameterized systems using our technique to demonstrate its utility.
embedding problems for paths with direction constrained edges. we determine the reachability properties of the embeddings in r3 of a directed path, in the graph-theoretic sense, whose edges have each been assigned a desired direction (east, west, north, south, up, or down) but no length. we ask which points of r3 can be reached by the terminus of an embedding of such a path, by choosing appropriate positive lengths for the edges, if the embedded path starts at the origin, does not intersect itself, and respects the directions pre-assigned to its edges. this problem arises in the context of extending planar graph embedding techniques and vlsi rectilinear layout techniques from 2d to 3d. we give a combinatorial characterization of reachability that yields linear time recognition and layout algorithms. finally, we extend our characterization to rd, d > 3.
node rewriting in graphs and hypergraphs: a categorical framework. vertex rewriting in graphs is a very powerful mechanism which has been studied for quite a long time. in this paper we eventually provide a categorical theory of vertex rewriting and show how it can extend in a uniform way to node and pattern rewriting mechanisms in hypergraphs. copyright 2001 elsevier science b.v.
equilogical spaces. it is well known that one can build models of full higher-order dependent-type theory (also called the calculus of constructions) using partial equivalence relations (pers) and assemblies over a partial combinatory algebra. but the idea of categories of pers and ers (total equivalence relations) can be applied to other structures as well. in particular, we can easily define the category of ers and equivalence-preserving continuous mappings over the standard category top0 of topological t0-spaces; we call these spaces (a topological space together with an er) equilogical spaces and the resulting category equ. we show that this category--in contradistinction to top0--is a cartesian closed category. the direct proof outlined here uses the equivalence of the category equ to the category pequ of pers over algebraic lattices (a full subcategory of top0 that is well known to be cartesian closed from domain theory). in another paper with carboni and rosolini (cited herein), a more abstract categorical generalization shows why many such categories are cartesian closed. the category equ obviously contains top0 as a full subcategory, and it naturally contains many other well known subcategories. in particular, we show why, as a consequence of work of ershov, berger, and others, the kleene-kreisel hierarchy of countable functionals of finite types can be naturally constructed in equ from the natural numbers object n by repeated use in equ of exponentiation and binary products. we also develop for equ notions of modest sets (a category equivalent to equ) and assemblies to explain why a model of dependent type theory is obtained. we make some comparisons of this model to other, known models.
propositional default logics made easier: computational complexity of model checking. liberatore and schaerf (proceedings of the ecai' 98, 1998) give a proof that model checking for propositional normal default theories is in δ2p and δ2p[o(log n)]-hard. however, the precise complexity is left as an open problem. we solve this problem by proving that model checking for normal default theories is complete for δ2p[o(log n)]. this is the class of decision problems solvable in polynomial time with a logarithmic number of calls to an oracle in np. additionally, we analyse the computational cost of model checking w.r.t, weak extensions, stable expansions and n-expansions and take a look at the complexity of model checking for disjunction-free default theories. furthermore, we show that not only for disjunction-free default theories, but also for a larger class of default theories, which we call default theories in extended horn normal form, the complexity of model checking is, in the case of normal default theories, tractable. additionally, the complexity results are used to draw some interesting conclusions on translatability issues. in particular, there exists no function from default logic into logic programming which is polynomial, faithful and modular unless conp = σ2p. finally, we give an overview of our results concerning model checking in case of disjunctive default logic and stationary default logic.
completeness in standard and differential approximation classes: poly-(d)apx- and (d)ptas-completeness. several problems are known to be apx-, dapx-, ptas-, or poly-apx-pb-complete under suitably defined approximation-preserving reductions. but, to our knowledge, no natural problem is known to be ptas-complete and no problem at all is known to be poly-apx-complete. on the other hand, dptas- and poly-dapx-completeness have not been studied until now. we first prove in this paper the existence of natural poly-apx- and poly-dapx-complete problems under the well known ptas-reduction and under the dptas-reduction (defined in "g. ausiello, c. bazgan, m. demange, and v. th. paschos, completeness in differential approximation classes, mfcs'03"), respectively. next, we deal with ptas- and dptas-completeness. we introduce approximation preserving reductions, called ft and dft, respectively, and prove that, under these new reductions, natural problems are ptas-complete, or dptas-complete. then, we deal with the existence of intermediate problems under our reductions and we partially answer this question showing that the existence of npo-intermediate problems under turing-reductions is a sufficient condition for the existence of intermediate problems under both ft- and dft-reductions. finally, we show that min coloring is dapx-complete under dptas-reductions. this is the first dapx-complete problem that is not simultaneously apx-complete.
partitioning vertices of 1-tough graphs into paths. in this paper we prove that every 1-tough graph has a partition of its vertices into paths of length at least two.
on the differential approximation of min set cover. we present in this paper differential approximation results for min set cover and min weighted set cover. we first show that the differential approximation ratio of the natural greedy algorithm for min set cover is bounded below by 1.365/δ and above by 4/(δ + 1), where δ is the maximum set-cardinality in the min set cover-instance. next, we study another approximation algorithm for min set cover that computes 2-optimal solutions, i.e., solutions that cannot be improved by removing two sets belonging to them and adding another set not belonging to them. we prove that the differential approximation ratio of this second algorithm is bounded below by 2/(δ + 1) and that this bound is tight. finally, we study an approximation algorithm for min weighted set cover and provide a tight lower bound of 1/δ. our results identically hold for max hypergraph independent set in both the standard and the differential approximation paradigms.
degree-constrained decompositions of graphs: bounded treewidth and planarity. we study the problem of decomposing the vertex set v of a graph into two nonempty parts v1, v2 which induce subgraphs where each vertex v ∈ v1 has degree at least a(v) inside v1 and each v ∈ v2 has degree at least b(v) inside v2. we give a polynomial-time algorithm for graphs with bounded treewidth which decides if a graph admits a decomposition, and gives such a decomposition if it exists. this result and its variants are then applied to designing polynomial-time approximation schemes for planar graphs where a decomposition does not necessarily exist but the local degree conditions should be met for as many vertices as possible.
an algorithmic view of gene teams. comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are "not too far" in all genomes. in this paper, we propose a unifying concept, called gene teams, which can be adapted to various notions of distance. we present two algorithms for identifying gene teams formed by n genes placed on m linear chromosomes. the first one runs in o(mn log2n) and uses a divide and conquer approach based on the formal properties of gene teams. we next propose an optimization of the original algorithm, and, in order to better understand the complexity bound of the algorithms, we recast the problem in the hopcroft's partition refinement framework. this allows us to analyze the complexity of the algorithms with elegant amortized techniques. both algorithms require linear space. we also discuss extensions to circular chromosomes that achieve the same complexity.
determinization of transducers over finite and infinite words. we study the determinization of transducers over finite and infinite words. the first part of the paper is devoted to finite words. we recall the characterization of subsequential functions due to choffrut. we describe here a known algorithm to determinize a transducer.in the case of infinite words, we consider transducers with all their states final. we give an effective characterization of sequential functions over infinite words. we describe an algorithm to determinize transducers over infinite words. this part contains the main novel results of the paper.
squaring transducers: an efficient procedure for deciding functionality and sequentiality. we describe here a construction on transducers that give a new conceptual proof for two classical decidability results on transducers: it is decidable whether a finite transducer realizes a functional relation, and whether a finite transducer realizes a sequential relation. a better complexity follows then for the two decision procedures.
a hierarchy of shift equivalent sofic shifts. we define new subclasses of the class of irreducible sofic shifts. these classes form an infinite hierarchy where the lowest class is the class of almost finite type shifts introduced by b. marcus. we give effective characterizations of these classes with the syntactic semigroups of the shifts. we prove that these classes define invariants for shift equivalence (and thus for conjugacy). finally, we extend the result to the case of reducible sofic shifts.
codes and sofic constraints. we study the notion of a code in a sofic subshift. we first give a generalization of the kraft-mcmillan inequality to this case. we then prove that the polynomial of the alphabet in an irreducible sofic shift divides the polynomial of any finite code which is complete for this sofic shift. this settles a conjecture from reutenauer.
codes, unambiguous automata and sofic systems. we study the relationship between codes and unambiguous automata inside a sofic system. we show that a recognizable set is a code in a sofic system if and only if a particular automaton associated to the set and the shift is unambiguous. we discuss an example of a finite complete code in a sofic system in connection with the factorization conjecture.