waashk/dblp huggingface dataset:
minimization and np multifunctions. the implicit characterizations of the polynomial-time computable functions fp given by bellantoni-cook and leivant suggest that this class is the complexity-theoretic analog of the primitive recursive functions. hence, it is natural to add minimization operators to these characterizations and investigate the resulting class of partial functions as a candidate for the analog of the partial recursive functions. we do so in this paper for cobham's definition of fp by bounded recursion and for bellantoni-cook's safe recursion and prove that the resulting classes capture exactly npmv, the nondeterministic polynomial-time computable partial multifunctions. we also consider the relationship between our schemes and a notion of nondeterministic recursion defined by leivant and show that the latter characterizes the total functions of npmv. we view these results as giving evidence that npmv is the appropriate analog of partial recursive. this view is reinforced by earlier results of spreen and stahl who show that for many of the relationships between partial recursive functions and r.e. sets, analogous relationships hold between npmv and np sets. furthermore, since npmv is obtained from fp in the same way as the recursive functions are obtained from the primitive recursive functions (when defined via function schemes), this also gives further evidence that fp is properly seen as playing the role of primitive recursion.
enumeration of polyominoes using macsyma. this paper shows the use of a symbolic language, macsyma, to obtain new exact or asymptotic results in combinatorics. the examples are taken among polyominoes [sic] objects. the main purpose of the paper is to show how easy it is to bring some methods into operation in order to obtain new results in enumerative combinatorics. &mdash;from the abstract
computational isomorphisms in classical logic. all standard 'linear' boolean equations are shown to be computationally realized within a suitable classical sequent calculus lkηp. specifically, lkηp can be equipped with a cut-elimination compatible equivalence on derivations based upon reversibility properties of logical rules. so that any pair of derivations, without structural rules, of f → g and g → f, where f, g are first-order formulas 'without any qualities', defines a computational isomorphism.
formal molecular biology. a language of formal proteins, the k-calculus, is introduced. interactions are modeled at the domain level, bonds are represented by means of shared names, and reactions are required to satisfy a causality requirement of monotonicity.an example of a simplified signalling pathway is introduced to illustrate how standard biological events can be expressed in our protein language. a more comprehensive example, the lactose operon, is also developed, bringing some confidence in the formalism considered as a modeling language.then a finer-grained concurrent model, the mk-calculus, is considered, where interactions have to be at most binary. we show how to embed the coarser-grained language in the latter, a properly which we call self-assembly.finally we show how the finer-grained language can itself be encoded in π-calculus, a standard foundational language for concurrency theory.
a deterministic (2-2/(k+1)) algorithm for k-sat based on local search. local search is widely used for solving the propositional satisfiability problem. papadimitriou (1991) showed that randomized local search solves 2-sat in polynomial time. recently, schöning (1999) proved that a close algorithm for k-sat takes time (2 - 2/k)n up to a polynomial factor. this is the best known worst-case upper bound for randomized 3-sat algorithms (cf. also recent preprint by schuler et al.).we describe a deterministic local search algorithm for k-sat running in time (2-2/(k+ 1))n up to a polynomial factor. the key point of our algorithm is the use of covering codes instead of random choice of initial assignments. compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. we also describe an improved version of local search. for 3-sat the improved algorithm runs in time 1.481n up to a polynomial factor. our bounds are better than all previous bounds for deterministic k-sat algorithms.
a first-order one-pass cps transformation. we present a new transformation of λ-terms into continuation-passing style (cps). this transformation operates in one pass and is both compositional and first-order. previous cps transformations only enjoyed two out of the three properties of being first-order, one-pass, and compositional, but the new transformation enjoys all three properties. it is proved correct directly by structural induction over source terms instead of indirectly with a colon translation, as in plotkin's original proof. similarly, it makes it possible to reason about cps-transformed terms by structural induction over source terms, directly.the new cps transformation connects separately published approaches to the cps transformation. it has already been used to state a new and simpler correctness proof of a direct-style transformation, and to develop a new and simpler cps transformation of control-flow information.
quasi-periodic configurations and undecidable dynamics for tilings, infinite words and turing machines. we describe turing machines, tilings and infinite words as dynamical systems and analyze some of their dynamical properties. it is known that some of these systems do not always have periodic configurations; we prove that they always have quasi-periodic configurations and we quantify quasi-periodicity. we then study the decidability of dynamical properties for these systems. in analogy to rice's theorem for computable functions, we derive a theorem that characterizes dynamical system properties that are undecidable. as an illustration of this result, we prove that topological entropy is undecidable for turing machines and for tilings.
solitaire clobber. clobber is a new two-player board game. in this paper, we introduce the one-player variant solitaire clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves. we show that a n stone checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones. for boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones. we also show that in general it is np-complete to decide whether an arbitrary clobber configuration can be reduced to a single stone.
correlation clustering in general weighted graphs. we consider the following general correlation-clustering problem [n. bansal, a. blum, s. chawla, correlation clustering, in: proc. 43rd annu. ieee symp. on foundations of computer science, vancouver, canada, november 2002, pp. 238-250]: given a graph with real nonnegative edge weights and a 〈+〉/〈-〉 edge labelling, partition the vertices into clusters to minimize the total weight of cut 〈+〉 edges and uncut 〈-〉 edges. thus, 〈+〉 edges with large weights (representing strong correlations between endpoints) encourage those endpoints to belong to a common cluster while 〈-〉 edges with large weights encourage the endpoints to belong to different clusters. in contrast to most clustering problems, correlation clustering specifies neither the desired number of clusters nor a distance threshold for clustering; both of these parameters are effectively chosen to be best possible by the problem definition.correlation clustering was introduced by bansal et al. [correlation clustering, in: proc. 43rd annu. ieee syrup. on foundations of computer science, vancouver, canada, november 2002, pp. 238-250], motivated by both document clustering and agnostic learning. they proved np-hardness and gave constant-factor approximation algorithms for the special case in which the graph is complete (full information) and every edge has the same weight. we give an o(log n)-approximation algorithm for the general case based on a linear-programming rounding and the "region-growing" technique. we also prove that this linear program has a gap of ω(log n), and therefore our approximation is tight under this approach. we also give an o(r3)-approximation algorithm for kr, r-minor-free graphs. on the other hand, we show that the problem is equivalent to minimum multicut, and therefore apx-hard and difficult to approximate better than θ(log n).
operations and language generating devices suggested by the genome evolution. language-theoretic problems arising from the genome evolution discussed in series of papers (dassow and mitrana, proc. 2nd pacific symp. on biocomputing, world scientific, singapore, 1997, pp. 97-108; bioinformatics, lecture notes in computer science, vol. 1278, springer, berlin, pp. 199-209; dassow et al., biosystems 43 (1997) 169-177; dassow, jewels are forever, springer, berlin, 1999, pp. 171-181) are presented in a uniform way. the main emphasis is on the operations of inversion, transposition, duplication and deletion suggested by the genome evolution. basic problems concerning these operations and their iterated versions are settled. a generative device (evolutionary grammar) based on these operations is investigated from different points of view (computational power, decidability problems, descriptional complexity). "adult languages" (sets of stable strings) of such evolutionary grammars possess a surprising generative power.
understanding the mismatch combinator in chi calculus. the theory of chi processes with the mismatch operator is studied. four congruence relations are investigated. these are late open congruence, early open congruence, ground congruence and barbed congruence. the late and early open congruence relations are the chi calculus counterparts of the weak late and early congruence relations of pi calculus. both turn out to be special cases of the ground congruence and the barbed congruence. the ground congruence is essentially the open congruence. complete systems are given for all the four congruence relations. these systems use some interesting tau laws unknown from previous studies of the chi calculus without the mismatch combinator. the results of this paper point out that the mismatch operator changes the algebraic semantics of chi calculus dramatically. they also correct some common mistakes in literature.
online searching with turn cost. we consider the problem of searching for an object on a line at an unknown distance opt from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. this is a generalization of the well-studied linear-search problem. we describe a strategy that is guaranteed to find the object at a cost of at most 9 ċ opt + 2d, which has the optimal competitive ratio 9 with respect to opt plus the minimum corresponding additive term. our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences for an explicit proof of optimality. we feel that this technique is interesting in its own right and should help solve other searching problems. in particular, we consider the star search or cowpath problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. for this problem we give a tight bound of (1 + 2mm/(m - 1)m-1)opt + m((m/(m - 1))m-1 - 1)d. we also discuss tradeoffs between the corresponding coefficients and we consider randomized strategies on the line.
range assignment for energy efficient broadcasting in linear radio networks. given a set s of n radio-stations located on a d-dimensional space, a source node s (∈ s) and an integer h (1 ≤ h ≤ n - 1), the h-hop broadcast range assignment problem deals with assigning ranges to the members in s so that s can communicate with all other members in s in at most h-hops, and the total power consumption is minimum. the problem is known to be np-hard for d ≥ 2. we propose an o(n2) time algorithm for the one dimensional version (d = 1) of the problem. this is an improvement over the existing result on this problem by a factor of h [a.e.f clementi et al. the minimum broadcast range assignment problem on linear multi-hop wireless networks, theoret. comput. sci. 299 (2003) 751-761].
on approximate learning by multi-layered feedforward circuits. we deal with the problem of efficient learning of feedforward neural networks. first, we consider the objective to maximize the ratio of correctly classified points compared to the size of the training set. we show that it is np-hard to approximate the ratio within some constant relative error if architectures with varying input dimension, one hidden layer, and two hidden neurons are considered where the activation function in the hidden layer is the sigmoid function, and the situation of epsilon-separation is assumed, or the activation function is the semilinear function. for single hidden layer threshold networks with varying input dimension and n hidden neurons, approximation within a relative error depending on n is np-hard even if restricted to situations where the number of examples is limited with respect to n.afterwards, we consider the objective to minimize the failure ratio in the presence of misclassification errors. we show that it is np-hard to approximate the failure ratio within any positive constant for a multilayered threshold network with varying input dimension and a fixed number of neurons in the hidden layer if the thresholds of the neurons in the first hidden layer are zero. furthermore, even obtaining weak approximations is almost np-hard in the same situation.
(, )-coloring problems in line graphs. the (p, k)-coloring problems generalize the usual coloring problem by replacing stable sets by cliques and stable sets. complexities of some variations of (p, k)-coloring problems (split-coloring and cocoloring) are studied in line graphs; polynomial algorithms or proofs of np-completeness are given according to the complexity status. we show that the most general (p, k)-coloring problems are more difficult than the cocoloring and the split-coloring problems while there is no such relation between the last two problems. we also give complexity results for the problem of finding a maximum (p, k)-colorable subgraph in line graphs. finally, upper bounds on the optimal values are derived in general graphs by sequential algorithms based on welsh-powell and matula orderings.
on-line vertex-covering. we study the minimum vertex-covering problem under two on-line models corresponding to two different ways vertices are revealed. the former one implies that the input-graph is revealed vertex-by-vertex. the second model implies that the input-graph is revealed per clusters, i.e. per induced subgraphs of the final graph. under the cluster-model, we then relax the constraint that the choice of the part of the final solution dealing with each cluster has to be irrevocable, by allowing backtracking. we assume that one can change decisions upon a vertex membership of the final solution, this change implying, however, some cost depending on the number of the vertices changed.
a polynomial space construction of tree-like models for logics with local chains of modal connectives. the la-logics ("logics with local agreement") are polymodal logics defined semantically such that at any world of a model, the sets of successors for the different accessibility relations can be linearly ordered and the accessibility relations are equivalence relations. in a previous work, we have shown that every la-logic defined with a finite set of modal indices has an np-complete satisfiability problem. in this paper, we introduce a class of la-logics with a countably infinite set of modal indices and we show that the satisfiability problem is pspace-complete for every logic of such a class. the upper bound is shown by exhibiting a tree structure of the models. this allows us to establish a surprising correspondence between the modal depth of formulae and the number of occurrences of distinct modal connectives. more importantly, as a consequence, we can show the pspace-completeness of gargov's logic dalla and nakamura's logic lgm restricted to modal indices that are rational numbers, for which the computational complexity characterization has been open until now. these logics are known to belong to the class of information logics and fuzzy modal logics, respectively.
ltl over integer periodicity constraints. periodicity constraints are used in many logical formalisms, in fragments of presburger ltl, in calendar logics, and in logics for access control, to quote a few examples. in the paper, we introduce the logic pltlmod, an extension of linear-time temporal logic ltl with past-time operators whose atomic formulae are defined from a first-order constraint language dealing with periodicity. although the underlying constraint language is a fragment of presburger arithmetic shown to admit a pspace-complete satisfiability problem, we establish that pltlmod model-checking and satisfiability problems remain in pspace as plain ltl (full presburger ltl is known to be highly undecidable). this is particularly interesting for dealing with periodicity constraints since the language of pltlmod has a language more concise than existing languages and the temporalization of our first-order language of periodicity constraints has the same worst case complexity as the underlying constraint language. finally, we show examples of introduction the quantification in the logical language that provide to pltlmod, expspace-complete problems. as another application, we establish that the equivalence problem for extended single-string automata, known to express the equality of time granularities, is pspace-complete by designing a reduction from qbf and by using our results for pltlmod.
towards an algebraic theory of typed mobile processes. the impact of types on the algebraic theory of the π-calculus is studied. the type system has capability types. they allow one to distinguish between the ability to read from a channel, to write to a channel, and both to read and to write. they also give rise to a natural and powerful subtyping relation.two variants of typed bisimilarity are considered, both in their late and in their early version. for both of them, proof systems that are sound and complete on the closed finite terms are given. for one of the two variants, a complete axiomatisation for the open finite terms is also presented.
learning from positive and unlabeled examples. in many machine learning settings, labeled examples are difficult to collect while unlabeled data are abundant. also, for some binary classification problems, positive examples which are elements of the target concept are available. can these additional data be used to improve accuracy of supervised learning algorithms? we investigate in this paper the design of learning algorithms from positive and unlabeled data only. many machine learning and data mining algorithms, such as decision tree induction algorithms and naive bayes algorithms, use examples only to evaluate statistical queries (sq-like algorithms). kearns designed the statistical query learning model in order to describe these algorithms. here, we design an algorithm scheme which transforms any sq-like algorithm into an algorithm based on positive statistical queries (estimate for probabilities over the set of positive instances) and instance statistical queries (estimate for probabilities over the instance space). we prove that any class learnable in the statistical query learning model is learnable from positive statistical queries and instance statistical queries only if a lower bound on the weight of any, target concept f can be estimated in polynomial time. then, we design a decision tree induction algorithm posc4.5, based on c4.5, that uses only positive and unlabeled examples and we give experimental results for this algorithm. in the case of imbalanced classes in the sense that one of the two classes (say the positive class) is heavily underrepresented compared to the other class, the learning problem remains open. this problem is challenging because it is encountered in many real-world applications.
learning regular languages using rfsas. residual languages are important and natural components of regular languages and several grammatical inference algorithms naturally rely on this notion. in order to identify a given target language l, classical inference algorithms try to identify words which define identical residual languages of l. here, we study whether it could be interesting to perform a tighter analysis by identifying inclusion relations between the residual languages of l. we consider the class of residual finite state automata (rfsas). an rfsa a is a nondeterministic automaton whose states corresponds to residual languages of the language la it recognizes. the inclusion relations between residual languages of la can be naturally materialized on a. we prove that the class of rfsas is not polynomially characterizable. we lead some experiments which show that when a regular language is randomly drawn by using a nondeterministic representation, the number of inclusion relations between its residual languages is very important. moreover, its minimal rfsa representation is much smaller than its minimal dfa representation. finally, we design a new learning algorithm, delete2, based on the search for the inclusion relations between the residual languages of the target language. we give sufficient conditions for the identifiability of the target language. we experimentally compare the performance of delete2 to those of classical inference algorithms.
correctness of java card method lookup via logical relations. this article presents a formalisation of the bytecode optimisation of sun's java card language from the class file to cap file format as a set of constraints between the two formats, and defines and proves its correctness. java card bytecode is formalised using an abstract operational semantics, which can then be instantiated into the two formats. the optimisation is given as a logical relation such that the instantiated semantics are observably equal.
strategies for the renyi-ulam game with fixed number of lies. we consider the problem of finding the minimal number ll(m) of binary questions needed to find an unknown element of a set of cardinality m with a sequential strategy if at most l of the answers are lies. obviously, in the case l = 0 ⌈ log m ⌉ questions are needed. thus, one more question is necessary if the number of elements is doubled. we show that for every fixed l and sufficiently large m, then ll(2m) ≤ ll(m) + 2 and moreover ll(3/2m) ≤ ll(m)+ 1. these bounds are sharp in infinitely many cases. as a consequence, at most one question more than the information theoretic lower bound is needed to successfully find the unknown number. one of our strategies uses the minimum amount of adaptiveness during the search process.
abstract canonical presentations. solving goals--like proving properties, deciding word problems or resolving constraints--is much easier with some presentations of the underlying theory than with others. typically, what have been called "completion processes", in particular in the study of equational logic, involve finding appropriate presentations of a given theory to more easily solve a given class of problems.we provide a general proof-theoretic setting that relies directly on the fundamental concept of "good", that is, normal-form, proofs, itself defined using well-founded orderings on proof objects. this foundational framework allows for abstract definitions of canonical presentations and very general characterizations of saturation and redundancy criteria.