waashk/dblp huggingface dataset:
physical constraints on hypercomputation. many attempts to transcend the fundamental limitations to computability implied by the halting problem for turing machines depend on the use of forms of hypercomputation that draw on notions of infinite or continuous, as opposed to bounded or discrete, computation. thus, such schemes may include the deployment of actualised rather than potential infinities of physical resources, or of physical representations of real numbers to arbitrary precision. here, we argue that such bases for hypercomputation are not materially realisable and so cannot constitute new forms of effective calculability.
bounding lemmata for non-deterministic halting times of transfinite turing machines. we use the methods of descriptive set theory and generalized recursion theory to prove various bounding lemmata that contribute to a body of results on halting times of non-deterministic infinite time turing machine computations. in particular we observe that there is a uniform bounding lemma which states that if any total algorithm halts before the first ordinal admissible in the input x, then there is a recursive ordinal @c by which the algorithm halts on all inputs.
cryptographic logical relations. using contextual equivalence (a.k.a. observational equivalence) to specify security properties is an important idea in the field of formal verification of cryptographic protocols. while contextual equivalence is difficult to prove directly, one is usually able to deduce it using the so-called logical relations in typed @l-calculi. we apply this technique to the cryptographic metalanguage-an extension of moggi's computational @l-calculus, where we use stark's model for name creation to explore the difficult aspect of dynamic key generation. the categorical construction of logical relations for monadic types (by goubault-larrecq et al.) then allows us to derive logical relations over the category set^i. although set^i is a perfectly adequate model of dynamic key generation, it lacks in some aspects when we study relations between programs in the metalanguage. this leads us to an interesting exploration of what should be the proper category to consider. we show that, to define logical relations in the cryptographic metalanguage, a better choice of category is set^i^^^-> that we proposed in [y. zhang, d. nowak, logical relations for dynamic name creation, in: proceedings of the 17th international workshop of computer science logic and the 8th kurt godel colloqium, csl & kgl, in: lecture notes in computer science, vol. 2803, springer-verlag, 2003, pp. 575-588]. however, this category is still lacking in some subtler aspects and we propose a refined category set^p^i^^^-> to fix the flaws, but our final choice is set^i^x^i, which is equivalent to set^p^i^^^->. we define the contextual equivalence based on set^i^x^i and show that the cryptographic logical relation derived over set^i^x^i is sound and can be used to verify protocols in practice.
a graphical criterion of planarity for rna secondary structures with pseudoknots in rivas-eddy class. an rna secondary structure is considered to be planar if its arc graph can be embedded into a plane without edge crossing. in this paper, a graphical criterion of planarity is presented based on graphical composition for rna secondary structures with pseudoknots in rivas-eddy class. effective planar testing algorithms are introduced based on our graphical criterion.
multi-break rearrangements and chromosomal evolution. most genome rearrangements (e.g., reversals and translocations) can be represented as 2-breaks that break a genome at 2 points and glue the resulting fragments in a new order. multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. while multi-break rearrangements were studied in depth for k=2 breaks, the k-break distance problem for arbitrary k remains unsolved. we prove a duality theorem for multi-break distance problem and give a polynomial algorithm for computing this distance.
compositional semantics and behavioral equivalences for p systems. the aim of the paper is to give a compositional semantics in the style of the structural operational semantics (sos) and to study behavioral equivalence notions for p systems. firstly, we consider p systems with maximal parallelism and without priorities. we define a process algebra, called p algebra, whose terms model membranes, we equip the algebra with a labeled transition system (lts) obtained through sos transition rules, and we study how some equivalence notions defined over the lts model apply in our case. then, we consider p systems with priorities and extend the introduced framework to deal with them. we prove that our compositional semantics reflects correctly maximal parallelism and priorities.
property matching and weighted matching. in many pattern matching applications the text has some properties attached to its various parts. pattern matching with properties (property matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property. some immediate examples come from molecular biology where it has long been a practice to consider special areas in the genome by their structures. it is straightforward to do sequential matching in a text with properties. however, indexing in a text with properties becomes difficult if we desire the time to be output dependent. we present an algorithm for indexing a text with properties in o(nlog|@s|+nloglogn) time for preprocessing and o(|p|log|@s|+tocc"@p) per query, where n is the length of the text, p is the sought pattern, @s is the alphabet, and tocc"@p is the number of occurrences of the pattern that satisfy some property @p. as a practical use of property matching we show how to solve weighted matching problems using techniques from property matching. weighted sequences have recently been introduced as a tool to handle a set of sequences that are not identical but have many local similarities. the weighted sequence is a ''statistical image'' of this set, where we are given the probability of every symbol's occurrence at every text location. weighted matching problems are pattern matching problems where the given text is weighted. we present a reduction from weighted matching to property matching that allows off-the-shelf solutions to numerous weighted matching problems including indexing, swapped matching, parameterized matching, approximate matching, and many more. assuming that one seeks the occurrence of pattern p with probability @e in weighted text t of length n, we reduce the problem to a property matching problem of pattern p in text t^' of length o(n(1@e)^2log1@e).
computation of distances for regular and context-free probabilistic languages. several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. in most cases, only pairs of probabilistic regular languages were considered. in this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.
counting suffix arrays and strings. suffix arrays are used in various applications and research areas like data compression or computational biology. in this work, our goal is to characterise the combinatorial properties of suffix arrays and their enumeration. for a fixed alphabet size and string length, we divide the set of all strings into equivalence classes of strings that share the same suffix array. for each such equivalence class, we count the number of strings contained in it. we also give exact formulas for computing the number of equivalence classes. our methods yield a lower bound for the compressibility of suffix arrays and build the foundation for the efficient generation of appropriate test data sets for suffix array based algorithms. we also show that summing up the elements of all equivalence classes forms a particular instance for some summation identities of eulerian numbers.
solving np-complete problems in the tile assembly model. formalized study of self-assembly has led to the definition of the tile assembly model, a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the internet. previously, i defined deterministic and nondeterministic computation in the tile assembly model and showed how to add, multiply and factor. here, i extend the notion of computation to include deciding subsets of the natural numbers, and present a system that decides subsetsum, a well-known np-complete problem. the computation is nondeterministic and each parallel assembly executes in time linear in the input. the system requires only a constant number of different tile types: 49. i describe mechanisms for finding the successful solutions among the many parallel assemblies and explore bounds on the probability of such a nondeterministic system succeeding and prove that probability can be made arbitrarily close to one.
detection of subtle variations as consensus motifs. we address the problem of detecting consensus motifs, that occur with subtle variations, across multiple sequences. these are usually functional domains in dna sequences such as transcriptional binding factors or other regulatory sites. the problem in its generality has been considered difficult and various benchmark data serve as the litmus test for different computational methods. we present a method centered around unsupervised combinatorial pattern discovery. the parameters are chosen using a careful statistical analysis of consensus motifs. this method works well on the benchmark data and is general enough to be extended to a scenario where the variation in the consensus motif includes indels (along with mutations). we also present some results on detection of transcription binding factors in human dna sequences.
computing similarity of run-length encoded strings with affine gap penalty. the problem of computing the similarity of two run-length encoded strings has been studied for various scoring metrics. many algorithms have been developed for the longest common subsequence metric and some algorithms for the levenshtein distance metric and the weighted edit distance metric. in this paper we consider similarity based on the affine gap penalty metric which is a more general and rather complicated scoring metric than the weighted edit distance. to compute the similarity in this model efficiently, we convert the problem into a path problem on a directed acyclic graph and use some properties of maximum paths in this graph. we present an o(nm^'+n^'m) time algorithm for computing the similarity of two run-length encoded strings in the affine gap penalty model, where n and m are the lengths of given two strings whose run-length encoded lengths are n^' and m^', respectively.
sequential vs. parallel complexity in simple gene assembly. we investigate some differences between the general intramolecular model for gene assembly and its restricted simple model. although both models satisfactorily sort all current experimental data, we show that the general model offers assembly strategies for a given string that vary in both assembly length and the operations used, while the simple model will always use the same number of each type of operation to sort a gene. when simple operations are applied in parallel this is given a new twist. we prove that for any n>=1, there exists a string having maximally parallel assemblies of any length between n and 2n.
reversible computing and cellular automata - a survey. reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of nature. in this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. we shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. we discuss these problems based on reversible logic elements/circuits, reversible turing machines, reversible cellular automata, and some other related models of reversible computing.
fast profile matching algorithms - a survey. position-specific scoring matrices are a popular choice for modelling signals or motifs in biological sequences, both in dna and protein contexts. a lot of effort has been dedicated to the definition of suitable scores and thresholds for increasing the specificity of the model and the sensitivity of the search. it is quite surprising that, until very recently, little attention has been paid to the actual process of finding the matches of the matrices in a set of sequences, once the score and the threshold have been fixed. in fact, most profile matching tools still rely on a simple sliding window approach to scan the input sequences. this can be a very time expensive routine when searching for hits of a large set of scoring matrices in a sequence database. in this paper we will give a survey of proposed approaches to speed up profile matching based on statistical significance, multipattern matching, filtering, indexing data structures, matrix partitioning, fast fourier transform and data compression. these approaches improve the expected searching time of profile matching, thus leading to implementation of faster tools in practice.
algorithms for computing variants of the longest common subsequence problem. the longest common subsequence (lcs) problem is one of the classical and well-studied problems in computer science. the computation of the lcs is a frequent task in dna sequence analysis, and has applications to genetics and molecular biology. in this paper we introduce new variants of lcs problem and present efficient algorithms to solve them. in particular we introduce the notion of gap constraints in the lcs problems. for the lcs problem with fixed gap, we first present a naive algorithm runs in o(n^2+r(k+1)^2) time, where r is the total number of ordered pairs of positions at which the two strings match and k is the fixed gap constraint. we then improve the running time to o(n^2+rk+rloglogn) using some novel techniques. furthermore, we present an algorithm that is independent of k and runs in o(n^2+rloglogn) time. using these techniques, we also present a new o(n^2) algorithm to solve the original lcs problem. additionally, we modify our algorithms to handle elastic and rigid gaps. we also apply the notion of rigidness to the original lcs problem and modify the traditional dynamic programming solution to handle the rigidness presenting a o(n^2) algorithm to solve the problem. finally, we also improve the solution to rigid fixed gap lcs to o(n^2). notably, in all of the above cases, we assume that the two given strings are of equal length i.e. n. but our results can be easily extended to handle two strings of different length.
nondeterministic polynomial time factoring in the tile assembly model. formalized study of self-assembly has led to the definition of the tile assembly model, previously i presented ways to compute arithmetic functions, such as addition and multiplication, in the tile assembly model: a highly distributed parallel model of computation that may be implemented using molecules or a large computer network such as the internet. here, i present tile assembly model systems that factor numbers nondeterministically using @q(1) distinct components. the computation takes advantage of nondeterminism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. i describe mechanisms for finding the successful solutions among the many parallel executions and explore bounds on the probability of such a nondeterministic system succeeding and prove that the probability can be made arbitrarily close to 1.
modeling spiking neural networks. a notation for the functional specification of a wide range of neural networks consisting of temporal or non-temporal neurons, is proposed. the notation is primarily a mathematical framework, but it can also be illustrated graphically and can be extended into a language in order to be automated. its basic building blocks are processing entities, finer grained than neurons, connected by instant links, and as such they form sets of interacting entities resulting in bigger and more sophisticated structures. the hierarchical nature of the notation supports both top-down and bottom-up specification approaches. the use of the notation is evaluated by a detailed example of an integrated tangible agent consisting of sensors, a computational part, and actuators. a process from specification to both software and hardware implementation is proposed.
on the entropy of a hidden markov process. we study the entropy rate of a hidden markov process (hmp) defined by observing the output of a binary symmetric channel whose input is a first-order binary markov process. despite the simplicity of the models involved, the characterization of this entropy is a long standing open problem. by presenting the probability of a sequence under the model as a product of random matrices, one can see that the entropy rate sought is equal to a top lyapunov exponent of the product. this offers an explanation for the elusiveness of explicit expressions for the hmp entropy rate, as lyapunov exponents are notoriously difficult to compute. consequently, we focus on asymptotic estimates, and apply the same product of random matrices to derive an explicit expression for a taylor approximation of the entropy rate with respect to the parameter of the binary symmetric channel. the accuracy of the approximation is validated against empirical simulation results. we also extend our results to higher-order markov processes and to renyi entropies of any order.
approximating the 2-interval pattern problem. we address the issue of approximating the 2-interval pattern problem over its various models and restrictions. this problem, motivated by rna secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints. we present several constant factor approximation algorithms whose performance guarantee depends on the different possible restrictions imposed on the input 2-interval set. in addition, we show that our results extend to the weighted variant of the problem.
partitioned probe comparability graphs. given a class of graphs g, a graph g is a probe graph of g if its vertices can be partitioned into a set of probes and an independent set of nonprobes such that g can be embedded into a graph of g by adding edges between certain nonprobes. if the partition of the vertices is part of the input, we call g a partitioned probe graph of g. in this paper we show that there exists a polynomial-time algorithm for the recognition of partitioned probe graphs of comparability graphs. this immediately leads to a polynomial-time algorithm for the recognition of partitioned probe graphs of cocomparability graphs. we then show that a partitioned graph g is a partitioned probe permutation graph if and only if g is at the same time a partitioned probe graph of comparability and cocomparability graphs.
on approximate optimal dual power assignment for biconnectivity and edge-biconnectivity. topology control is one of the major approaches to achieve energy efficiency as well as fault tolerance in wireless networks. in this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model. the problem has arisen from the following practical origin. in a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerant connected network topology in the most energy-efficient way? specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity. note that to achieve a minimum number of high-power nodes is harder than an optimization problem in the same model whose objective is to minimize the total power cost. we first address these two optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model. due to the np-hardness, we propose an approximation algorithm, called prioritized edge selection algorithm, which achieves a 4-ratio approximation for 2-edge connectivity. after that, we modify the algorithm to solve the problem for 2-vertex connectivity and also achieve the same approximation ratio. we also show that the 4-ratio is tight for our algorithms in both cases.
on a quasi-ordering on boolean functions. it was proved few years ago that classes of boolean functions definable by means of functional equations [o. ekin, s. foldes, p.l. hammer, l. hellerstein, equational characterizations of boolean functions classes, discrete mathematics 211 (2000) 27-51], or equivalently, by means of relational constraints [n. pippenger. galois theory for minors of finite functions, discrete mathematics 254 (2002) 405-419], coincide with initial segments of the quasi-ordered set (@w,@?) made of the set @w of boolean functions, suitably quasi-ordered. furthermore, the classes defined by finitely many equations [o. ekin, s. foldes, p.l. hammer, l. hellerstein, equational characterizations of boolean functions classes, discrete mathematics 211 (2000) 27-51] coincide with the initial segments of (@w,@?) which are definable by finitely many obstructions. the resulting ordered set (@w@?,@?) embeds into ([@w]^
weak-vertex-pancyclicity of (n, k)-star graphs. the (n,k)-star graph (s"n","k for short) is an attractive alternative to the hypercube and also a generalized version of the n-star. it is isomorphic to the n-star (n-complete) graph if k=n-1 (k=1). jwo et al. have already demonstrated in 1991 that an n-star contains a cycle of every even length from 6 to n!. this work shows that every vertex in an s"n","k lies on a cycle of length l for every 3@?l@?n!/(n-k)! when 1@?k@?n-4 and n>=6. additionally, for n-3@?k@?n-2, each vertex in an s"n","k is contained in a cycle of length ranged from 6 to n!/(n-k)!. moreover, each constructed cycle of an available length in an s"n","k can contain a desired 1-edge.
tight bounds for the multiplicative complexity of symmetric functions. the multiplicative complexity of a boolean function f is defined as the minimum number of binary conjunction (and) gates required to construct a circuit representing f, when only exclusive-or, conjunction and negation gates may be used. this article explores in detail the multiplicative complexity of symmetric boolean functions. new techniques that allow such exploration are introduced. they are powerful enough to give exact multiplicative complexities for several classes of symmetric functions. in particular, the multiplicative complexity of computing the hamming weight of n bits is shown to be exactly n-h^n(n), where h^n(n) is the hamming weight of the binary representation of n. we also show a close relationship between the complexities of basic symmetric functions and the fractal known as sierpinski's gasket.