waashk/dblp huggingface dataset:
metrics for labelled markov processes. the notion of process equivalence of probabilistic processes is sensitive to the exact probabilities of transitions. thus, a slight change in the transition probabilities will result in two equivalent processes being deemed no longer equivalent. this instability is due to the quantitative nature of probabilistic processes. in a situation where the process behavior has a quantitative aspect there should be a more robust approach to process equivalence. this paper studies a metric between labelled markov processes. this metric has the property that processes are at zero distance if and only if they are bisimilar. the metric is inspired by earlier work on logics for characterizing bisimulation and is related, in spirit, to the hutchinson metric.
an algorithm to generate exactly once every tiling with lozenges of a domain. we first show that the tilings of a domain d form a lattice (using the same kind of arguments as in (research report no. 1999-25)) which we then undertake to decompose and generate without any redundance. to this end, we study extensively the relatively simple case of hexagons and their deformations. we show that general domains can be broken up into hexagon-like parts. finally we give an algorithm to generate exactly once every element in the lattice of the tilings of a general domain d.
domino tilings and related models: space of configurations of domains with holes. we first prove that the set of domino tilings of a fixed finite figure is a distributive lattice, even in the case when the figure has holes. we then give a geometrical interpretation of the order given by this lattice, using (not necessarily local) transformations called flips.this study allows us to formulate an exhaustive generation algorithm and a uniform random sampling algorithm.we finally extend these results to other types of tilings (calisson tilings, tilings with bicolored wang tiles).
optimal graph exploration without good maps. a robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. the quality of an exploration algorithm a is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. the ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class u, is called the overhead of algorithm a for the class u of graphs. we consider three scenarios, providing the robot with varying amount of information. the robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map).for all of the above scenarios, we construct natural exploration algorithms that have smallest, or--in one case--close to smallest, overhead. while for the class of all graphs, depth-first search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. we show that, under the scenario without any knowledge, dfs is still optimal for trees but this is not the case if a map is available. under the scenario with an unanchored map, we show that optimal overhead is at least √3 but strictly below 2 (and thus dfs is not optimal). under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is 3/2. we also consider exploration of the class of lines (simple paths). in this case, depth-first search remains optimal for the scenario without any knowledge, with overhead 2. under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is √3. finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is 7/5. an important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms.
a formula for the number of tilings of an octagon by rhombi. we propose the first algebraic determinantal formula to enumerate tilings of a centrosymmetric octagon of any size by rhombi. this result uses the gessel-viennot technique and generalizes to any octagon a formula given by elnitsky in a special case.
a bijection between directed column-convex polyominoes and ordered trees of height at most three. a bijection is given between the set of directed column-convex polyominoes of area n and the set of ordered trees of height at most three and having n edges. additional bijections with less well known combinatorial objects are sketched.
xml queries and constraints, containment and reformulation. starting from the xquery language we define xbind, an xml analog of relational conjunctive queries as well as a related class of xml integrity constraints (dependencies). we identify a fragment of xbind for which containment is decidable, in fact π2p-complete, and a further fragment for which containment is np-complete. we extend the containment algorithm to take xml dependencies into account. we give an algorithm for the reformulation of xbind queries under combinations of gav and lav xquery views, as well as additional dependencies. we prove a completeness theorem which guarantees that under certain conditions, our algorithm will find a minimal reformulation if one exists. moreover, we identify conditions when this algorithm achieves optimal complexity bounds. our results on containment and reformulation depend on certain restrictions on the query and constraint languages. we calibrate the results by showing that lifting these restrictions significantly changes the complexity of the problems.
rounding voronoi diagram. computational geometry classically assumes real-number arithmetic which does not exist in actual computers. a solution consists in using integer coordinates for data and exact arithmetic for computations. this approach implies that if the results of an algorithm are the input of another, these results must be rounded to match this hypothesis of integer coordinates. in this paper, we treat the case of two-dimensional voronoi diagrams and are interested in rounding the voronoi vertices to grid points while interesting properties of the voronoi diagram are preserved. these properties are the planarity of the embedding and the convexity of the cells. we give a condition on the grid size to ensure that rounding to the nearest grid point preserves the properties. we also present heuristics to round vertices (not to the nearest grid point) and preserve these properties.
general parameterised refinement and recursion for the m-net calculus. the algebra of m-nets, a high-level class of labelled petri nets, was introduced in order to cope with the size problem of the low-level petri box calculus, especially when applied as semantical domain for parallel programming languages. general, unrestricted and parameterised refinement and recursion operators, allowing to represent the (possibly recursive and concurrent) procedure call mechanism, are introduced into the m-net calculus.
a note on dimensions of polynomial size circuits. in this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. we show that for every i ≥0, p/poly has ith-order scaled p3-strong dimension 0. we also show that p/polyi.o. has p3-dimension 1/2 and p3-strong dimension 1. our results improve previous measure results of lutz [almost everywhere high nonuniform complexity, j. comput. syst. sci. 44(2) (1992) 220-258] and dimension results of hitchcock and vinodchandran [dimension, entropy rates, and compression, in: proc. 19th ieee conf. computational complexity, 2004, pp. 174-183, j. comput. syst. sci., to appear]. additionally, we establish a supergale dilation theorem, which extends the martingale dilation technique introduced implicitly by ambos-spies, terwijn, and zheng [resource bounded randomness and weakly complete problems, theoret. comput. sci. 172(1-2)(1997) 195-207] and made explicit by juedes and lutz [weak completeness in e and e2, theoret. comput. sci. 143(1) (1995) 149-158].
an efficient approach for the rank aggregation problem. this paper presents some computational properties of the rank-distance, a measure of similarity between partial rankings. we show how this distance generalizes the spearman footrule distance, preserving its good computational complexity: the rank-distance between two partial rankings can be computed in linear time, and the rank aggregation problem can be solved in polynomial time. further, we present a generalization of the rank-distance to strings, which permits to solve the median string problem in polynomial time. this appears rather surprising to us given the fact that for other non-trivial string distances, such as edit-distance, this problem is np-hard.
efficiency and equilibrium in the electronic mail game; the general case. in the email game (amer. econom. rev. 79 (1989) 385) noisy information channels may prevent risky-efficient coordination, even when the game is almost common knowledge. in this paper, we show that this is the case whenever message failure probabilities are not sufficiently different. quite intuitively, the extent of the difference is governed by the game payoffs, and in particular by the mixed nash equilibrium strategy of one of the two games to be played. this is because, conditionally to having observed one's type, a player's beliefs on the opponent's choices are governed by the reliability of communication channels.
eigenvariables, bracketing and the decidability of positive minimal predicate logic. we give a new proof of a theorem of mints that the positive fragment of minimal predicate logic is decidable. the idea of the proof is to replace the eigenvariable condition of sequent calculus by an appropriate scoping mechanism. the algorithm given by this proof seems to be more practical than that given by the original proof. a naive implementation is given at the end of the paper. another contribution is to show that this result extends to a large class of theories, including simple type theory (higher-order logic) and second-order propositional logic. we obtain this way a new proof of the decidability of the inhabitation problem for positive types in system f.
infinitary lambda calculus and discrimination of berarducci trees. we propose an extension of lambda calculus for which the berarducci trees equality coincides with observational equivalence, when we observe rootstable or rootactive behavior of terms. in one direction the proof is an adaptation of the classical böhm out technique. in the other direction the proof is based on confluence for strongly converging reductions in this extension.
a coding theory construction of new systematic authentication codes. there are several approaches to the construction of authentication codes without secrecy using error correcting codes. in this paper, we describe one approach and construct several classes of authentication codes using several types of error correcting codes. some of the authentication codes constructed here are asymptotically optimal, and some are optimal.
typical rounding problems. the linear discrepancy problem is to round a given [0, 1]-vector x to a binary vector y such that the rounding error with respect to a linear form is small, i.e., such that ||a(x - y)||∞ is small for some given matrix a. the combinatorial discrepancy problem is the special case of x=(1/2,...,1/2)t. a famous result of beck and spencer [math. programming 30 (1984) 88] as well as lovász et al. [european j. combin. 7 (1986) 151] shows that the linear discrepancy problem is not much harder than this special case: any linear discrepancy problem can be solved with at most twice the maximum rounding error among the discrepancy problems of the submatrices of a.in this paper, we strengthen this result for the common situation that the discrepancy of submatrices having n0 columns is bounded by cn0α for some c > 0, α ∈ [0, 1]. in this case, we improve the constant by which the general problem is harder than the discrepancy one from 2 down to 2(2/3)α. we also find that a random vector has expected linear discrepancy 2(1/2)αcnα only. hence in the typical situation that the discrepancy is decreasing for smaller matrices, the linear discrepancy problem is even less difficult compared to the discrepancy one than assured by previous results. we also obtain the bound lindisc(a,x) ≤ 2(2α/(21-α- 1))c||x||1α. our proofs use a reduction to pusher-chooser games.
interpolation in grothendieck institutions. it is well known that interpolation properties of logics underlying specification formalisms play an important rule in the study of structured specifications, they have also many other useful logical consequences.in this paper, we solve the interpolation problem for grothendieck institutions which have recently emerged as an important mathematical structure underlying heterogenous multilogic specification. our main result can be used in the applications in several different ways. it can be used to establish interpolation properties for multi-logic grothendieck institutions, but also to lift interpolation properties from unsorted logics to their many sorted variants. the importance of the latter resides in the fact that, unlike other structural properties of logics, many sorted interpolation is a non-trivial generalisation of unsorted interpolation.the concepts, results, and the applications discussed in this paper are illustrated with several examples from conventional logic and algebraic specification theory.
behavioural specification for hierarchical object composition. behavioural specification based on hidden (sorted) algebra constitutes one of the most promising recently developed formal specification and verification paradigms for system development.here we formally introduce novel concepts of behavioural object and equivalence between behavioural objects within the hidden algebra framework. we formally define several object composition operators on behavioural objects corresponding to the hierarchical object composition methodology introduced by cafeobj. we study their basic semantical properties and show that our most general form of behavioural object composition with synchronisation has final semantics and a composability property of behavioural equivalence supporting a high reusability of verifications. we also show the commutativity and the associativity of parallel compositions without synchronisation.
european tenure games. we study a variant of the tenure game introduced by spencer (theoret. comput. sci. 131 (1994) 415). in this version, faculty is not fired, but downgraded to the lowest rung instead.for the upper bound we give a potential function argument showing that the value υd of the game starting with d faculty on the first rung satisfies υd ≤ ⌊log2d + log2 log2d + 1.98⌋. we prove a nearly matching lower bound of ⌊log2d + log2 log2d⌋ using a strategy that can be interpreted as an antirandomization of spencer's original game. for d tending to infinity, these bounds improve to ⌊ log2d + log2 log2d + 1 + o(1)⌋ ≤ υd ⌊log2d + log2 log2d + 1.73 + o(1)⌋. in particular, the set of all d ∈ n such that the value of the game is precisely ⌊log2d + log2 log2d+ 1⌋ has lower density greater than 1/5.
logical foundations of cafeobj. this paper surveys the logical and mathematical foundations of cafeobj, which is a successor of the famous algebraic specification language obj but adds to it several new primitive paradigms such as behavioural concurrent specification and rewriting logic.we first give a concise overview of cafeobj. then we focus on the actual logical foundations of the language at two different levels: basic specification and structured specification, including also the definition of the cafeobj institution. we survey some novel or more classical theoretical concepts supporting the logical foundations of cafeobj, pointing out the main results but without giving proofs and without discussing all mathematical details. novel theoretical concepts include the coherent hidden algebra formalism and its combination with rewriting logic, and grothendieck (or fibred) institutions. however, for proofs and for some of the mathematical details not discussed here we give pointers to relevant publications.the logical foundations of cafeobj are structured by the concept of institution. moreover, the design of cafeobj emerged from its logical foundations, and institution concepts played a crucial rôle in structuring the language design.
improved bounds and schemes for the declustering problem. the declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. using deep results from discrepancy theory, we improve previous work of several authors concerning range queries to higher-dimensional data. we give a declustering scheme with an additive error of od (logd-1m) independent of the data size, where d is the dimension, m the number of storage devices and d - 1 does not exceed the smallest prime power in the canonical decomposition of m into prime powers. in particular, our schemes work for arbitrary-m in dimensions two and three. for general d, they work for all m≥d - 1 that are powers of two. concerning lower bounds, we show that a recent proof of a ωd (log(d-1)/2m) bound contains an error. we close the gap in the proof and thus establish the bound.
the stable marriage problem with restricted pairs. a stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. in an instance of the stable marriage problem, each of the n men and n women ranks the members of the opposite sex in order of preference. it is well known that at least one stable matching exists for every stable marriage problem instance. we consider extensions of the stable marriage problem obtained by forcing and by forbidding sets of pairs. we present a characterization for the existence of a solution for the stable marriage with forced and forbidden pairs problem. in addition, we describe a reduction of the stable marriage with forced and forbidden pairs problem to the stable marriage with forbidden pairs problem. finally, we also present algorithms for finding a stable matching, all stable pairs and all stable matchings for this extension. the complexities of the proposed algorithms are the same as the best known algorithms for the unrestricted version of the problem.
generating bicliques of a graph in lexicographic order. an independent set of a graph is a subset of pairwise non-adjacent vertices. a complete bipartite set b is a subset of vertices admitting a bipartition b = x ∪ y, such that both x and y are independent sets, and all vertices of x are adjacent to those of y. if both x, y ≠ 0, then b is called proper. a biclique is a maximal proper complete bipartite set of a graph. we present an algorithm that generates all bicliques of a graph in lexicographic order, with polynomial-time delay between the output of two successive bicliques. we also show that there is no polynomial-time delay algorithm for generating all bicliques in reverse lexicographic order, unless p = np. the methods are based on those by johnson, papadimitriou and yannakakis, in the solution of these two problems for independent sets, instead of bicliques.
bounds on the max and min bisection of random cubic and random 4-regular graphs. in this paper, we present a randomized algorithm to compute the bisection width of cubic and 4-regular graphs. the analysis of the proposed algorithms on random graphs provides asymptotic upper bounds for the bisection width of random cubic and random 4-regular graphs with n vertices, giving upper bounds of 0.174039n for random cubic, and of 0.333333n for random 4-regular. we also obtain asymptotic lower bounds for the size of the maximum bisection, for random cubic and random 4-regular graphs with n vertices, of 1.32697n and 1.66667n, respectively. the randomized algorithms are derived from initial greedy algorithm and their analysis is based on the differential equation method.
the multiplicative fragment of the yanov equational theory. we give a finite equational axiomatization for +-free identities of (regular) languages which contain the empty word. the axioms for the whole equational theory of such languages were given by yanov.
deletion along trajectories. we describe a new way to model deletion operations on formal languages, called deletion along trajectories. we examine its closure properties, which differ from those of shuffle on trajectories, previously introduced by mateescu et al. in particular, we define classes of nonregular sets of trajectories such that the associated deletion operation preserves regularity. our results give uniform proofs of closure properties of the regular languages for several deletion operations.we also show that deletion along trajectories serves as an inverse to shuffle on trajectories. this leads to results on the decidability of certain language equations, including those of the form ltx = r, where l,r are regular languages and x is unknown.
representing recursively enumerable languages by iterated deletion. a characterization of the recursively enumerable languages in terms of the iterated deletion operation is given. this solves two open problems posed by ito and silva on the closure properties and decidability of iterated deletion.
the chromatic and clique numbers of random scaled sector graphs. random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. in the random scaled sector graph model vertices are placed uniformly at random into the [0, 1]2 unit square. each vertex i is assigned uniformly at random sector si, of central angle αi, in a circle of radius ri (with vertex i as the origin). an arc is present from vertex i to any vertex j, if j falls in si. in this work, we study the value of the chromatic number χ(gn), directed clique number ω(gn), and undirected clique number ω2 (gn) for random scaled sector graphs with n vertices, where each vertex spans a sector of α degrees with radius rn = √ln n/n. we prove that for values α < π, as n → ∞ w.h.p., χ(gn) and ω2 (gn) are θ(ln n/ln ln n), while ω(gn) is o(1), showing a clear difference with the random geometric graph model. for α > π w.h.p., χ(gn) and ω2 (gn) are θ (ln n), being the same for random scaled sector and random geometric graphs, while ω(gn) is θ(ln n/ln ln n).
decidability of trajectory-based equations. we consider the decidability of existence of solutions to language equations involving the operations of shuffle and deletion along trajectories. these operations generalize the operations of catenation, insertion, shuffle, quotient, sequential and scattered deletion, as well as many others. our results are constructive in the sense that if a solution exists, it can be effectively represented. we show both positive and negative decidability results. we also briefly consider systems of language equations.
counting h-colorings of partial k-trees. the problem of counting all h-colorings of a graph g with n vertices is considered. while the problem is, in general, #p-complete, we give linear time algorithms that solve the main variants of this problem when the input graph g is a k-tree or, in the case where g is directed, when the underlying graph of g is a k-tree. our algorithms remain polynomial even in the case where k=o(logn) or in the case where the size of h is o(n). our results are easy to implement and imply the existence of polynomial time algorithms for a series of problems on partial k-trees such as core checking and chromatic polynomial computation.