waashk/dblp huggingface dataset:
positive varieties of tree languages. pin's variety theorem for positive varieties of string languages and varieties of finite ordered semigroups is proved for trees, i.e., a bijective correspondence between positive varieties of tree languages and varieties of finite ordered algebras is established. this, in turn, is extended to generalized varieties of finite ordered algebras, which corresponds to steinby's generalized variety theorem. also, families of tree languages and classes of ordered algebras that are definable by ordered (syntactic or translation) monoids are characterized.
a new approach to all-pairs shortest paths on real-weighted graphs. we present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. it runs in o(mn + n2 log log n) time, improving on the long-standing bound of o(mn + n2 log n) derived from an implementation of dijkstra's algorithm with fibonacci heaps. here m and n are the number of edges and vertices, respectively.our algorithm is rooted in the so-called component hierarchy approach to shortest paths invented by thorup for integer-weighted undirected graphs, and generalized by hagerup to integer-weighted directed graphs. the technical contributions of this paper include a method for approximating shortest path distances and a method for leveraging approximate distances in the computation of exact ones. we also provide a simple, one line characterization of the class of hierarchy-type shortest path algorithms. this characterization leads to some pessimistic lower bounds on computing single-source shortest paths with a hierarchy-type algorithm.
the factor composition matrix of sequences. let s = {a, b} be a two-letter alphabet and s a sequence over s. an infinite matrix (ti,j)i,j ≥ 0 is associated with s in the following way: ti,j = 1 if s has a factor which contains i times a and j times b; otherwise ti,j = 0. this matrix will be called the factor composition matrix (fcm) of the sequence s. in this paper, combinatorial properties of certain sequences are studied via their fcms. in particular (i) the fcm of the thue-morse sequence is shown to be pentadiagonal, and substitutions whose fixed points have the same fcm as the thue-morse sequence are determined; (ii) an algorithm for computing the fcm of a sturmian sequence is presented; (iii) the fcms of fixed points of invertible substitutions are characterized in terms of their singular decompositions.
finite transducers for divisibility monoids. divisibility monoids are a natural lattice-theoretical generalization of mazurkiewicz trace monoids, namely monoids in which the distributivity of the involved divisibility lattices is kept as an hypothesis, but the relations between the generators are not supposed to necessarily be commutations. here, we show that every divisibility monoid admits an explicit finite transducer which allows to compute normal forms in quadratic time. in addition, we prove that every divisibility monoid is biautomatic.
explicit versus implicit representations of subsets of the herbrand universe. in lassez and marriott (j. automat. reson. 3 (3) (1987) 301-317), explicit and implicit generalizations were studied as representations of subsets of some fixed herbrand universe h. an explicit generalization e = r1v ... v rl represents all ground terms that are instances of at least one of the terms ti, whereas an implicit generalization i = t/t1 v ... v tm represents all h-ground instances of t that are not instances of any term ti. more generally, a disjunction i = i1 v ... v in of implicit generalizations contains all ground terms that are contained in at least one of the implicit generalizations ij.implicit generalizations have applications to many areas of computer science like machine learning, unification, specification of abstract data types, logic programming, functional programming, etc. in these areas, the so-called finite explicit representability problem plays an important role, i.e. given a disjunction of implicit generalizations i =i1 v ... v in, does there exist an explicit generalization e, s.t. i and e are equivalent? we shall prove the conp-completeness of this decision problem.implicit generalizations can be represented as equational formulae, i.e., first-order formulae whose only predicate symbol is syntactic equality. closely related to the finite explicit representability problem is the so-called negation elimination problem of equational formulae, i.e. given an arbitrary equational formula p is p semantically equivalent to an equational formula without universal quantifiers and negation. in this work we study the negation elimination problem of equational formulae with purely existential quantifier prefix. we prove the conp-completeness for such formulae in dnf and the π2p -hardness in case of cnf.
reconstruction of convex polyominoes from orthogonal projections of their contours. the problem of reconstructing a convex polyominoes from its horizontal and vertical projections when the projections are defined as the number of cells of the polyomino in the different lines and columns was studied by del lungo and m. nivat. in this paper, we study the reconstruction of any convex polyomino when the orthogonal projections are defined as the contour length of the object intercepted by the ray. we prove the np-hardness of this problem for several classes of polyominoes: general, h-convex, v-convex. for hv-convex polyominoes we give a polynomial time algorithm for the reconstruction problem.
a proof outline logic for object-oriented programming. this paper describes a proof outline logic that covers most typical object-oriented language constructs in the presence of inheritance and subtyping. the logic is based on a weakest precondition calculus for assignments and object allocation which takes field shadowing into account. dynamically bound method calls are tackled with a variant of hoare's rule of adaptation that deals with the dynamic allocation of objects in object-oriented programs. the logic is based on an assertion language that is closely tailored to the abstraction level of the programming language.
measuring the confinement of probabilistic systems. in this paper we lay the semantic basis for a quantitative security analysis of probabilistic systems by introducing notions of approximate confinement based on various process equivalences. we recast the operational semantics classically expressed via probabilistic transition systems (pts) in terms of linear operators and we present a technique for defining approximate semantics as probabilistic abstract interpretations of the pts semantics. an operator norm is then used to quantify this approximation. this provides a quantitative measure ε of the indistinguishability of two processes and therefore of their confinement. in this security setting a statistical interpretation is then given of the quantity ε which relates it to the number of tests needed to breach the security of the system.
a topological approach to transductions. this paper is a contribution to the mathematical foundations of the theory of automata. we give a topological characterization of the transductions τ from a monoid m into a monoid n, such that if r is a recognizable subset of n, τ-1(r) is a recognizable subset of m. we impose two conditions on the monoids, which are fullfilled in all cases of practical interest: the monoids must be residually finite and, for every positive integer n, must have only finitely many congruences of index n. our solution proceeds in two steps. first we show that such a monoid, equipped with the so-called hall distance, is a metric space whose completion is compact. next we prove that τ can be lifted to a map τ from m into the set of compact subsets of the completion of n. this latter set, equipped with the hausdorff metric, is again a compact monoid. finally, our main result states that τ-1 preserves recognizable sets if and only if τ is continuous.
accumulators: new logic variable abstractions for functional languages. much attention has been focused by the declarative languages community on combining the functional and logic programming paradigms. in particular, there are many efforts to incorporate logic variables into functional languages. we propose a generalization of logic variables called accumulators which are eminently suited for incorporation into functional languages. we demonstrate the utility of accumulators by presenting examples which show that accumulators can be used profitably in many scientific applications to enhance storage efficiency and parallelism.
on the rate of convergence of error estimates for the partitioning classification rule. the error probability of the partitioning classification rule is shown to converge to the bayes error faster than 1/√n under certain conditions. the resubstitution and the deleted error estimates for the partitioning classification rule from a sample (x1, y1),..., (xn, yn) are studied. the random part of the resubstitution estimate is shown to be small for arbitrary partition and for any distribution of (x, y). if we assume that x has a density f and the partitions consist of rectangles, then the difference between the expected value of the estimate and the bayes error restricted to the partition is less than a constant times 1/√n. the main result of the paper is that, under the same conditions, for both estimates the difference between the estimate and the real error probability of the classification rule is asymptotically normal with 0 mean and variance l*/2, where l* is the bayes error.
inequalities characterizing standard sturmian and episturmian words. considering the smallest and the greatest factors with respect to the lexicographic order we associate to each infinite word r two other infinite words min(r) and max(r). in this paper we prove that the inequalities as ≤ min(s) ≤ max(s) ≤ bs characterize standard sturmian words (proper ones and periodic ones) and that the condition "for any x ∈ a and lexicographic order < satisfying x = min(a) one has xs ≤ min(s)" characterizes standard episturmian words.
a maude specification of an object-oriented model for telecommunication networks. this paper presents an object-oriented model for broadband telecommunication networks, which can be used both for network management and for network planning purposes. the object-oriented model has been developed using the parallel object-oriented specification language maude, which allows us to define not only structural aspects of the model but also procedural aspects. the reflective properties of rewriting logic are applied to control the rewriting process, using a strategy language that can be specified internally to the logic. several modeling approaches are compared, emphasizing the definition of the object relationships and the benefits obtained from using reflection as opposed to the extra effort required to control the process at the object level itself.
the accelerated k-in-a-row game. we investigate two versions of the well-known k-in-a-row game. while in the most intriguing k=5 case the outcome of the game has been recently settled, very little is known about what happens when the rules are changed. a natural modification is that the players take more than one square of the board per move in order to speed up the game. our main goal is to improve the quadratic bound on the error term, given by csirmaz in csirmaz (discrete math. 29 (1980) 19-23), to a logarithmic one for the accelerated k-in-a-row. the other issue is the extreme sensitivity of k-in-a-row under biased rules. beck proposed in beck (unpublished lecture notes) that a player may trade some of his freedom of choice for the right of taking more squares than his opponent. we prove logarithmic bounds on the error term in that case, too.
the binomial transform and the analysis of skip lists. to any sequence of real numbers 〈an〉 n ≥ 0, we can associate another sequence 〈âs〉s ≥ 0 which knuth calls its binomial transform. this transform is defined through the rule âs = bsan=σn(-1)n(s n) an.we study the properties of this transform, obtaining rules for its manipulation and a table of transforms, that allow us to invert many transforms by inspection.we use these methods to perform a detailed analysis of skip lists, a probabilistic data structure introduced by pugh as an alternative to balanced trees. in particular, we obtain the mean and variance for the cost of searching for the first or the last element in the list (confirming results obtained previously by other methods), and also for the cost of searching for a random element (whose variance was not known).we obtain exact solutions, although not always in closed form. from them we are able to find the corresponding asymptotic expressions.
dynamic orthogonal range queries in olap. we study the problem of pre-computing auxillary information to support on-line range queries for the sum and max functions on a datacube. for a d-dimensional datacube with size n in each dimension, we propose a dynamic range max data structure with o(αd(s,n)ld) query time, o(αd(s, n)l2dnd/l) update time and o(sd) storage where l and s are parameters chosen by the user before the construction of the data structure such that l ∈ { 1,..., ⌈log n⌉ } and s is a non-negative multiple of n; and α(s, n) is the functional inverse of ackermann's function. moreover, the data structure can be initialized in time linear to its size. there are three major techniques employed in designing the data structure, namely, a technique for trading query and update times, a technique for trading query time and storage and a technique for extending one-dimensional data structures to d-dimensional ones. our techniques are also applicable to range queries over any semigroup and group operation, such as min, sum and count.
interpreted systems and kripke models for multiagent systems from a categorical perspective. both kripke models and interpreted systems have been put forward as basic models of multi-agent systems and for reasoning about knowledge in such systems. this paper enriches previous comparisons of these two forms of semantics by considering categories of models in both cases and then shows that constructions given by lomuscio and ryan, extend to give an adjoint equivalence between the two settings. this equivalence is exploited in a discussion of colimits of interpreted systems.
zeno machines and hypercomputation. this paper reviews the church-turing thesis (or rather, theses) with reference to their origin and application and considers some models of "hypercomputation", concentrating on perhaps the most straight-forward option: zeno machines (turing machines with accelerating clock). the halting problem is briefly discussed in a general context and the suggestion that it is an inevitable companion of any reasonable computational model is emphasised. it is suggested that claims to have "broken the turing barrier" could be toned down and that the important and well-founded rôle of turing computability in the mathematical sciences stands unchallenged.
a bijection for triangulations of a polygon with interior points and multiple edges. loopless triangulations of a polygon with k vertices in k + 2n triangles (with interior points and possibly multiple edges) were enumerated by mullin in 1965, using generating functions and calculations with the quadratic method.in this article we propose a simple bijective interpretation of mullin's formula. the argument rests on the method of conjugacy classes of trees, a variation of the cycle lemma designed for planar maps. in the much easier case of loopless triangulations of the sphere (k = 3), we recover and prove correct an unpublished construction of the second author.
a note on measuring in p. we revisit the problem of generalising lutz's resource-bounded measure (rbm) to small complexity classes, and propose a definition of a random-based rbm on p=∪k∈n dtime (o(nk)), which we argue as being a good generalisation to p of lutz's rbm. we cannot unconditionally prove the existence of such a measure, but we give sufficient and necessary conditions for its existence. we also revisit µτ, an rbm for p defined by strauss [inform. comput. 136(1) (1997) 1], and correct an erroneous claim concerning the relations between µτ and random sets. a correction to this mistake is then proposed, which is a less powerful but accurate relation between µτ and random sets.in order to obtain these results, we introduce a mathematical structure called a measuring system, which is a general setting that can be used to compare different rbms on any fixed complexity class through a partial ordering relation.
premonoidal categories as categories with algebraic structure. we develop the study of premonoidal categories. specifically, we reconcile premonoidal categories with the usual study of categories with algebraic structure by adding a little extra structure. we further give a notion of closedness for a premonoidal category with such extra structure, and show that every premonoidal category fully embeds into a closed one.
generic models for computational effects. a freyd-category is a subtle generalisation of the notion of a category with finite products. it is suitable for modelling environments in call-by-value programming languages, such as the computational λ-calculus, with computational effects. we develop the theory of freyd-categories with that in mind. we first show that any countable lawvere theory, hence any signature of operations with countable arity subject to equations, directly generates a freyd-category. we then give canonical, universal embeddings of freyd-categories into closed freyd-categories, characterised by being free cocompletions. the combination of the two constructions sends a signature of operations and equations to the kleisli category for the monad on the category set generated by it, thus refining the analysis of computational effects given by monads. that in turn allows a more structural analysis of the λc-calculus. our leading examples of signatures arise from side-effects, interactive input/output and exceptions. we extend our analysis to an enriched setting in order to account for recursion and for computational effects and signatures that inherently involve it, such as partiality, nondeterminism and probabilistic nondeterminism.
fixpoint operators for domain equations. we investigate fixpoint operators for domain equations. it is routine to verify that if every endofunctor on a category has an initial algebra, then one can construct a fixpoint operator from the category of endofunctors to the category. that construction does not lift routinely to enriched categories, using the usual enriched notion of initiality of an endofunctor. we show that by embedding the 2-category of small enriched categories into the 2-category of internal categories of a presheaf topos, we can recover the fixpoint construction elegantly. also, we show that in the presence of cotensors, an enriched category allows the fixpoint construction.
combining a monad and a comonad. we give a systematic treatment of distributivity for a monad and a comonad as arises in giving category theoretic accounts of operational and denotational semantics, and in giving an intensional denotational semantics. we do this axiomatically, in terms of a monad and a comonad in a 2-category, giving accounts of the eilenberg-moore and kleisli constructions. we analyse the eight possible relationships, deducing that two pairs are isomorphic, but that the other pairs are all distinct. we develop those 2-categorical definitions necessary to support this analysis.
factorizing fault tolerance. this paper presents a theory of component based development for exception-handling in fault tolerant systems. the theory is based on a general theory of composition, which enables us to factorize the temporal specification of a system into the specifications of its components. this is a new development because in the past efforts to set up such a theory have always been hindered by the problem of composing progress properties.
chu spaces as a semantic bridge between linear logic and mathematics. the motivating role of linear logic is as a "logic behind logic". we propose a sibling role for it as a logic of transformational mathematics via the self-dual category of chu spaces, a generalization of topological spaces. these create a bridge between linear logic and mathematics by soundly and fully completely interpreting linear logic while fully and concretely embedding a comprehensive range of concrete categories of mathematics. our main goal is to treat each end of this bridge in expository detail. in addition, we introduce the dialectic lambda-calculus, and show that dinaturality semantics is not fully complete for the chu interpretation of linear logic.
looking at the stars. the problem of packing k vertex-disjoint copies of a graph h into another graph g is np-complete if h has more than two vertices in some connected component. in the framework of parameterized complexity, we analyze a particular family of instances of this problem, namely the packing of stars. we give a quadratic kernel for packing k copies of h = k1,s. when we consider the special case of s = 2, i.e. h being a star with two leaves, we give a linear kernel and an algorithm running in time o(25.301kk2.5 + n3).
generalized domino-shuffling. the problem of counting tilings of a plane region using specified tiles can often be recast as the problem of counting (perfect) matchings of some subgraph of an aztec diamond graph an, or more generally calculating the sum of the weights of all the matchings, where the weight of a matching is equal to the product of the (pre-assigned) weights of the constituent edges (assumed to be non-negative). this article presents efficient algorithms that work in this context to solve three problems: finding the sum of the weights of the matchings of a weighted aztec diamond graph an; computing the probability that a randomly-chosen matching of an, will include a particular edge (where the probability of a matching is proportional to its weight); and generating a matching of an at random. the first of these algorithms is equivalent to a special case of mihai ciucu's cellular complementation algorithm (j. combin. theory ser. a 81 (1998) 34) and can be used to solve many of the same problems. the second of the three algorithms is a generalization of not-yet-published work of alexandru ionescu, and can be employed to prove an identity governing a three-variable generating function whose coefficients are all the edge-inclusion probabilities; this formula has been used (duke math. j. 85 (1996) 117) as the basis for asymptotic formulas for these probabilities, but a proof of the generating function identity has not hitherto been published. the third of the three algorithms is a generalization of the domino-shuffling algorithm presented in (j. algebraic combin. 1 (1992) 111); it enables one to generate random "diabolo-tilings of fortresses" and thereby to make intriguing inferences about their asymptotic behavior.
when a genetic algorithm outperforms hill-climbing. a toy optimisation problem is introduced which consists of a fitness gradient broken up by a series of hurdles. the performance of a hill-climber and a stochastic hill-climber are computed. these are compared with the empirically observed performance of a genetic algorithm (ga) with and without. the hill-climber with a sufficiently large neighbourhood outperforms the stochastic hill-climber, but is outperformed by a ga both with and without crossover. the ga with crossover substantially outperforms all the other heuristics considered here. the relevance of this result to real world problems is discussed.