waashk/dblp huggingface dataset:
a polynomial algorithm for deciding bisimilarity of normed context-free processes. the previous best upper bound on the complexity of deciding bisimilarity between normed context-free processes, due to huynh and tian, is that the problem lies in the second level of the polynomial hierarchy: their algorithm guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in np. in this paper we improve on this result by presenting a polynomial-time algorithm which solves this problem. as a corollary, we have a polynomial algorithm for the equivalence problem for simple context-free grammars.
computing with quanta - impacts of quantum theory on computation. this is a survey article to quantum computing. we begin with a brief introduction on the theory of computing and represent the hilbert space formalism of quantum physics. we study some devices for quantum computing, and finally mention some important achievements and restrictions of quantum computing.
max3sat is exponentially hard to approximate if np has positive dimension. under the hypothesis that np has positive p-dimension, we prove that any approximation algorithm a for max3sat must satisfy at least one of the following: 1. for some δ > 0, a uses at least 2nδ time. 2. for all ε > 0, a has performance ratio less than 7/8 + ε on an exponentially dense set of satisfiable instances. as a corollary, this solves one of lutz and mayordomo's "twelve problems on resource-bounded measure" (bull. european assoc. theoret. comput. sci. 68 (1999) 64-80).
the size of spp. derandomization techniques are used to show that at least one of the following holds regarding the size of the counting complexity class spp: 1. µp(spp)=0. 2. ph ⊆ spp. in other words, spp is small by being a negligible subset of exponential time or large by containing the entire polynomial-time hierarchy. this addresses an open problem about the complexity of the graph isomorphism problem: it is not weakly complete for exponential time unless ph is contained in spp. it is also shown that the polynomial-time hierarchy is contained in sppnp if np does not have p-measure 0.
hausdorff dimension and oracle constructions. bennett and gill [relative to a random oracle a, pa ≠ npa ≠ co-npa with probability 1, siam j. comput. 10 (1981) 96-113] proved that pa ≠ npa relative to a random oracle a, or in other words, that the set o[p=np] = {a | pa = npa} has lebesgue measure 0. in contrast, we show that o[p=np] has hausdorff dimension 1.this follows from a much more general theorem: if there is a relativizable and paddable oracle construction for a complexity-theoretic statement φ, then the set of oracles relative to which φ holds has hausdorff dimension 1.we give several other applications including proofs that the polynomial-time hierarchy is infinite relative to a hausdorff dimension 1 set of oracles and that pa ≠ npa ∩ conpa relative to a hausdorff dimension 1 set of oracles.
distribution of a class of divide and conquer recurrences arising from the computation of the walsh-hadamard transform. this paper explores the performance of a family of algorithms for computing the walsh-hadamard transform, a useful computation in signal and image processing. recent empirical work has shown that the family of algorithms exhibit a wide range of performance and that it is non-trivial to determine which algorithm is optimal on a given computer. this paper provides a theoretical basis for the performance distribution. performance is modeled by a family of recurrence relations that determine the number of instructions required to execute a given algorithm, and the recurrence relations can be used to explore the performance of the space of algorithms. the recurrence relations are related to standard divide and conquer recurrences, however, there are a variable number of recursive parts which can grow to infinity as the input size increases. thus standard approaches to solving such recurrences cannot be used and new techniques must be developed. in this paper, the minimum, maximum, expected values, and variances are calculated and the limiting distribution is obtained.
generalized metrics and uniquely determined logic programs. the introduction of negation into logic programming brings the benefit of enhanced syntax and expressibility, but creates some semantical problems. specifically, certain operators which are monotonic in the absence of negation become non-monotonic when it is introduced, with the result that standard approaches to denotational semantics then become inapplicable. in this paper, we show how generalized metric spaces can be used to obtain fixed-point semantics for several classes of programs relative to the supported model semantics, and investigate relationships between the underlying spaces we employ. our methods allow the analysis of classes of programs which include the acyclic, locally hierarchical, and acceptable programs, amongst others, and draw on fixed-point theorems which apply to generalized ultrametric spaces and to partial metric spaces.
the algebra of binary search trees. we introduce a monoid structure on the set of binary search trees, by a process very similar to the construction of the plactic monoid, the robinson-schensted insertion being replaced by the binary search tree insertion. this leads to a new construction of the algebra of planar binary trees of loday-ronco, defining it in the same way as non-commutative symmetric functions and free symmetric functions. we briefly explain how the main known properties of the loday-ronco algebra can be described and proved with this combinatorial point of view, and then discuss it from a representation theoretical point of view, which in turns leads to new combinatorial properties of binary trees.
trees, grids, and mso decidability: from graphs to matroids. monadic second order (mso) logic has proved to be a useful tool in many areas of application, reaching flom decidability and complexity to picture processing, correctness of programs and parallel processes. to characterize the structural borderline between decidability and undecidability is a classical research problem here. this problem is related to questions in computational complexity, especially to the model checking problem, for which many tools developed in the area of decidability have proved to be useful for more than two decades it was conjectured in [d. seese, the structure of the models of decidable monadic theories of graphs, ann. pure appl. logic 53 (1991) 169-195] that decidability of monadic theories of countable structures implies that the theory can be reduced via interpretability to a theory of trees.it is one of the main goals of this article to prove a variant of this conjecture for matroids representable over a finite field. (matroids can be viewed as a wide generalization of graphs, and they seem to capture some second order properties in a more suitable way than graphs themselves, cf. the recent development in matroid structure theory [j.f. geelen, a.h.m. gerards, g.p. whittle, branch-width and well-quasi-ordering in matroids and graphs, j. combin. theory ser. b 84 (2002) 270-290; j.f. geelen, a.h.m. gerards, n. robertson, g.p. whittle, excluding a planar graph from a gf(q)-representable matroid, manuscript, 2003].) more exactly we prove, for every finite field f, that any class of f-representable matroids with a decidable mso theory must have uniformly bounded branch-width. moreover, we show that bounding the branch-width of all matroids in general is not sufficient to obtain a decidable mso theory.our paper gives a (rather detailed) introduction to these different subjects, and shows that a blend of ideas and methods from logic together with structural matroid theory can lead to new tools and algorithms, and can shed light on some old open problems.
deterministic parallel backtrack search. the backtrack search problem involves visiting all the nodes of an arbitrary binary tree given a pointer to its root subject to the constraint that the children of a node are revealed only after their parent is visited. we present a fast, deterministic backtrack search algorithm for a p-processor common crcw-pram, which visits any n-node tree of height h in time o((n/p+h)(logloglogp)22). this upper bound compares favourably with a natural &ohgr;(n/p+h) lower bound for this problem. our approach embodies novel, efficient techniques for dynamically assigning tree-nodes to processors to ensure that the work is shared equitably among them.
a classification of wait-free loop agreement tasks. loop agreement is a family of wait-free tasks that includes instances of set agreement and approximate agreement tasks. a task g implements task f if one can construct a solution to f from a solution to g, possibly followed by access to a read/write memory. loop agreement tasks form a lattice under this notion of implementation.this paper presents a classification of loop agreement tasks. each loop agreement task can be assigned an algebraic signature consisting of a finitely presented group g and a distinguished element g in g. this signature characterizes the task's power to implement other tasks. if f and g are loop agreement tasks with respective signatures 〈f,f〉 and 〈g,g〉, then f implements g if and only if there exists a group homomorphism h : f → g carrying f to g.
the complexity of the characteristic and the minimal polynomial. we investigate the complexity of (1) computing the characteristic polynomial, the minimal polynomial, and all the invariant factors of an integer matrix, and of (2) verifying them, when the coefficients are given as input.it is known that each coefficient of the characteristic polynomial of a matrix a is computable in gapl, and the constant term, the determinant of a, is complete for gapl. we show that the verification of the characteristic polynomial is complete for complexity class c=l (exact counting logspace).we show that each coefficient of the minimal polynomial of a matrix a can be computed in ac0(gapl), the ac0-closure of gapl, and there is a coefficient which is hard for gapl. furthermore, the verification of the minimal polynomial is in ac0(c=l) and is hard for c=l. the hardness result extends to (computing and verifying) the system of all invariant factors of a matrix.
process algebra for performance evaluation. this paper surveys the theoretical developments in the field of stochastic process algebras, process algebras where action occurrences may be subject to a delay that is determined by a random variable. a huge class of resource-sharing systems - like large-scale computers, client-server architectures, networks - can accurately be described using such stochastic specification formalisms. the main emphasis of this paper is the treatment of operational semantics, notions of equivalence, and (sound and complete) axiomatisations of these equivalences for different types of markovian process algebras, where delays are governed by exponential distributions. starting from a simple actionless algebra for describing time-homogeneous continuous-time markov chains, we consider the integration of actions and random delays both as a single entity (like in known markovian process algebras like tipp, pepa and empa) and as separate entities (like in the timed process algebras timed csp and tccs). in total we consider four related calculi and investigate their relationship to existing markovian process algebras. we also briefly indicate how one can profit from the separation of time and actions when incorporating more general, non-markovian distributions.
paracategories i: internal paracategories and saturated partial algebras. based on the monoid classifier δ, we give an alternative axiomatization of freyd's paracategories, which can be interpreted in any bicategory of partial maps. assuming furthermore a free-monoid monad t in our ambient category, and coequalisers satisfying some exactness conditions, we give an abstract envelope construction, putting paramonoids (and paracategories) in the more general context of partial algebras. we introduce for the latter the crucial notion of saturation, which characterises those partial algebras which are isomorphic to the ones obtained from their enveloping algebras. we also set up a factorisation system for partial algebras, via epimorphisms and (monic) kleene morphisms and relate the latter to saturation.
paracategories ii: adjunctions, fibrations and examples from probabilistic automata theory. in this sequel to hermida and mateus (paracategories i: internal paracategories and saturated partial algebras, theoret. comput. sci., in press), we explore some of the global aspects of the category of paracategories. we establish its (co)completeness and cartesian closure. from the closed structure we derive the relevant notion of transformation for paracategories. we set up the relevant notion of adjunction between paracategories and apply it to define (co)completeness and cartesian closure, exemplified by the paracategory of bivariant functors and dinatural transformations. we introduce partial multicategories to account for partial tensor products. we also consider fibrations for paracategories and their indexed-paracategory version. finally, we instantiate all these concepts in the context of probabilistic automata.
a complexity analysis of functional interpretations. we give a quantitative analysis of gödel's functional interpretation and its monotone variant. the two have been used for the extraction of programs and numerical bounds as well as for conservation results. they apply both to (semi-)intuitionistic as well as (combined with negative translation) classical proofs. the proofs may be formalized in systems ranging from weak base systems to arithmetic and analysis (and numerous fragments of these). we give upper bounds in basic proof data on the depth, size, maximal type degree and maximal type arity of the extracted terms as well as on the depth of the verifying proof. in all cases terms of size linear in the size of the proof at input can be extracted and the corresponding extraction algorithms have cubic worst-time complexity. the verifying proofs have depth linear in the depth of the proof at input and the maximal size of a formula of this proof.
computations with effective real numbers. a real number x is said to be effective if there exists an algorithm which, given a required tolerance ε ∈ z2z, returns a binary approximation x˜ ∈, z2z for x with |x˜-x| < ε. effective real numbers are interesting in areas of numerical analysis where numerical instability is a major problem.one key problem with effective real numbers is to perform intermediate computations at the smallest precision which is sufficient to guarantee an exact end-result. in this paper we first review two classical techniques to achieve this: a priori error estimates and interval analysis. we next present two new techniques: "relaxed evaluations" reduce the amount of re-evaluations at larger precisions and "balanced error estimates" automatically provide good tolerances for intermediate computations.
a universal cellular automaton in the hyperbolic plane. the paper gives the construction of a universal ca with 22 states in the regular rectangular pentagonal grid of the hyperbolic plane. the ca implements a railway circuit which simulates a register machine and which improves a bit already known railway simulations of a turing machine.
deleting string rewriting systems preserve regularity. a string rewriting system is called deleting if there exists a partial ordering on its alphabet such that each letter in the right-hand side of a rule is less than some letter in the corresponding left-hand side. we show that the rewrite relation induced by a deleting system can be represented as the composition of a finite substitution (into an extended alphabet), a rewrite relation of an inverse context-free system (over the extended alphabet), and a restriction (to the original alphabet). here, a system is called inverse context-free if the length of the right-hand side of any rule does not exceed one. the decomposition result directly implies that deleting systems preserve regularity and that inverse deleting systems preserve context-freeness. the latter result was already obtained by hibbard (j. acm 21(3) (1974) 446-453).
a computational interpretation of dolev-yao adversaries. the dolev-yao model is a simple and useful framework in which to analyze security protocols, but it assumes that the adversary is extremely limited. we show that it is possible for the results of this model to remain valid even if the adversary is given additional power. in particular, we show that there exist situations in which dolev-yao adversary can be viewed as a valid abstraction of all realistic adversaries. we do this in a number of steps: (1) the dolev-yao model places strong assumptions on the adversary. we capture those assumptions in the computational model (an alternate framework with a very powerful adversary) as a nonmalleability property of public-key encryption. (2) we prove an abadi-rogaway-style indistinguishability property (j. cryptol. 15(2) (2002) 103-127) for the public-key setting. that is, we show that if two dolev-yao expressions are indistinguishable to the dolev-yao adversary, then their computational interpretations (via a chosen-ciphertext secure encryption scheme) are computationally indistinguishable. (3) we show that any encryption scheme that satisfies the indistinguishability property also satisfies our (more natural) non-malleability property.
realizability models for bll-like languages. we give a realizability model of girard-scedrov-scott's bounded linear logic (bll). this gives a new proof that all numerical functions representable in that system are polytime. our analysis naturally justifies the design of the bll syntax and suggests further extensions.
graph traversal and graph transformation. graph traversal algorithms are important since graphs are a common data structure in which information is distributed. none of the existing algorithmic paradigms focuses on graph traversal. this article introduces ennce substitution as an extension to ence substitution. the relationship between ennce substitution and ence substitution is explored. moreover, an ennce graph transformation system is defined and then used to generate depth-first and breadth-first graph traversal. thus, ennce graph transformation shows potential as a fundamental concept for a traversal-oriented algorithmic paradigm.
on deterministic finite automata and syntactic monoid size. we investigate the relationship between regular languages and syntactic monoid size. in particular, we consider the transformation monoids of n-state (minimal) deterministic finite automata. we show tight upper and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used. it turns out, that the two generator case is the most involved one. there we show a lower bound of nn (1 - 2/√n) for the size of the syntactic monoid of a language accepted by an n-state deterministic finite automaton with binary input alphabet. moreover, we prove that for every prime n ≥ 7, the maximal size semigroup w.r.t. its size among all (transformation) semigroups which can be generated with two generators, is generated by a permutation with two cycles (of appropriate lengths) and a non-bijective mapping merging elements from these two cycles. as a by-product of our investigations we determine the maximal size among all semigroups generated by two transformations, where one is a permutation with a single cycle and the other is a non-bijective mapping.
on the descriptional complexity of finite automata with modified acceptance conditions. we consider deterministic and nondeterministic finite automata with acceptance conditions that rely on the whole history of a computation on a given word and not only on the last state of the computation under consideration. formally, these conditions can be seen as the natural analogies of the büchi and muller acceptance for finite automata on infinite words. we study the computational power of these new acceptance mechanisms and prove some results on the descriptional complexity of conversions between automata with these new acceptance criteria and finite automata with ordinary acceptance.
alternating and empty alternating auxiliary stack automata. we consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. in this way we get new characterizations of np, the polynomial hierarchy, pspace, and bounded query classes like co-dp=nl〈np[1]〈 and θ2p=pnp[o(logn)], in a uniform framework.
assembling molecules in atomix is hard. it is shown that assembling molecules in the atomix game can be used to simulate finite automata. in particular, an instance of atomix is constructed that has a solution if and only if the non-emptiness intersection problem for finite automata is solvable. this shows that the game under consideration is pspace-complete, improving a recent result of hüffner et al. (lecture notes in computer science, vol. 2174, springer, vienna, austria, 2001, pp. 229-243). moreover, the given reduction shows that there are atomix games which have exponentially long optimal solutions. we also give an easy construction of atomix game levels whose optimal solutions meet the worst case.
lower bounds for restricted read-once parity branching programs. we prove the first lower bounds for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. namely, sums of k graph-driven ⊕ bp1s with polynomial size graph-orderings are under consideration. we prove lower bounds for the characteristic function of linear codes. we generalize a lower bound by savický and sieling (see [p. savický, d. sieling, a hierarchy result for read-once branching programs with restricted parity nondeterminism, theoret. comput. sci. 340 (2005) 594-605]) and recent results on graph-driven parity branching programs.
on d0l power series. we study d0l power series. we show how elementary morphisms introduced by ehrenfeucht and rozenberg can be used in connection with power series, characterize the sequences of rational numbers and integers which can be appear as coefficients in d0l power series and establish various decidability results.
a short solution for the hdt0l sequence equivalence problem. we give a solution for the hdt0l sequence equivalence problem which uses hilbert''s basis theorem but avoids the use of makanin''s algorithm or hall''s results about metabelian groups.
on parikh slender context-free languages. in a recent paper we defined and studied parikh slender languages and showed that they can be used in simplifying ambiguity proofs of context-free languages. in this paper parikh slender context-free languages are characterized. the characterization has diverse applications.
on images of d0l and dt0l power series. the d0l and dt0l power series are generalizations of d0l and dt0l languages. we continue the study of these series by investigating various decidability questions concerning the images of d0l and dt0l power series.
decidability results for watson-crick d0l systems with nonregular triggers. we show that sequence equivalence, language equivalence, growth equivalence and road equivalence are decidable for standard watson-crick d0l systems having bounded balance.
the language equivalence problem for hd0l systems having d0l growths. we show that language equivalence is decidable for hd0l systems having d0l growths. by definition, an hd0l system h has d0l growth if the length sequence of h is a d0l length sequence.