waashk/dblp huggingface dataset:
a strip-like tiling algorithm. we extend our previous results on the connection between strip tiling problems and regular grammars by showing that an analogous algorithm is applicable to other tiling problems, not necessarily related to rectangular strips. we find generating functions for monomer and dimer tilings of t- and l-shaped figures, holed and slotted strips, diagonal strips and combinations of them, and show how analogous results can be obtained by using different pieces.
a physicist's approach to number partitioning. the statistical physics approach to the number partioning problem, a classical np-hard problem, is both simple and rewarding. very basic notions and methods from statistical mechanics are enough to obtain analytical results for the phase boundary that separates the "easy-to-solve" from the "hard-to-solve" phase of the npp as well as for the probability distributions of the optimal and sub-optimal solutions. in addition, it can be shown that solving a number portioning problem of size n to some extent corresponds to locating the minimum in an unsorted list of o(2n ) numbers. considering this correspondence it is not surprising that known heuristics for the partitioning problem are not signi4cantly better than simple random search.
aspects of complexity of probabilistic learning under monotonicity constraints. in the setting of learning indexed families, probabilistic learning under monotonicity constraints is more powerful than deterministic learning under monotonicity constraints, even if the probability is close to 1, provided the learning machines are restricted to proper or class preserving hypothesis spaces (cf. meyer, theoret. comput. sci. 185 (1997) 81--128). in this paper, we investigate the relation between probabilistic learning and oracle identification under monotonicity constraints. in particular, we deal with the question how much additional information provided by oracles is necessary for compensating the additional power of probabilistic learning machines. in section 1, we show that k is necessary and sufficient to compensate the additional power of probabilistic learning machines in the case of conservative (monotonic) probabilistic learning with p > 1/2 (p > 2/3), and for strong-monotonic probabilistic learning with 1/2 < p &le; 2/3. in the case of strong-monotonic learning with p, however, every peano-complete oracle is sufficient for compensating the power of probabilistic learning machines. in contrast, the oracle k is not sufficient for compensating the power of conservative and strong-monotonic probabilistic learning with probability p=1/2, and monotonic probabilistic learning with p=2=3. the main result in section 2 is that for each oracle a &le; tk, there exists an indexed family la which is properly conservatively identifiable with p=1/2, and which exactly reflects the turing degree of a, i.e., la is properly conservatively identi/able by an oracle machine m[b] iff a&le;t b. thus, for every oracle a below k, we can construct a learning problem characterizing a within proper conservative learning. however, not every indexed family which is conservatively identifiable with probability p=1/2 reflects the turing degree of an oracle. hence, the conservative probabilistic learning classes are higher structured than the turing degrees below k. finally, we prove that there exist learning problems which are conservatively (monotonically) identifiable with probability p=1/2 (p=2/3), but conservatively (monotonically) identifiable only by oracle machines having access to tot. for strong-monotonic learning, this result does not hold. copyright 2001 elsevier science b.v. all rights reserved.
quantization of games: towards quantum artificial intelligence. we discuss the impact of quantum game theory on information processing and the emerging information society. the framework, that we establish, encompasses various particular models considered in the field of artificial intelligence. this paper provides insight into the following issues: detailed analysis of a quantum algorithm solving newcombs' paradox, the elitzur-vaidman circuit breaker and the metropolis algorithm is presented.
small turing machines and generalized busy beaver competition. let tm(k,l) be the set of one-tape turing machines with k states and l symbols. it is known that the halting problem is decidable for machines in tm(2,3) and tm(3,2). we prove that the decidability of machines in tm(2,4) and tm(3,3) will be difficult to settle, by giving machines in these sets for which the halting problem depends on an open problem in number theory. a machine in tm(5,2) with the same result is already known, and, moreover, this machine is the record holder for the busy beaver competitions: this is the machine in tm(5,2) which halts when starting from a blank tape, making the greatest number of steps and leaving the greatest number of non-blank symbols. we give potential winners for similar generalized busy beaver competitions in tm(2,3), tm(2,4) and tm(3,3).
interfaces as functors, programs as coalgebras - a final coalgebra theorem in intensional type theory. in [p. hancock, a. setzer, interactive programs in dependent type theory, in: p. clote, h. schwichtenberg (eds.), proc. 14th annu. conf. of eacsl, csl'00, fischbau, germany, 21-26 august 2000, vol. 1862, springer, berlin, 2000, pp. 317-331, url 〈citeseer.ist.psu.edu/article/hancock00interactive.html〉 p. hancock, a. setzer, interactive programs and weakly final coalgebras in dependent type theory, in: l. crosilla, p. schuster (eds.), from sets and types to topology and analysis. towards practicable foundations for constructive mathematics, oxford logic guides, clarendon press, 2005, url 〈www.cs.swan.ac.uk/~csetzer/〉] hancock and setzer introduced rules to extend martin-löf's type theory in order to represent interactive programming. the rules essentially reflect the existence of weakly final coalgebras for a general form of polynomial functor. the standard rules of dependent type theory allow the definition of inductive types, which correspond to initial algebras. coalgebraic types are not represented in a direct way. in this article we show the existence of final coalgebras in intensional type theory for these kind of functors, where we require uniqueness of identity proofs (uip) for the set of states s and the set of commands c which determine the functor. we obtain the result by identifying programs which have essentially the same behaviour, viz. are bisimular. this proves the rules of setzer and hancock admissible in ordinary type theory, if we replace definitional equality by bisimulation. all proofs [m. michelbrink, verifications of final coalgebra theorem in: interfaces as functors, programs as coalgebras-a final coalgebra theorem in intensional type theory, 2005, url 〈www.cs.swan.ac.uk/~csmichel/〉] are verified in the theorem prover agda [c. coquand, agda, internet, url 〈www.cs.chalmers.se/~catarina/agda/〉; k. peterson, a programming system for type theory, technical report, s-412 96, chalmers university of technology, göteborg, 1982], which is based on intensional martin-löf type theory.
combined super-/substring and super-/subsequence problems. super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. moreover we introduce different types of minimal superstring and maximal substring problems. in particular, we consider the following problems: given a set l of strings and a string s, (i) find a minimal superstring (or maximal substring) of l that is also a supersequence (or a subsequence) of s, (ii) find a minimal supersequence (or maximal subsequence) of l that is also a superstring (or a substring) of s. in addition some non-super-/non-substring and non-super-/nonsubsequence variants are studied. we obtain several np-hardness or even max snp-hardness results and also identify types of "weak minimal" superstrings and "weak maximal" substrings for which (i) is polynomial-time solvable.
a solution to the tennis ball problem. we present a complete solution to the so-called tennis ball problem, which is equivalent to counting the number of lattice paths in the plane that use north and east steps and lie between certain boundaries. the solution takes the form of explicit expressions for the corresponding generating functions.our method is based on the properties of tutte polynomials of matroids associated to lattice paths. we also show how the same method provides a solution to a wide generalization of the problem.
words and forbidden factors. given a finite or infinite word v, we consider the set m(v) of minimal forbidden factors of v. we show that the set m(v) is of fundamental importance in determining the structure of the word v. in the case of a finite word w we consider two parameters that are related to the size of m(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. we derive sharp upper and lower bounds for both parameters. we prove also that the second parameter is related to the minimal period of the word w. we are further interested to the algorithmic point of view. indeed, we design linear time algorithm for the following two problems: (i) given w, construct the set m(w) and, conversely, (ii) given m(w), reconstruct the word w. in the case of an infinite word x, we consider the following two functions: gx that counts, for each n, the allowed factors of x of length n and fx that counts, for each n, the minimal forbidden factors of x of length n. we address the following general problem: what information about the structure of x can be derived from the pair (gx,fx)? we prove that these two functions characterize, up to the automorphism exchanging the two letters, the language of factors of each single infinite sturmian word.
on fine and wilf's theorem for bidimensional words. generalizations of fine and wilf's periodicity theorem are obtained for the case of bidimensional words using geometric arguments. the domains considered constitute a large class of convex subsets of r2 which include most parallelograms. a complete discussion is provided for the parallelogram case.
language-theoretic aspects of dna complematarity. the optimism about the possibilities of dna computing is based on two central issues: the watson-crick complementarity and the massive parallelism of dna strands. while the latter issue renders exhaustive searches possible and thus may settle problems previously considered intractable, the former issue is the cause behind the universality of many models of dna computing. moreover, complementarity can be viewed as a purely language-theoretic operation: undesirable circumstances in a string trigger a transition to the complementary string. this aspect of complementarity is investigated in the present paper, mainly from the point of view of $l$ systems. new types of word sequences will be discovered. sometimes the resulting decision problems are equivalent to well-known open problems from other areas.
the complexity of makespan minimization for pipeline transportation. sptp is a model for the pipeline transportation of petroleum products. it uses a directed graph g, where arcs represent pipes and nodes represent locations. in this paper, we analyze the complexity of finding a minimum makespan solution to sptp. this problem is called sptmp. we prove that, for any fixed ε > 0, there is no η1-ε-approximate algorithm for the sptmp unless p = np, where η is the input size. this result also holds if g is both planar and acyclic. if g is acyclic, then we give a m-approximate algorithm to sptmp, where m is the number of arcs in g.
the category-theoretic solution of recursive program schemes. this paper provides a general account of the notion of recursive program schemes, studying both uninterpreted and interpreted solutions. it can be regarded as the category-theoretic version of the classical area of algebraic semantics. the overall assumptions needed are small indeed: working only in categories with "enough final coalgebras" we show how to formulate, solve, and study recursive program schemes. our general theory is algebraic and so avoids using ordered or metric structures. our work generalizes the previous approaches which do use this extra structure by isolating the key concepts needed to study substitution in infinite trees, including second-order substitution. as special cases of our interpreted solutions we obtain the usual denotational semantics using complete partial orders, and the one using complete metric spaces. our theory also encompasses implicitly defined objects which are not usually taken to be related to recursive program schemes. for example, the classical cantor two-thirds set falls out as an interpreted solution (in our sense) of a recursive program scheme.
on the cell probe complexity of polynomial evaluation. we consider the cell probe complexity of the polynomial evaluation problem with preprocessing of coefficients, for polynomials of degree at most n over a finite field k. we show that the trivial cell probe algorithm for the problem is optimal if k is sufficiently large compared to n. as an application, we give a new proof of the fact that p != ncr - time (o (log n/ log log n) ).
on converting cnf to dnf. we study how big the blow-up in size can be when one switches between the cnf and dnf representations of boolean functions. for a function f : {0, 1}n → {0, 1}, cnfsize(f) denotes the minimum number of clauses in a cnf for f; similarly, dnfsize(f) denotes the minimum number of terms in a dnf for f. for 0 ≤ m ≤ 2n-1, let dnfsize(m, n) be the maximum dnfsize(f) for a function f : {0, 1}n → {0, 1} with cnfsize(f) ≤ m. we show that there are constants c1, c2 ≥ 1 and ε > 0, such that for all large n and all m ∈ [ 1/ε n, 2εn], we have 2n-c1(n/log(m/n)) ≤ dnfsize(m, n) ≤ 2n-c2(n/log(m/n)). in particular, when m is the polynomial nc, we get dnfsize(nc, n) = 2n-θ(c-1(n/log n)).
a termination proof for epsilon substitution using partial derivations. epsilon substitution method introduced by hilbert is a successive approximation process providing numerical realizations from proofs of existential formulas. most convergence (termination) proofs for it use assignments of decreasing ordinals to stages of the process and work only for predicative systems. we describe a new ordinal assignment for the case of first-order arithmetic admitting extension to impredicative systems. it is based on an interpretation of individual epsilon substitutions forming the substitution process as incomplete finite proofs, each encoding a complete but infinite proof.
some results about the markov chains associated to gps and general eas. geiringer's theorem is a statement which tells us something about the limiting frequency of occurrence of a certain individual when a classical genetic algorithm is executed in the absence of selection and mutation. recently poll, stephens, wright and rowe extended the original theorem of geiringer to include the case of variable-length genetic algorithms and linear genetic programming. in the current paper a rather powerful finite population version of geiringer's theorem which has been established recently by mitavskiy is used to derive a schema-based version of the theorem for nonlinear genetic programming with homologous crossover. the theorem also applies in the presence of "node mutation". the corresponding formula in case when "node mutation" is present has been established.the limitation of the finite population geiringer result is that it applies only in the absence of selection. in the current paper we also observe some general inequalities concerning the stationary distribution of the markov chain associated to an evolutionary algorithm in which selection is the last (output) stage of a cycle. moreover we prove an "anti-communism" theorem which applies to a wide class of eas and says that for small enough mutation rate, the stationary distribution of the markov chain modelling the ea cannot be uniform.
a probabilistic polynomial-time process calculus for the analysis of cryptographic protocols. we prove properties of a process calculus that is designed for analysing security protocols. our long-term goal is to develop a form of protocol analysis, consistent with standard cryptographic assumptions, that provides a language for expressing probabilistic polynomial-time protocol steps, a specification method based on a compositional form of equivalence, and a logical basis for reasoning about equivalence.the process calculus is a variant of ccs, with bounded replication and probabilistic polynomial-time expressions allowed in messages and boolean tests. to avoid inconsistency between security and nondeterminism, messages are scheduled probabilistically instead of nondeterministically. we prove that evaluation of any process expression halts in probabilistic polynomial time and define a form of asymptotic protocol equivalence that allows security properties to be expressed using observational equivalence, a standard relation from programming language theory that involves quantifying over all possible environments that might interact with the protocol.we develop a form of probabilistic bisimulation and use it to establish the soundness of an equational proof system based on observational equivalences. the proof system is illustrated by a formation derivation of the assertion, well-known in cryptography, that el gamal encryption's semantic security is equivalent to the (computational) decision diffie-hellman assumption. this example demonstrates the power of probabilistic bisimulation and equational reasoning for protocol security.
on the complexity of finding a local maximum of functions on discrete planar subsets. we study how many values of an unknown integer-valued function f one needs to know in order to find a local maximum of f. we consider functions defined on finite subsets of discrete plane. we prove upper bounds for functions defined on rectangles and present lower bounds for functions defined on arbitrary domains in terms of the size of the domain and the size of its border.
ternary directed acyclic word graphs. given a set s of strings, a dfa accepting s offers a very time-efficient solution to the pattern matching problem over s. the key is how to implement such a dfa in the trade-off between time and space, and especially the choice of how to implement the transitions of each state is critical. bentley and sedgewick proposed an effective tree structure called ternary trees. the idea of ternary trees is to 'implant' the process of binary search for transitions into the structure of the trees themselves. this way the process of binary search becomes visible, and the implementation of the trees becomes quite easy. the directed acyelic word graph (dawg) of a string w is the smallest dfa that accepts all suffixes of w, and requires only linear space. we apply the scheme of ternary trees to dawgs, introducing a new data structure named ternary dawgs (tdawgs). furthermore, the scheme of avl trees is applied to the tdawgs, yielding a more time-efficient structure avl tdawgs. we also perform some experiments that show the efficiency of tdawgs and avl tdawgs, compared to dawgs in which transitions are implemented by linked lists.
algebras of modal operators and partial correctness. modal kleene algebras are kleene algebras enriched by forward and backward box and diamond operators. we formalise the symmetries of these operators as galois connections, complementarities and dualities. we study their properties in the associated operator algebras and show that the axioms of relation algebra are theorems at the operator level. modal kleene algebras provide a unifying semantics for various program calculi and enhance efficient cross-theory reasoning in this class, often in a very concise pointfree style. this claim is supported by novel algebraic soundness and completeness proofs for hoare logic and by connecting this formalism with an algebraic decision procedure.
two-sorted metric temporal logics. temporal logic has been successfully used for modeling and analyzing the behavior of reactive and concurrent systems.one shortcoming of (standard) temporal logic is that it is inadequate for real-time applications, because it only deals with qualitative timing properties.this is overcome by metric temporal logics which offer a uniform logical framework in which both qualitative and quantitative timing properties can be expressed by making use of a parameterized operator of relative temporal realization. in this paper we deal with completeness issues for basic systems of metric temporal logic --- despite their relevance, such issues have been ignored or only partially addressed in the literature.we view metric temporal logics as two-sorted formalisms having formulae ranging over time instants and parameters ranging over an (ordered) abelian group of temporal displacements.we first provide an axiomatization of the pure metric fragment of the logic, and prove its soundness and completeness.then, we show how to obtain the metric temporal logic of linear orders by adding an ordering over displacements.finally, we consider general metric temporal logic allowing quantification over algebraic variables and free mixing of algebraic formulae and temporal propositional symbols.
set of periods of additive cellular automata. it is shown that the set of periods of any additive cellular automata f, where the addition is done modulo a prime p, can be determined using some simple conditions on the coefficients in the linear expression of f. in particular, we establish that the set of periods has only four possibilities: {1, m} for some m where 1 ≤ m < p, n\{pm : m ∈ n}, n\{2pm : m ∈ n ∪ {0}} or the whole set n = {1,2,3,...}. using our results, the set of periods of any additive cellular automata, where the addition is done modulo a square-free positive integer, is easily obtained.
universality and decidability of number-conserving cellular automata. number-conserving cellular automata (ncca) are particularly interesting, both because of their natural appearance as models of real systems, and because of the strong restrictions that number-conservation implies. here we extend the definition of the property to include cellular automata with any set of states in z, and show that they can be always extended to "usual" ncca with contiguous states. we show a way to simulate any one dimensional ca through a one-dimensional ncca, proving the existence of intrinsically universal ncca. finally, we give an algorithm to decide, given a ca, if its states can be labeled with integers to produce a ncca, and to find this relabeling if the answer is positive.
on conservative and monotone one-dimensional cellular automata and their particle representation. number-conserving (or conservative) cellular automata (ca) have been used in several contexts, in particular traffic models, where it is natural to think about them as systems of interacting particles. in this article we consider several issues concerning one-dimensional cellular automata which are conservative, monotone (specially "non-increasing"), or that allow a weaker kind of conservative dynamics. we introduce a formalism of "particle automata", and discuss several properties that they may exhibit, some of which, like anticipation and momentum preservation, happen to be intrinsic to the conservative ca they represent. for monotone ca we give a characterization, and then show that they too are equivalent to the corresponding class of particle automata. finally, we show how to determine, for a given ca and a given integer b, whether its states admit a b-neighborhood-dependent relabeling whose sum is conserved by the ca iteration; this can be used to uncover conservative principles and particle-like behavior underlying the dynamics of some ca. compliments at http://www.dim.uchile.cl/~anmoreir/ncca