waashk/dblp huggingface dataset:
algorithms for four variants of the exact satisfiability problem. we present four polynomial space and exponential time algorithms for variants of the exact satisfiability problem. first, an o(1.1120n) (where n is the number of variables) time algorithm for the np-complete decision problem of exact 3-satisfiability, and then an o(1.1907n) time algorithm for the general decision problem of exact satisfiability. the best previous algorithms run in o(1.1193n) and o(1.2299n) time, respectively. for the #p-complete problem of counting the number of models for exact 3-satisfiability we present an o(1.1487n) time algorithm. we also present an o(1.2190n) time algorithm for the general problem of counting the number of models for exact satisfiability; presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix.
counting models for 2sat and 3sat formulae. we here present algorithms for counting models and max-weight models for 2sat and 3sat formulae. they use polynomial space and run in o(1.2561n) and o(1.6737n) time, respectively, where n is the number of variables. this is faster than the previously best algorithms for counting nonweighted models for 2sat and 3sat, which run in o(1.3247n) and o(1.6894n) time, respectively. in order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. we also provide an algorithm for the restricted case of separable 2sat formulae, with fast running times for well-studied input classes. for all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices.
finite-state dimension. classical hausdorff dimension (sometimes called fractal dimension) was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. in this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. the theorem of eggleston (quart. j. math. oxford ser. 20 (1949) 31-36) relating hausdorff dimension to entropy is shown to hold for finite-state dimension, both in the space of all sequences and in the space of all rational sequences (binary expansions of rational numbers). every rational sequence has finite-state dimension 0, but every rational number in [0,1] is the finite-state dimension of a sequence in the low-level complexity class ac0. our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors.
backtracking games and inflationary fixed points. we define a new class of games, called backtracking games. backtracking games are essentially parity games with an additional rule allowing players, under certain conditions, to return to an earlier position in the play and revise a choice or to force a countback of the number of moves. this new feature makes backtracking games more powerful than parity games. as a consequence, winning strategies become more complex objects and computationally harder. the corresponding increase in expressiveness allows us to use backtracking games as model-checking games for inflationary fixed-point logics such as ifp or mic. we identify a natural subclass of backtracking games, the simple games, and show that these are the "right" model-checking games for ifp by (a) giving a translation of formulae ϕ and structures u into simple games such that u = φ if, and only if, player 0 wins the corresponding game and (b) showing that the winner of simple backtracking games can again be defined in ifp.
closure and decidability properties of some language classes with respect to ciliate bio-operations. the process of gene unscrambling in ciliates (a type of unicellular protozoa), which accomplishes the difficult task of re-arranging gene segments in the correct order and deleting non-coding sequences from an "encrypted" version of a dna strand, has been modeled and studied so far from the point of view of the computational power of the dna bio-operations involved. here we concentrate on a different aspect of the process, by considering only the linear version of the bio-operations, that do not involve thus any circular strands, and by studying the resulting formal operations from a purely language-theoretic point of view. we investigate closure properties of language families under the mentioned bio-operations and study language equations involving them. we also study the decidability of the existence of solutions to equations of the form l ♦ y = r, x ♦ l = r where l and r are given languages, x and y are unknowns, and ♦ signifies one of the defined bio-operations.
template-guided dna recombination. the family of stichotrichous ciliates have received a great deal of study due to the presence of scrambled genes in their genomes. the mechanism by which these genes are descrambled is of interest both as a biological process and as a model of natural computation. several formal models of this process have been proposed, the most recent of which involves the recombination of dna strands based on template guides. we generalize this template-guided dna recombination model proposed by prescott, ehrenfeucht and rozenberg to an operation on strings and languages. we then proceed to investigate the properties of this operation with the intention of viewing ciliate gene descrambling as a computational process.
learnability of quantified formulas. we consider the following classes of quantified formulas. fix a set of basic relations called a basis. take conjunctions of these basic relations applied to variables and constants in arbitrary ways. finally, quantify existentially or universally some of the variables. we introduce some conditions on the basis that guarantee efficient learnability. furthermore, we show that with certain restrictions on the basis the classification is complete. we introduce, as an intermediate tool, a link between this class of quantified formulas and some well-studied structures in universal algebra called clones. more precisely, we prove that the computational complexity of the learnability of these formulas is completely determined by a simple algebraic property of the basis of relations: their clone of polymorphisms. finally, we use this technique to give a simpler proof of the already known dichotomy theorem over boolean domains.
the complexity of counting homomorphisms seen from the other side. for every class of relational structures c, let hom(c, _) be the problem of deciding whether a structure a ∈ c has a homomorphism to a given arbitrary structure b. grohe has proved that, under a certain complexity-theoretic assumption, hom(c, _) is solvable in polynomial time if and only if the cores of all structures in c have bounded tree-width. we prove (under a weaker complexity-theoretic assumption) that the corresponding counting problem #hom(c, _) is solvable in polynomial time if and only if all structures in c have bounded tree-width. this answers an open question posed by grohe.
a 5/4-approximation algorithm for scheduling identical malleable tasks. we consider the problem of finding a schedule for n-independent identical malleable tasks on p identical processors with minimal completion time. this problem arises while using the branch-and-bound or the divide-and-conquer strategy to solve a problem on a parallel system. if nothing is known about the subproblems, then they are assumed to be identical. we assume that the execution time decreases with the number of processors while the computational work increases. we give an algorithm with execution time exponential in p which computes an optimal schedule. in order to approximate an optimal schedule, we use the concept of phase-by-phase schedules. here schedules consist of phases in which every job uses the same number of processors. we prove that one can approximate an optimal schedule up to a factor of 5/4 using constant time, and we show that this is optimal. furthermore, we give an ε-approximation algorithm if the speed-up is optimal up to a constant factor.
two short notes on the on-line travelling salesman: handling times and lookahead. we study extensions of the on-line travelling salesman problem. our results are: the optimal competitive ratio 2 for arbitrary metric spaces also holds in the case of nonzero handling times. the optimal competitive ratio 3/2 on the half-line cannot be improved by randomization, but there is a 4/3-competitive algorithm under the assumption that the server is notified when the last request has been released. this ratio is also optimal.
nearly optimal strategies for special cases of on-line capital investment. suppose that some job must be done for a period of unspecified duration. the market offers a selection of devices that can do this job, each characterized by purchase and running costs. which of them should we buy at what times, in order to minimize the total costs? as usual in competitive analysis, the cost of an on-line solution is compared to the optimum costs paid by a clearvoyant buyer. this problem which generalizes the basic rent-to-buy problem has been introduced by azar et al. in the so-called convex case where lower running costs always imply higher prices, a strategy with competitive ratio 4+2√2 ≈ 6.83 has been proposed. here we consider two natural subcases of the convex case in a continuous-time model where new devices can be bought at any time. for the static case where all devices are available at the beginning, we give a simple 4-competitive deterministic algorithm, and we show that 3.618 is a lower bound. (this is also the first non-trivial lower bound for the convex case, both for discrete and continuous time.) furthermore, we give a 2.88-competitive randomized algorithm. in the case that all devices have equal prices but are not all available at the beginning, we show that a very simple algorithm is 2-competitive, and we derive a 1.618 lower bound.
a causal semantics for ccs via rewriting logic. we consider two operational semantics for ccs defined in the literature: the first exploits proved transition systems (pts) and the second rewriting logic (rl). we show that the interleaving interpretation of both semantics agree, in that they define the same transitions and exhibit the same non-deterministic structure. in addition, we study causality in ccs computations. we recall its treatment via pts, exhibiting the notion of causality presented in the literature, and we show how to recast it in the rl semantics via suitable axioms. also in this case, the two semantics agree.
parameterized enumeration, transversals, and imperfect phylogeny reconstruction. we study parameterized enumeration problems where we are interested in all solutions of limited size rather than just some solution of minimum cardinality. (actually, we have to enumerate the inclusion-minimal solutions in order to get fixed-parameter tractable (fpt) results.) two novel concepts are the notion of a full kernel that contains all small solutions and implicit enumeration of solutions in form of compressed descriptions. in particular, we study combinatorial and computational bounds for the transversal hypergraph (vertex covers in graphs is a special case), restricted to hyperedges with at most k elements. as an example, we apply the results and further special-purpose techniques to almost-perfect phylogeny reconstruction, a problem in computational biology.
on queuing lengths in on-line switching. queues that temporarily store fixed-length packets are ubiquitous in network switches. scheduling algorithms that prevent packet-loss are always desirable. longest-queue-first (lqf) is an on-line greedy algorithm widely exploited because of its simplicity and efficiency. in this paper, we give improved bounds on the competitive ratio of lqf in terms of the worst-case queuing length, parameterized with respect to the optimal queuing length of a clairvoyant adversary. this gives a better picture of lqf's performance under heavy traffic than the usual (unparameterized) competitive ratio. we also discuss randomization, and we conclude with some intriguing open problems regarding a two-dimensional generalization of the problem.
a simple paradigm for graph recognition: application to cographs and distance hereditary graphs. an easy way for graph recognition algorithms is to use a two-step process: first, compute a characteristic feature as if the graph belongs to that class; second, check whether the computed characteristic feature as if the graph belongs to that class; second, check whether the computed separating them may yield new and much more easily understood algorithms. in this paper we apply that paradigm to the cograph and distance hereditary graph recognition problems.
on computing the entropy of cellular automata. we study the topological entropy of a particular class of dynamical systems: cellular automata. the topological entropy of a dynamical system (x,f) is a measure of the complexity of the dynamics of f over the space x. the problem of computing (or even approximating) the topological entropy of a given cellular automata is algorithmically undecidable (ergodic theory dynamical systems 12 (1992) 255). in this paper, we show how to compute the entropy of two important classes of cellular automata namely, linear and positively expansive cellular automata. in particular, we prove a closed formula for the topological entropy of d-dimensional (d ≥ 1) linear cellular automata over the ring zm (m ≥ 2) and we provide an algorithm for computing the topological entropy of positively expansive cellular automata.
formalizing generalized maps in coq. this paper is the first half of a two-part series devoted to an exemplary formal proof of a fundamental result in the field of geometry--the theorem of classification of surfaces--which has major implications in computer graphics. we study here the specification of generalized maps, a topological combinatory model for surfaces subdivisions. we show how we developed in coq two fundamentally distinct formalizations of generalized maps, each based on one of the standard definitions, in a single common framework, then used this specification to prove for the first time their complete equivalence.
formalizing the trading theorem in coq. this paper is the second half of a two-part series devoted to the formalization of a combinatorial model of geometric varieties, generalized maps. we study here how to express continuous notions like homeomorphisms in the combinatorial world, in order to constructively describe the well-known theorem of surface classification according to genus, number of boundaries and orientability coefficient. we then use the coq specification elaborated in the previous paper to prove the first half of this theorem, called the trading theorem.
pushdown timed automata: a binary reachability characterization and safety verification. we consider pushdown timed automata (ptas) that are timed automata (with dense clocks) augmented with a pushdown stack. a configuration of a pta includes a state, dense clock values and a stack word. by using the pattern technique, we give a decidable characterization of the binary reachability (i.e., the set of all pairs of configurations such that one can reach the other) of a pta. since a timed automaton can be treated as a pta without the pushdown stack, we can show that the binary reachability of a timed automaton is definable in the additive theory of reals and integers. the results can be used to verify a class of properties containing linear relations over both dense variables and unbounded discrete variables. the properties previously could not be verified using the classic region technique nor expressed by timed temporal logics for timed automata and ctl* for pushdown systems. the results are also extended to other generalizations of timed automata.
past pushdown timed automata and safety verification. we consider past pushdown timed automata that are discrete pushdown timed automata with past formulas as enabling conditions. using past formulas allows a past pushdown timed automaton to access the past values of the finite state variables in the automaton. we prove that the reachability (i.e., the set of reachable configurations from an initial configuration) of a past push-down timed automaton can be accepted by a nondeterministic reversal-bounded counter-machine augmented with a pushdown stack (i.e., a reversal-bounded npcm). by using the known fact that the emptiness problem for reversal-bounded npcms is decidable, we show that model-checking past pushdown timed automata against presburger safety properties on discrete clocks and stack word counts is decidable. we also investigate the reachability problem for a class of transition systems under some fairness constraints in the form of generalized past formulas. finally, we present an example astral specification to demonstrate the usefulness of the results.
generalized discrete timed automata: decidable approximations for safety verificatio. we consider generalized discrete timed automata with general linear relations over clocks and parameterized constants as clock constraints and with parameterized durations. we look at three approximation techniques (i.e., the r-reset-bounded approximation, the b-bounded approximation, and the 〈b, r〉-crossing-bounded approximation), and derive automata-theoretic characterizations of the binary reachability under these approximations. the characterizations allow us to show that the safety analysis problem is decidable for generalized discrete timed automata with unit durations and for deterministic generalized discrete timed automata with parameterized durations. an example specification written in astral is used to run a number of experiments using one of the approximation techniques.
on two-way nondeterministic finite automata with one reversal-bounded counter. we show that the emptiness problem for two-way nondeterministic finite automata augmented with one reversal-bounded counter (i.e., the counter alternates between nondecreasing and nonincreasing modes for a fixed number of times) operating on bounded languages (i.e., subsets of w*1 ... w*k for some nonnull words w1, ...., wk) is decidable, resolving an open problem. the proof is a rather involved reduction to the solution of a special class of diophantine systems of degree 2 via a class of programs called two-phase programs.
on feasible cases of checking multi-agent systems behavior. the complexity of multi-agent systems behavior properties is studied. the behavior properties are formulated using classical temporal logic languages and are checked relative to the transition system induced by the multi-agent system definition. we show that there are deterministic or nondeterministic polynomial time check algorithms under some realistic structural and semantic restrictions on agent programs and actions.
on composition and lookahead delegation of -services modeled by automata. let m be a class of (possibly nondeterministic) language acceptors with a one-way input tape. a system (a; a1,..., ar) of automata in m is composable if for every string w = a1...an of symbols accepted by a, there is an assignment of each symbol aj in w to one of the ai's such that for each 1 ≤ i ≤ r, the subsequence of w assigned to ai is accepted by ai. for a nonnegative integer k, a k-lookahead delegator for (a; a1,..., ar) is a deterministic machine d in m which, knowing (a) the current states of a, a1,...,ar and the accessible "local" information of each machine (e.g., the top of the stack if each machine is a pushdown automaton, whether a counter is zero or nonzero if each machine is a multicounter automaton, etc.), and (b) the k lookahead symbols to the right of the current input symbol being processed, can uniquely determine the ai to assign the current symbol. moreover, every string w accepted by a is also accepted by d; i.e., the subsequence of string w delegated by d to each ai is accepted by ai. thus, k-lookahead delegation is a stronger requirement than composability, since the delegator d must be deterministic. a system that is composable may not have a k-delegator for any k.we study the decidability of composability and existence of k-delegators for various classes of machines m. our results generalize earlier ones (and resolve some open questions) concerning composability of deterministic finite automata as e-services to finite automata that are augmented with unbounded storage (e.g., counters and pushdown stacks) and finite automata with discrete clocks (i.e., discrete timed automata). the results have applications to automated composition of e-services.
presburger liveness verification of discrete timed automata. using an automata-theoretic approach, we investigate the decidability of liveness properties (called presburger liveness properties) for timed automata when presburger formulas on configurations are allowed. while the general problem of checking a temporal logic such as tptl augmented with presburger clock constraints is undecidable, we show that there are various classes of presburger liveness properties which are decidable for discrete timed automata. for instance, it is decidable, given a discrete timed automaton a and a presburger property p, whether there exists an ω-path of a where p holds infinitely often. we also show that other classes of presburger liveness properties are indeed undecidable for discrete timed automata, e.g., whether p holds infinitely often for each ω-path of a. these results might give insights into the corresponding problems for timed automata over dense domains, and help in the definition of a fragment of linear temporal logic, augmented with presburger conditions on configurations, which is decidable for model checking timed automata.
identifying codes in some subgraphs of the square lattice. an identifying code of a graph is a subset of vertices c such that the sets b(v) ∩ c are all nonempty and different. in this paper, we investigate the problem of finding identifying codes of minimum cardinality in strips and finite grids. we first give exact values for the strips of height 1 and 2, then we give general bounds for strips and finite grids. finally, we give a sublinear algorithm which finds the minimum cardinality of an identifying code in a restricted class of graphs which includes the grid.
using interval arithmetic to prove that a set is path-connected. in this paper, we give a numerical algorithm able to prove whether a set s described by nonlinear inequalities is path-connected or not. to our knowledge, no other algorithm (numerical or symbolic) is able to deal with this type of problem. the proposed approach uses interval arithmetic to build a graph which has exactly the same number of connected components as s. examples illustrate the principle of the approach.