waashk/dblp huggingface dataset:
on the expressive power of first-order boolean functions in pcf. recent results of bucciarelli show that the semilattice of degrees of parallelism of first-order boolean functions in pcf has both infinite chains and infinite antichains. by considering a simple subclass of sieber's sequentiality relations, we identify levels in the semilattice and derive inexpressibility results concerning functions on different levels. this allows us to further explore the structure of the semilattice of degrees of parallelism: we identify semilattices characterized by simple level properties, and show the existence of new infinite hierarchies which are in a certain sense natural with respect to the levels. copyright 2001 elsevier science b.v.
on reducibility and symmetry of disjoint np pairs. we consider some problems about pairs of disjoint np sets. the theory of these sets with a natural concept of reducibility is, on the one hand, closely related to the theory of proof systems for propositional calculus, and, on the other, it resembles the theory of np completeness. furthermore, such pairs are important in cryptography. among others, we prove that the broken mosquito screen pair of disjoint np sets can be polynomially reduced to clique-coloring pair and thus is polynomially separable and we show that the pair of disjoint np sets canonically associated with the resolution proof system is symmetric.
on the power of membrane division in p systems. first, we consider p systems with active membranes, hence with the possibility that the membranes can be divided, with non-cooperating evolution rules (the objects always evolve separately). these systems are known to be able to solve np-complete problems in linear time. here we give a normal form theorem for such systems: their computational universality is preserved even if only the elementary membranes are divided. the possibility of solving sat in linear time is preserved only when non-elementary membranes may also be divided under the influence of objects in their region.second, we consider a slight generalization, namely, we allow that a membrane can produce by division both a copy of itself and a copy of a membrane with a different label; again, only elementary membranes may be divided. in this case, we prove that the hierarchy on the maximal number of membranes present in the system collapses: three membranes at a time are sufficient in order to characterize the recursively enumerable sets of vectors of natural numbers. this result is optimal, two membranes are shown not to be sufficient.third, we consider p systems with cooperating rules (several objects may evolve together). making use of this powerful feature, we show that many np-complete problems can be solved in linear time in a quite uniform way (by systems which are very similar to each other), using only elementary membranes division (and not further ingredients, such as electrical charges). the degree of cooperation is minimal: two objects at a time.
greedy algorithms, h-colourings and a complexity-theoretic dichotomy. let h be a fixed undirected graph. an h-colouring of an undirected graph g is a homomorphism from g to h. if the vertices of g are partially ordered then there is a generic non-deterministic greedy algorithm which computes all lexicographically first maximal h- colourable subgraphs of g. we show that the complexity of deciding whether a given vertex of g is in a lexicographically first maximal h-colourable subgraph of g is np-complete, if h is bipartite, and σ2p-complete, if h is non-bipartite. this result complements hell and nesetril's seminal dichotomy result that the standard h-colouring problem is in p, if h is bipartite, and np-complete, if h is non-bipartite. our proofs use the basic techniques established by hell and nesetril, combinatorially adapted to our scenario.
possible worlds and resources: the semantics of bi. the logic of bunched implications, bi, is a substructural system which freely combines an additive (intuitionistic) and a multiplicative (linear) implication via bunches (contexts with two combining operations, one which admits weakening and contraction and one which does not). bi may be seen to arise from two main perspectives. on the one hand, from proof-theoretic or categorical concerns and, on the other, from a possible-worlds semantics based on preordered (commutative) monoids. this semantics may be motivated from a basic model of the notion of resource. we explain bi's proof-theoretic, categorical and semantic origins. we discuss in detail the question of completeness, explaining the essential distinction between bi with and without ⊥ (the unit of v). we give an extensive discussion of bi as a semantically based logic of resources, giving concrete models based on petri nets, ambients, computer memory, logic programming, and money.
characterizations of quantum automata. we define q quantum finite automata (qqfas) and q quantum regular grammars (qqrgs), and verify that they are exactly equivalent to those measure-once quantum finite automata (mo-qfas) in the literature. in particular, we define q quantum pushdown automata (qqpdas) and qpdas that are at least as powerful as those defined by moore and crutchfield, and especially we focus on demonstrating the equivalence between qqpdas and qpdas. also, we discuss some of the properties of languages accepted by qqpdas; for example, every cut-point language accepted by qqpda is independent of the cut-point
periodicity and local complexity. we consider the complexity of bi-infinite words in one and two dimensions. a result of morse and hedlund in one dimension states that if the complexity, pξ(n), of a word satisfies pξ(n) ≤ n for some n, then the word ξ is periodic. the corresponding question in two dimensions (whether pξ(m, n) ≤ mn implies that ξ is periodic) is known as the nivat conjecture. in this paper, we strengthen the one-dimensional result of morse and hedlund and prove a weak form of the nivat conjecture, namely that if for a bi-infinite two-dimensional word ξ, pξ(m, n) ≤ mn/16 then ξ is periodic.
convexity and global optimization: a theoretical link. here we propose a characterization of the subsets of rn which are the sets of local optima of the restriction of some convex function to some discrete subset, and we prove that, under some conditions, recognizing these subsets can be done in polynomial time. we discuss eventual applications of these results to global optimization problems.
finite variability interpretation of monadic logic of order. we consider an interpretation of monadic second-order logic of order in the continuous time structure of finitely variable signals. we provide a characterization of the expressive power of monadic logic. as a by-product of our characterization we show that many fundamental theorems which hold in the discrete time interpretation of monadic logic are still valid in the continuous time interpretation.
automata over continuous time. the principal objective of this paper is to lift basic concepts of the classical automata theory from discrete to continuous (real) time. it is argued that the set of finite memory retrospective functions is the set of functions realized by finite state devices. we show that the finite memory retrospective functions are speed-independent, i.e., they are invariant under 'stretchings' of the time axis. therefore, such functions cannot deal with metrical aspects of the reals.we classify and analyze phenomena which appear at continuous time and are invisible at discrete time.
improving time bounds on maximum generalised flow computations by contracting the network. we consider the maximum generalised network flow problem and a supply-scaling algorithmic framework for this problem. we present three network-modification operations, which may significantly decrease the size of the network when the remaining node supplies become small. we use these three operations in goldfarb et al.'s supply-scaling algorithm and prove an õ(m2n log b) bound on the running time of the resulting algorithm. the previous best time bounds on computing maximum generalised flows are the o(m1.5n log b) bound of kapoor and vaidya's algorithm based on the interior-point method, and the õ(m3 log b) bound of goldfarb et al.'s algorithm.
getting results from programs extracted from classical proofs. we present a new method to extract from a classical proof of ∀x(i[x] → ??(o[y] ∧ s[x,y])) a program computing y from x. this method applies when o is a data type and s is a decidable predicate. algorithms extracted this way are often far better than a stupid enumeration of all the possible outputs and this is verified on a nontrivial example: a proof of dickson's lemma.
on sparse evaluation representations. the sparse evaluation graph has emerged over the past several years as an intermediate representation that captures the dataflow information in a program compactly and helps perform dataflow analysis efficiently. the contributions of this paper are three-fold: we present a linear time algorithm for constructing a variant of the sparse evaluation graph for any dataflow analysis problem. our algorithm has two advantages over previous algorithms for constructing sparse evaluation graphs. first, it is simpler to understand and implement. second, our algorithm generates a more compact representation than the one generated by previous algorithms. (our algorithm is also as efficient as the most efficient known algorithm for the problem.) we present a formal definition of an equivalent flow graph, which attempts to capture the goals of sparse evaluation. we present a quadratic algorithm for constructing an equivalent flow graph consisting of the minimum number of vertices possible. we show that the problem of constructing an equivalent flow graph consisting of the minimum number of vertices and edges is np-hard. we generalize the notion of an equivalent flow graph to that of a partially equivalent flow graph, an even more compact representation, utilizing the fact that the dataflow solution is not required at every node of the control-flow graph. we also present an efficient linear time algorithm for constructing a partially equivalent flow graph. copyright 2002 elsevier science b.v.
parameterized algorithms for feedback set problems and their duals in tournaments. the parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. the parameterized complexity of this problem in general directed graphs is a long standing open problem. we investigate the problems on tournaments, a well studied class of directed graphs. we consider both weighted and unweighted versions.we also address the parametric dual problems which are also natural optimization problems. we show that they are fixed parameter tractable not just in tournaments but in oriented directed graphs (where there is at most one directed arc between a pair of vertices). more specifically, the dual problem we show fixed parameter tractable are: given an oriented directed graph, is there a subset of k vertices (arcs) that forms an acyclic directed subgraph of the graph?our main results include: • an o((2.4143)knω)1 algorithm for weighted feedback vertex set problem, and an o((2.415)knω) algorithm for weighted feedback arc set problem in tournaments; • an o((e2k/k)kk2 + min{m ig n, n2}) algorithm for the dual of feedback vertex set problem (maximum vertex induced acyclic graph) in oriented directed graphs, and an o(4kk + m) algorithm for the dual of feedback arc set problem (maximum arcinduced acyclic graph) in general directed graphs.we also show that the dual of feedback vertex set is w[1]--hard in general directed graphs and the feedback arc set problem is fixed parameter tractable in dense directed graphs. our results are the first non-trivial results for these problems.
a (restricted) quantifier elimination for security protocols. while reasoning about security protocols, most of the difficulty of reasoning relates to the complicated semantics (with freshness of nonces, multisessions, etc.). while logics for security protocols need to be abstract (without explicitly dealing with nonces, encryption, etc.), ignoring details may result in rendering any verification of abstract properties worthless. we would like the verification problem for the logic to be decidable as well, to allow for automated methods for detecting attacks. from this viewpoint, we study a logic with session abstraction and quantifiers over session names. we show that interesting security properties like secrecy and authentication can be described in the logic. we prove the existence of a normal form for runs of tagged protocols. this leads to a quantifier elimination result for the logic which establishes the decidability of the verification problem for tagged protocols, when we assume a fixed finite set of nonces.
avoiding large squares in infinite binary words. we consider three aspects of avoiding large squares in infinite binary words. first, we construct an infinite binary word avoiding both cubes xxx and squares yy with |y| ≥4; our construction is somewhat simpler than the original construction of dekking. second, we construct an infinite binary word avoiding all squares except 02, 12, and (01)2; our construction is somewhat simpler than the original construction of fraenkel and simpson. in both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. finally, we answer an open question of prodinger and urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.
polynomial-time learnability of logic programs with local variables from entailment. in this paper, we study exact learning of logic programs from entailment and present a polynomial time algorithm to learn a rich class of logic programs that allow local variables and include many standard programs like append, merge, split, delete, member, prefix, suffix, length, reverse, append/4 on lists, tree traversal programs on binary trees and addition, multiplication and exponentiation on natural numbers. grafting a few aspects of incremental learning (krishna rao, proc. algorithmic learning theory, alt'95, lecture notes in artificial intelligence, vol. 997, pp. 95--109. revised version in theoret. comput. sci. special issue on alt'95 185 (1995) 193--213) onto the framework of learning from entailment (arimura, proc. algorithmic learning theory, alt'97, lecture notes in artificial intelligence, vol. 1316, 1997, pp. 432--445), we generalize the existing results to allow local variables, which play an important role of sideways information passing in the paradigm of logic programming. 2001 elsevier science b.v. all rights reserved
complexity of hyperconcepts. in machine-learning, maximizing the sample margin can reduce the learning generalization error. samples on which the target function has a large margin (γ) convey more information since they yield more accurate hypotheses. let x be a finite domain and s denote the set of all samples s ⊆ x of fixed cardinality m. let h be a class of hypotheses h on x. a hyperconcept h' is defined as an indicator function for a set a ⊆ s of all samples on which the corresponding hypothesis h has a margin of at least γ. an estimate on the complexity of the class h' of hyperconcepts h' is obtained with explicit dependence on γ, the pseudodimension of h and m.
deadlocks and dihomotopy in mutual exclusion models. higher dimensional automata (hda) represent a promising tool for modelling ("true") concurrency in a both combinatorial and topological framework. within these models, fast algorithms investigating deadlocks and unreachable regions have been devised previously on a background of easily understandable "directed" geometric ideas. in this article, we modify notions and methods from homotopy theory to define and investigate "essentially different" schedules in a hda and to detect whether two given runs are essentially different using an algorithm again based on "directed geometry".
forbidden subgraphs in connected graphs. given a set ξ = {h1,h2,...} of connected non-acyclic graphs, a ξ-free graph is one which does not contain any member of ξ as copy. define the excess of a graph as the difference between its number of edges and its number of vertices. let wk,ξ be the exponential generating function (egf for brief) of connected ξ-free graphs of excess equal to k (k ≥ 1). for each fixed ξ, a fundamental differential recurrence satisfied by the egfs wk,ξ is derived. we give methods on how to solve this nonlinear recurrence for the first few values of k by means of graph surgery. we also show that for any finite collection ξ of non-acyclic graphs, the egfs wk,ξ are always rational functions of the generating function, t, of cayley's rooted (non-planar) labelled trees. from this, we prove that almost all connected graphs with n nodes and n + k edges are ξ-free, whenever k = o(n1/3) and |ξ| < ∞ by means of wright's inequalities and saddle point method. limiting distributions are derived for sparse connected ξ-free components that are present when a random graph on n nodes has approximately n/2 edges. in particular, the probability distribution that it consists of trees, unicyclic components, ..., (q + 1)-cyclic components all ξ-free is derived. similar results are also obtained for multigraphs, which are graphs where self-loops and multiple-edges are allowed.
peg-solitaire, string rewriting systems and finite automata. we consider a class of length-preserving string rewriting systems and show that the set of encodings of pairs of strings 〈s, f〉 such that f can be derived from s using the rewriting rules can be accepted by finite automata. as a consequence, we show the existence of a linear time algorithm for determining the solvability of a given k × n peg-solitaire board, for any fixed k. this result is in contrast to the results of (13) and (1) that the same problem is np-hard for n × n boards. we look at some related string rewriting systems and find conditions under which the encodings of the pairs 〈s,f〉 where f can be derived from s is regular.
weak minimization of dfa - an algorithm and applications. dfa minimization is an important problem in algorithm design and is based on the notion of dfa equivalence: two dfa's are equivalent if and only if they accept the same set of strings. in this paper, we propose a new notion of dfa equivalence (that we call weak-equivalence): we say that two dfa's are weakly equivalent if they both accept the same number of strings of length k for every k. the motivation for this problem is as follows. a large number of counting problems can be solved by encoding the combinatorial objects we want to count as strings over a finite alphabet. if the collection of encoded strings is accepted by a dfa, then standard algorithms from computational linear algebra can be used to solve the counting problem efficiently. when applying this approach to large-scale applications, the bottleneck is the space complexity since the computation involves a matrix of order k × k if k is the size of the underlying dfa m. this leads to the natural question: is there a smaller dfa that is weakly equivalent to m? we present an algorithm of time complexity o(k3) to find a compact dfa weakly equivalent to a given dfa. we illustrate, in the case of a tiling problem, that our algorithm reduces a (strongly minimal) dfa by a factor close to 1/2.
dense edge-disjoint embedding of complete binary trees in interconnection networks. we describe dense edge-disjoint embeddings of the complete binary tree with n leaves in the following n-node communication networks: the hypercube, the de bruijn and shuffle-exchange networks and the two-dimensional mesh. for the mesh and the shuffle-exchange graphs each edge is regarded as two parallel (or anti-parallel) edges. the embeddings have the following properties: paths of the tree are mapped onto edge-disjoint paths of the host graph and at most two tree nodes (just one of which is a leaf) are mapped onto each host node. we prove that the maximum distance from a leaf to the root of the tree is asymptotically as short as possible in all host graphs except in the case of the shuffle-exchange, in which case we conjecture that it is as short as possible. the embeddings facilitate efficient implementation of many p-ram algorithms on these networks.
resolution lower bounds for the weak functional pigeonhole principle. we show that every resolution proof of the functional version fphpnm of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp(ω(n/(log m)2)). this implies an exp(ω(n1/3)) bound when the number of pigeons m is arbitrary.
bioambients: an abstraction for biological compartments. biomolecular systems, composed of networks of proteins, underlie the major functions of living cells. compartments are key to the organization of such systems. we have previously developed an abstraction for biomolecular systems using the π-calculus process algebra, which successfully handled their molecular and biochemical aspects, but provided only a limited solution for representing compartments. in this work, we extend this abstraction to handle compartments. we are motivated by the ambient calculus, a process algebra for the specification of process location and movement through computational domains. we present the bioambients calculus, which is suitable for representing various aspects of molecular localization and compartmentalization, including the movement of molecules between compartments, the dynamic rearrangement of cellular compartments, and the interaction between molecules in a compartmentalized setting. guided by the calculus, we adapt the biospi simulation system, to provide an extended modular framework for molecular and cellular compartmentalization, and we use it to model and study a complex multi-cellular system.
a non-learnable class of e-pattern languages. we investigate the inferrability of e-pattern languages (also known as extended or erasing pattern languages) from positive data in gold's learning model. as the main result, our analysis yields a negative outcome for the full class of e-pattern languages--and even for the subclass of terminal-free e-pattern languages--if the corresponding terminal alphabet consists of exactly two distinct letters. furthermore, we present a positive result for a manifest subclass of terminal-free e-pattern languages. we point out that the considered problems are closely related to fundamental questions concerning the nondeterminism of e-pattern languages.