waashk/dblp huggingface dataset:
a common algebraic description for probabilistic and quantum computations. through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. on this basis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa; that is, given a tensor formula f of order n × 1 over a semiring i plus a positive integer k, deciding whether the kth partial trace of the matrix valin,n (f ċ ft) fulfills a certain property. we use this to show that a certain promise version of the sum-free partial trace problem is complete for the class pr- bpp (promise bpp) for formulas over the semiring (q+, +, ċ) of the positive rational numbers, for pr-bqp (promise bqp) in the case of formulas defined over the field (q+, +, ċ), and if the promise is given up, then completeness for pp is shown, regardless whether tensor formulas over positive rationals or rationals in general are used. this suggests that the difference between probabilistic and quantum polytime computers may ultimately lie in the possibility, in the latter case, of having destructive interference between computations occurring in parallel. moreover, by considering variants of this problem, classes like op, np, c=p, its complement co-c=p, the promise version of valiant's class up, its generalization promise spp, and unique polytime us can be characterized by carrying the problem properties and the underlying semiring.
mcnaughton families of languages. in 1988 the church-rosser languages were introduced by mcnaughton et al. as those languages that are recognized by finite, length-reducing and confluent string-rewriting systems using extra non-terminal symbols. here we generalize this concept by considering classes of languages that are obtained by other types of string-rewriting systems. to honour robert mcnaughton's original contribution we call the resulting families of languages mcnaughton families. here it is shown that the concept of mcnaughton families is as powerful as the notion of turing machine or the notion of phrase-structure grammar. we investigate the relationships between the various mcnaughton families, obtaining an extensive hierarchy of classes that includes many well-known language and complexity classes as well as some new classes. further, we consider some closure and non-closure properties for those mcnaughton families that are contained in the class of context-free languages, and we address the complexity of the fixed and the general membership problems for these families.
on probabilistic timed automata. we propose a model of probabilistic timed automaton which substitutes for the nondeterminism of an ordinary timed automaton, a new one (directly drawn from markov decision processes) by means of actions which provide a probabilistic distribution over transitions. using büchi acceptance conditions, timed automata can refer timing properties as "during every open time interval of length 1 at least one message is delivered". a policy is a mechanism which solves the non-determinism by choosing for each finite run an action and the time moment of the next transition step implied by this action. we prove that, given a probabilistic timed automaton a, there exists a markov (memoryless) policy which maximizes the probability p of the set of accepting runs realized by this policy. this policy as well as the maximal value of p are computable in polytime in the size of the region automaton of a. this result provides an algorithm of model-checking for properties like "there is a policy which realizes a correct behavior of the system with probability at least p".
groups and tilings. we prove that the word problem for the group of dominoes is equivalent to the existence of a directed tiling for the corresponding closed curve in the plane, which, in turn is equivalent to the fact that the curve is "balanced". this last property beeing decidable, the word problem is also decidable. moreover we prove that this result is transposable in any other regular grid (hexagonal or triangular) and we partially extend it to "exact" tiles.
a codicity undecidable problem in the plane. in this paper we give a new undecidability result about tiling problems. given a finite set of polyomino types, the problem whether this set is a code, is undecidable. the same result holds for dominoes.
decidable verification for reducible timed automata specified in a first order logic with time. we consider one type of first order timed logic (fotl) with explicit continuous time. fotl is sufficiently expressible from the user's point of view to rewrite directly requirements specifications often given in a language close to the natural one, and it permits to represent the set of runs of timed programs. thus, fotl is apt to formalize the verification problem for timed systems. our main goal is to describe in semantical terms interesting decidable classes of the verification problem within this setting. we prove that under some finiteness properties of the requirements and algorithm specifications the verification problem represented in fotl becomes decidable. the finiteness properties we introduce, "finite refutability" and "finite satisfiability", are undecidable in the general case. however, "finite refutability" is often easy to verify. on the other hand, we give a sufficient condition, namely reducibility, which ensures the "finite satisfiability" for timed automata, and we prove that the reducibility is decidable. this is the main result of the paper. as a consequence the verification of any finitely refutable requirements is decidable for reducible timed automata.
on the design of efficient atm routing schemes. in this paper we deal with the problem of designing virtual path layouts in atm networks when the hop-count is given and the load has to be minimized. we first prove a lower bound for networks with arbitrary topology and arbitrary set of connection requests. this result is then applied to derive lower bounds for the following settings: (i) one-to-all (one node has to be connected to all other nodes of the network) in arbitrary networks; (ii) all-to-all (each node has to be connected to all other nodes in the network) in several classes of networks, including planar and k-separable networks and networks of bounded genus. we finally study the all-to-all setting on two-dimensional meshes and we design a virtual path layout for this problem. when the hop-count and the network degree are bounded by constants, our results show that the upper bounds proposed in this paper for the one-to-all problem in arbitrary networks and for the all-to-all problem in two-dimensional mesh networks are asymptotically optimal. moreover, the general lower bound shows that the algorithm proposed in gerstel (ph.d. thesis, technion-haifa, israel, 1995) for the all-to-all problem in k-separable networks is also asymptotically optimal. the upper bound for mesh networks also shows that the lower bound presented in this paper for the all-to-all problem in planar networks is asymptotically tight.
semi-clairvoyant scheduling. in (symp. discrete algorithms 2002, p. 762) it was shown that the obvious semi-clairvoyant generalization of the shortest processing time is o(1)-competitive with respect to average stretch on a single machine. in (symp. discrete algorithms 2002, p. 762) it was left as an open question whether it was possible for a semi-clairvoyant algorithm to be o(1)-competitive with respect to average flow time on a single machine. here we settle this open question by giving a semi-clairvoyant algorithm that is o(1)-competitive with respect to average flow time on a single machine. we also show a semi-clairvoyant algorithm on parallel machines that achieves up to constant factors the best known competitive ratio for clairvoyant on-line algorithms. in some sense one might conclude from this that the qos achievable by semi-clairvoyant algorithms is competitive with clairvoyant algorithms. we finally show that, in contrast to the clairvoyant case, no semi-clairvoyant algorithm can be simultaneously o(1)-competitive with respect to average stretch and o(1)-competitive with respect to average flow time.
an example of a computable absolutely normal number. the first example of an absolutely normal number was given by sierpinski in 1916, twenty years before the concept of computability was formalized. in this note we give a recursive reformulation of sierpinski's construction which produces a computable absolutely normal number.
-valued non-associative lambek grammars are learnable from generalized functor-argument structures. this paper is concerned with learning categorial grammars from positive examples in the model of gold. functor-argument structures (written fa) are usual syntactical decompositions of sentences in sub-components distinguishing the functional parts from the argument parts defined in the case of classical categorial grammars also known as ab-grammars. in the case of nonassociative type-logical grammars, we propose a similar notion that we call generalized functor-argument structures and we show that these structures capture the essence of non-associative lambek (nl) calculus without product.we show that (i) rigid and k-valued non-associative lambek (nl without product) grammars are learnable from generalized functor-argument structured sentences.we also define subclasses of k-valued grammars in terms of arity. we first show that (ii) for each k and each bound on arity the class of fa-arity bounded k-valued nl languages of fa structures is finite and (iii) that fa-arity bounded k-valued nl grammars are learnable both from strings and from fa structures as a corollary.result (i) is obtained from (ii); this learnability result (i) is interesting and surprising when compared to other results: in fact we also show that (iv) this class has infinite elasticity. moreover, these classes are very close to classes like rigid associative lambek grammars learned from natural deduction structured sentences (that are different and much richer than fa or generalized fa) or to k-valued non-associative lambek grammars unlearnable from strings or even from bracketed strings. thus, the class of k-valued non-associative lambek grammars learned from generalized functor-argument sentences is at the frontier between learnable and unlearnable classes of languages.
notations for exponentiation. we define a coding of natural numbers--which we will call exponential notations--and interpretations of the less-than-relation, the successor, addition and exponentiation function on exponential notations. we prove that all these interpretations are polynomial time computable. as a corollary we obtain that feasible arithmetic can prove the consistency of the canonical equational theory for the language containing the successor, addition and exponentiation function.
synchronized shuffles. we extend the basic shuffle on words and languages, a well-known operation in theoretical computer science, by introducing three synchronized shuffles. these synchronized shuffles have some relevance to molecular biology since they may be viewed as the formal representations of various forms of gene linkage during genome shuffling. more precisely, each synchronized shuffle preserves the genetic backbone of the organisms, as well as the linked genes, by requiring the synchronization of some predefined genes while all other genes are arbitrarily shuffled. as for their mathematical properties, we prove that in a trio the closure under shuffle is equivalent to the closure under any of the synchronized shuffles studied here. finally, based on this result, we present an algorithm for deciding whether a given regular language is synchronized shuffle closed.
efficiently covering complex networks with cliques of similar vertices. we describe a polynomial time algorithm for covering graphs with cliques, prove its asymptotic optimality in a random intersection graph model and present experimental results on complex real-world networks.
the 3-server problem in the plane. in the k-server problem we wish to minimize, in an online fashion, the movement cost of k servers in response to a sequence of requests (we assume that k ≥ 2). the request issued at each step is specified by a point r in a given metric space m. to serve this request, one of the k servers must move to r. it is known that if m has at least k + 1 points then no online algorithm for the k-server problem in m has competitive ratio smaller than k. the best known upper bound on the competitive ratio in arbitrary metric spaces, by koutsoupias and papadimitriou (j. acm 42 (1995) 971), is 2k - 1. there are only a few special cases for which k-competitive algorithms are known: for k = 2, when m is a tree, or when m has at most k + 2 points. we prove that the work function algorithm is 3-competitive for the 3-server problem in the manhattan plane. as a corollary, we obtain a 4.243-competitive algorithm for 3 servers in the euclidean plane. the best previously known competitive ratio for 3 servers in these metric spaces was 5.
mod 3 arithmetic on triangulated riemann surfaces. let t be a triangulation of a riemann surface, orientable or non-orientable and of an arbitrary genus. suppose, a labeling of the vertices of t by three labels &thgr;, +1, and -1 is fixed. the present paper deals with the following problem: 2nd the number of labelings of the faces of t by two labels +1 and - 1, in such a way that the sum of the labels of the faces around any vertex is equal modulo 3 to the given label of the vertex. if t is a planar triangulation and all labels of vertices are zeros, then the problem of existence of such a labeling of faces is equivalent, according to p.j. heawood, to the four-colour problem for planar triangulations, and the corresponding counting problem is equivalent to that of counting the number of all proper four-colourings of t.
categorical proof theory of classical propositional calculus. we investigate semantics for classical proof based on the sequent calculus. we show that the propositional connectives are not quite well-behaved from a traditional categorical perspective, and give a more refined, but necessarily complex, analysis of how connectives may be characterised abstractly. finally we explain the consequences of insisting on more familiar categorical behaviour.
on probabilistic analog automata. we consider probabilistic automata on a general state space and study their computational power. the model is based on the concept of language recognition by probabilistic automata due to rabin (inform. control 3 (1963) 230) and models of analog computation in a noisy environment suggested by maass and orponen (neural comput. 10 (1998) 1071), and maass and sontag (neural comput. 11 (1999) 771). our main result is a generalization of rabin's reduction theorem that implies that under very mild conditions, the computational power of such automata is limited to regular languages.
the level ancestor problem simplified. we present a simple algorithm for the level ancestor problem. a level ancestor query la(v,d) requests the depth d ancestor of node v. the level ancestor problem is to preprocess a given rooted tree t to support level ancestor queries. while optimal solutions to this problem already exist, our new optimal solution is simple enough to be taught and implemented.
structural properties of xpath fragments. we study structural properties of each of the main sublanguages of navigational xpath (w3c recommendation) commonly used in practice. first, we characterize the expressive power of these language fragments in terms of both logics and tree patterns. second, we investigate closure properties, focusing on the ability to perform basic boolean operations while remaining within the fragment. we give a complete picture of the closure properties of these fragments, treating xpath expressions both as functions of arbitrary nodes in a document tree, and as functions that are applied only at the root of the tree. finally, we provide sound and complete axiom systems and normal forms for several of these fragments. these results are useful for simplification of xpath expressions and optimization of xml queries.
automated higher-order complexity analysis. this paper describes the automated complexity analysis (aca) system for automated higher-order complexity analysis of functional programs synthesized with the ncprd proof development system. we introduce a general framework for defining models of computational complexity for functional programs based on an annotation of a given operational language semantics. within this framework, we use type decomposition and polynomialization to express the complexity of higher-order terms. symbolic interpretation of open terms automates complexity analysis, which involves generating and solving higher-order recurrence equations. finally, the use of the aca system is demonstrated by analyzing three different implementations of the pigeonhole principle.
building continuous webbed models for system f. we present here a large family of concrete models for girard and reynolds polymorphism (system f), in a noncategorical setting. the family generalizes the construction of the model of barbanera and berardi (tech. report, university of turin, 1997), hence it contains complete models for fη (a βη-complete model for system f, preprint, june, 1998) and we conjecture that it contains models which are complete for f. it also contains simpler models, the simplest of them, e2, being a second-order variant of the engeler-plotkin model e. all the models here belong to the continuous semantics and have underlying prime algebraic domains, all have the maximum number of polymorphic maps. the class contains models which can be viewed as two intertwined compatible webbed models of untyped λ-calculus (in the sense of berline (from computations to foundations: the λ-calculus and its webbed models, revised version, theoret. comput. sci. 86 pp., to appear)), but it is much larger than this. finally, many of its models might he read as two intertwined strict intersection type systems.
from cascade decompositions to bit-vector algorithms. a vector algorithm is an algorithm that applies a bounded number of vector operations to an input vcctor, regardless of the length of the input. in this paper, we describe the links between the existence of vector algorithms and the cascade decompositions of counter-free automata.we show that any computation that can be carried out with a counter-free automaton can be recast as a vector algorithm. moreover, we show that for a class of automata that is closely related to algorithms in bio-computing, the complexity of the resulting algorithms is linear in the number of transitions of the original automaton.
computational complexity of some problems involving congruences on algebras. we prove that several problems concerning congruences on algebras are complete for nondeterministic log-space. these problems are: determining the congruence on a given algebra generated by a set of pairs, and determining whether a given algebra is simple or subdirectly irreducible. we also consider the problem of determining the smallest fully invariant congruence on a given algebra containing a given set of pairs. we prove that this problem is complete for nondeterministic polynomial time.
polarized process algebra with reactive composition. polarized processes are introduced to model the asymmetric interaction of systems. the asymmetry stems from the distinction between service and request. the scheduled concurrent composition of two polarized processes is called client-server composition or reactive composition, placing one process in the role of a client and the other process in the role of a server which is supposed to react on requests. the technical goal of this paper is to provide a definition of reactive composition for polarized processes and to prove that reactive composition thus defined is associative.
process algebra for hybrid systems. we propose a process algebra obtained by extending a combination of the process algebra with continuous relative timing from baeten and middelburg (process algebra with timing, springer, berlin, 2002, chapter 4), and the process algebra with propositional signals from baeten and bergstra (theoret. comput. sci. 177 (1977) 381-405). the proposed process algebra makes it possible to deal with the behaviour of hybrid systems, i.e. systems in which the instantaneous state transitions caused by performing actions are alternated with continuous state evolutions. this process algebra has, in addition to equational axioms, rules to derive equations with the help of real analysis.
branching time and orthogonal bisimulation equivalence. we propose a refinement of branching bisimulation equivalence that we call orthogonal bisimulation equivalence. typically, internal activity (the performance of τ-steps) may be compressed, but not completely discarded. hence, a process with τ-steps cannot be equivalent to one without τ-steps. also, we present a modal characterization of orthogonal bisimulation equivalence. this equivalence is a congruence for acp extended with abstraction and priority operators. we provide a complete axiomatization, and describe some expressiveness results. finally, we present the verification of a par protocol that is specified with use of priorities.
easiness in graph models. we generalize baeten and boerboom's method of forcing to show that there is a fixed sequence (uk)k∈ω of closed (untyped) λ-terms satisfying the following properties: (a) for any countable sequence (gk)k∈ω of scott continuous functions (of arbitrary arity) on the power set of an arbitrary countable set, there is a graph model such that (λx.xx)(λx.xx)uk represents gk in the model. (b) for any countable sequence (tk)k∈ω of closed λ-terms there is a graph model that satisfies (λx.xx)(λx.xx)uk = tk for all k. we apply these two results, which are corollaries of a unique theorem, to prove the existence of (1) a finitely axiomatized λ-theory l such that the interval lattice constituted by the λ-theories extending l is distributive; (2) a continuum of pairwise inconsistent graph theories (= λ-theories that can be realized as theories of graph models); (3) a congruence distributive variety of combinatory algebras (lambda abstraction algebras, respectively).
directed virtual path layouts in atm networks. motivated by asynchronous transfer mode in telecommunication networks, we investigate the problem of designing a directed virtual topology on a directed physical topology, which consists in finding a set of directed virtual paths (vps) satisfying some constraints in terms of load (the number of vps sharing a physical link) and hop count (the number of vps used to establish a connection). for both general and particular networks, such as paths, cycles, meshes, tori and trees, we derive tight bounds on the virtual diameter (the maximum hop count for a connection) as a function of the network capacity (the maximum load of a physical link).
a new dimension sensitive property for cellular automata. in this paper we study number-decreasing cellular automata. they form a super-class of standard number-conserving cellular automata. it is well-known that the property of being number-conserving is decidable in quasi-linear time. in this paper we prove that being number-decreasing is dimension sensitive, i.e. it is decidable for one-dimensional cellular automata and undecidable for dimension 2 or greater. there are only few known examples of dimension sensitive properties for cellular automata and this denotes some rich panel of phenomena in this class.