waashk/dblp huggingface dataset:
axiomatizations for probabilistic finite-state behaviors. we study a process calculus which combines both nondeterministic and probabilistic behavior in the style of segala and lynch's probabilistic automata. we consider various strong and weak behavioral equivalences, and we provide complete axiomatizations for finite-state processes, restricted to guarded recursion in case of the weak equivalences. we conjecture that in the general case of unguarded recursion the ''natural'' weak equivalences are undecidable. this is the first work, to our knowledge, that provides a complete axiomatization for weak equivalences in the presence of recursion and both nondeterministic and probabilistic choice.
compact and tractable automaton-based representations of time granularities. most approaches to time granularity proposed in the literature are based on algebraic and logical formalisms [j. euzenat, a. montanari, time granularity, in: m. fisher, d. gabbay, l. vila (eds.), handbook of temporal reasoning in artificial intelligence, elsevier, 2005, pp. 59-118]. here we follow an alternative automaton-based approach, originally outlined in [u. dal lago, a. montanari, calendars, time granularities, and automata, in: proceedings of the 7th international symposium on spatial and temporal databases, sstd, in: lncs, vol. 2121, springer, 2001, pp. 279-298], which makes it possible to deal with infinite time granularities in an effective and efficient way. such an approach provides a neat solution to fundamental algorithmic problems, such as the granularity equivalence and granule conversion problems, which have been often neglected in the literature. in this paper, we focus our attention on two basic optimization problems for the automaton-based representation of time granularities, namely, the problem of computing the smallest representation of a time granularity and that of computing the most tractable representation of it, that is, the one on which crucial algorithms, such as granule conversion algorithms, run fastest.
space-aware ambients and processes. resource control has attracted increasing interest in foundational research on distributed systems. this paper focuses on space control and develops an analysis of space usage in the context of an ambient calculus with bounded capacities and weighed processes, where migration and activation require space. a type system controls the dynamics of the calculus by providing static guarantees that the intended capacity bounds are preserved throughout the computation. we investigate various term-level mechanisms to complement the typed control on the dynamics of space allocation and acquisition, and study their consequences on the semantic theory of the calculus.
equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time. a program schema defines a class of programs, all of which have identical statement structure, but whose expressions may differ. we define a class of syntactic similarity binary relations between linear structured schemas, which characterise schema equivalence for structured schemas that are linear, free and liberal. in this paper we report that similarity implies equivalence for linear schemas, and that a near-converse holds for schemas that are linear, free and liberal. we also show that the similarity of two linear schemas is polynomial-time decidable. our main result considerably extends the class of program schemas for which equivalence is known to be decidable, and suggests that linearity is a constraint worthy of further investigation.
a compositional natural semantics and hoare logic for low-level languages. the advent of proof-carrying code has generated significant interest in reasoning about low-level languages. it is widely believed that low-level languages with jumps must be difficult to reason about because of being inherently non-modular. we argue that this is untrue. we take it seriously that, unlike statements of a high-level language, pieces of low-level code are multiple-entry and multiple-exit. and we define a piece of code as consisting of either a single labelled instruction or a finite union of pieces of code. thus we obtain a compositional natural semantics and a matching hoare logic for a basic low-level language with jumps. by their simplicity and intuitiveness, these are comparable to the standard natural semantics and hoare logic of while. the hoare logic is sound and complete wrt the semantics and allows for compilation of proofs of the hoare logic of while.
polynomial time algorithm for an optimal stable assignment with multiple partners. this paper considers the many-to-many version of the stable marriage problem where each man and woman has a strict preference ordering on the members of the opposite sex that he or she considers acceptable. further, each man and woman wishes to be matched to as many acceptable partners as possible, up to his or her specified quota. in this setup, a polynomial time algorithm for finding a stable matching that minimizes the sum of partner ranks across all men and women is provided. it is argued that this sum can be used as an optimality criterion for minimizing total dissatisfaction if the preferences over partner-combinations satisfy a no-complementarities condition. the results in this paper extend those already known for the one-to-one version of the problem.
adding recursion to dpi. dpi is a distributed version of the pi-calculus, in which processes are explicitly located, and a migration construct may be used for moving between locations. we argue that adding a recursion operator to the language increases significantly its descriptive power. but typing recursive processes requires the use of potentially infinite types. we show that the capability-based typing system of dpi can be extended to co-inductive types so that recursive processes can be successfully supported. we also show that, as in the pi-calculus, recursion can be implemented via iteration. this translation improves on the standard ones by being compositional but still requires co-inductive types and comes with a significant migration overhead in our distributed setting.
a rewriting logic framework for operational semantics of membrane systems. existing results in membrane computing refer mainly to p systems' characterization of turing computability, also to some polynomial solutions to np-complete problems by using an exponential workspace created in a ''biological way''. in this paper we define an operational semantics of a basic class of p systems, and give two implementations of the operational semantics using rewriting logic. we present some results regarding these implementations, including two operational correspondence results, and discuss why these implementations are relevant in order to take advantage of good features of both structural operational semantics and rewriting logic.
the rewriting logic semantics project. rewriting logic is a flexible and expressive logical framework that unifies algebraic denotational semantics and structural operational semantics (sos) in a novel way, avoiding their respective limitations and allowing succinct semantic definitions. the fact that a rewrite logic theory's axioms include both equations and rewrite rules provides a useful ''abstraction dial'' to find the right balance between abstraction and computational observability in semantic definitions. such semantic definitions are directly executable as interpreters in a rewriting logic language such as maude, whose generic formal tools can be used to endow those interpreters with powerful program analysis capabilities.
generating labeled planar graphs uniformly at random. we present a deterministic polynomial time algorithm to sample a labeled planar graph uniformly at random. our approach uses recursive formulae for the exact number of labeled planar graphs with n vertices and m edges, based on a decomposition into 1-, 2-, and 3-connected components. we can then use known sampling algorithms and counting formulae for 3-connected planar graphs.
hybrid commitments and their applications to zero-knowledge proof systems. we introduce the notion of hybrid trapdoor commitment schemes. intuitively a hybrid trapdoor commitment scheme is a primitive which can be either an unconditionally binding commitment scheme or a trapdoor commitment scheme depending on the distribution of commitment parameters. moreover, such two possible distributions are computationally indistinguishable. hybrid trapdoor commitments are related but different with respect to mixed commitments (introduced by damgard and nielsen at crypto 2002). in particular hybrid trapdoor commitments can either be polynomially trapdoor commitments or unconditionally binding commitments, while mixed commitments can be either trapdoor commitments or extractable commitments. in this paper we show that strong notions (e.g., simulation sound, multi-trapdoor) of hybrid trapdoor commitments admit constructions based on the sole assumption that one-way functions exist as well as efficient constructions based on standard number-theoretic assumptions. to further stress the difference between hybrid and mixed commitments, we remark here that mixed commitments seem to require stronger theoretical assumptions (and the known number-theoretic constructions are less efficient). our main result, is to show how to construct concurrent and simulation-sound zero-knowledge proof systems (in contrast to the arguments recently presented in [i. damgard, efficient concurrent zero-knowledge in the auxiliary string model, in: advances in cryptology - eurocrypt'00, in: lecture notes in computer science, vol. 1807, springer-verlag, 2000, pp. 418-430; p. mackenzie, k. yang, on simulation-sound trapdoor commitments, in: advances in cryptology - eurocrypt'04, in: lecture notes in computer science, vol. 3027, springer-verlag, 2004, pp. 382-400; r. gennaro, multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks, in: advances in cryptology - crypto'04, in: lecture notes in computer science, vol. 3152, springer-verlag, 2004, pp. 220-236]) in the common reference string model. we crucially use hybrid trapdoor commitments since we present general constructions based on the sole assumption that one-way functions exist and very efficient constructions based on number-theoretic assumptions.
characterizations of recognizable picture series. the theory of two-dimensional languages as a generalization of formal string languages was motivated by problems arising from image processing and pattern recognition, and also concerns models of parallel computing. here we investigate power series on pictures. these are functions that map pictures to elements of a semiring and provide an extension of two-dimensional languages to a quantitative setting. we assign weights to different devices, ranging from picture automata to tiling systems. we will prove that, for commutative semirings, the behaviours of weighted picture automata are precisely alphabetic projections of series defined in terms of rational operations, and also coincide with the families of series characterized by weighted tiling or weighted domino systems.
approximating the maximum clique minor and some subgraph homeomorphism problems. we consider the ''minor'' and ''homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest h such that the input graph (on n vertices) has a minor isomorphic to k"h or a subgraph homeomorphic to k"h, respectively, as well as the problem of finding the corresponding subgraphs. we term them as the maximum clique minor problem and the maximum homeomorphic clique problem, respectively. we observe that a known result of kostochka and thomason supplies an o(n) bound on the approximation factor for the maximum clique minor problem achievable in polynomial time. we also provide an independent proof of nearly the same approximation factor with explicit polynomial-time estimation, by exploiting the minor separator theorem of plotkin et al. next, we show that another known result of bollobas and thomason and of komlos and szemeredi provides an o(n) bound on the approximation factor for the maximum homeomorphic clique achievable in polynomial time. on the other hand, we show an @w(n^1^/^2^-^o^(^1^/^(^l^o^g^n^)^^^@c^)) lower bound (for some constant @c, unless np@?zptime(2^(^l^o^g^n^)^^^o^^^(^^^1^^^))) on the best approximation factor achievable efficiently for the maximum homeomorphic clique problem, nearly matching our upper bound. finally, we derive an interesting trade-off between approximability and subexponential time for the problem of subgraph homeomorphism where the guest graph has maximum degree not exceeding three and low treewidth.
intersecting periodic words. let a=a[1..2v] be a word which is a square and for which a[1..2u] is also a square and a[k+1..min(k+2w,2v)] has period w where u
the maximum agreement forest problem: approximation algorithms and computational experiments. there are various techniques for reconstructing phylogenetic trees from data, and in this context the problem of determining how distant two such trees are from each other arises naturally. various metrics for measuring the distance between two phylogenies have been defined. another way of comparing two trees t and u is to compute the so called maximum agreement forest of these trees. informally, the number of components of an agreement forest tells how many edges from each of t and u need to be cut so that the resulting forests agree, after performing all forced edge contractions. this problem is np-hard even when the input trees have maximum degree 2. hein et al. [j. hein, t. jiang, l. wang, k. zhang, on the complexity of comparing evolutionary trees, discrete applied mathematics 71 (1996) 153-169] presented an approximation algorithm for it, claimed to have performance ratio 3. we show that the performance ratio of the algorithm proposed by hein et al. is 4, and we also present two new 3-approximation algorithms for this problem. we show how to modify one of the algorithms into a (d+1)-approximation algorithm for trees with bounded degree d, d>=2. finally, we report on some computational experiments comparing the performance of the algorithms presented in this paper.
lattice grids and prisms are antimagic. an antimagic labelling of a finite undirected simple graph with m edges and n vertices is a bijection from the set of edges to the integers 1,...,m such that all n vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. a graph is called antimagic if it has an antimagic labelling. in 1990, hartsfield and ringel conjectured that every connected graph, but k"2, is antimagic. in [t.-m. wang, toroidal grids are antimagic, in: proc. 11th annual international computing and combinatorics conference, cocoon'2005, in: lncs, vol. 3595, springer, 2005, pp. 671-679], wang showed that the toroidal grids (the cartesian products of two or more cycles) are antimagic. two open problems left in wang's paper are about the antimagicness of lattice grid graphs and prism graphs, which are the cartesian products of two paths, and of a cycle and a path, respectively. in this article, we prove that these two classes of graphs are antimagic, by constructing such antimagic labellings.
an external-memory depth-first search algorithm for general grid graphs. graph data in modern scientific and engineering applications are often too large to fit in the computer's main memory. input/output (i/o) complexity is a major research issue in this context. minimization of the number of i/o operations (in external memory graph algorithms) is the main focus of current research while classical (internal memory) graph algorithms were designed to minimize temporal complexity. in this paper, we propose an external memory depth first search algorithm for general grid graphs. the i/o-complexity of the algorithm is o(sort(n)log"2nm), where n=|v|+|e|, sort(n)=@q(nblog"m"/"bnb) is the sorting i/o-complexity, m is the memory size, and b is the block size. the best known algorithm for this class of graph is the standard (internal memory) dfs algorithm with appropriate block (sub-grid) i/o-access. its i/o-complexity is o(n/b). recently, the authors proposed an o(sort(n)) algorithm for solid grid graphs.
fast algorithms for computing jones polynomials of certain links. we give a fast algorithm for computing jones polynomials of 2-bridge links. given the tait graph with n edges of a 2-bridge diagram, this algorithm runs with o(n) additions and multiplications in polynomials of degree o(n), namely in o(n^2logn) time. we also propose an algorithm that, given the tait graph with n edges of a closed 3-braid diagram, computes the jones polynomial of the closed 3-braid link in o(n^2logn) time.
the cell probe complexity of succinct data structures. we consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). in this model, the goal is to represent n-bit data with s=n+r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. in this paper, we consider the case of succinct representations, where s=n+r for some redundancyr@?n. for a boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy-query time tradeoff of the form (r+1)t>=@w(n/logn). in particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). we show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain (r+1)t>=@w(n) for certain problems. previously, no @w(m) lower bounds were known on t in the general model for explicit boolean problems, even for very small redundancies. by restricting our attention to systematic or index structures @f satisfying @f(x)=x@?@f^*(x) for some map @f^* (where @? denotes concatenation), we show similar lower bounds on the redundancy-query time tradeoff for the natural data structuring problems of prefix sum and substring search.
reversal and transposition medians. in determining phylogenetic trees using gene order information, medians provide a powerful alternative to pairwise distances. on the other hand, both breakpoint and reversal medians are np-hard to compute and the use of medians has been limited to relatively closely related genomes. in this paper, we show that in spite of the greater non-uniqueness of reversal medians, compared to breakpoint medians, medians of moderately distant genomes are often widely spread. this means that regardless of which approximation algorithms one may devise for computing reversal medians, the genomes need to be closely related for phylogenetic tree computations to be successful. to show this, we use results on transposition medians, which behave similarly, and also support our claims with simulations and a real data example with widely spread medians.
a new conceptual framework for analog computation. in this paper we show how to explore the classical theory of computability using the tools of analysis: a differential scheme is substituted for the classical recurrence scheme and a limit operator is substituted for the classical minimization. we show that most relevant problems of computability over the non-negative integers can be dealt with over the reals: elementary functions are computable, turing machines can be simulated, the hierarchy of non-computable functions can be represented (the classical halting problem being solvable at some level). the most typical concepts in analysis become natural in this framework. the most relevant question is posed: can we solve open problems of classical computability and computational complexity using, as popper says, the toolbox of analysis?
on the (n, t)-antipodal gray codes. an n-bit gray code is a circular listing of all 2^nn-bit binary strings in which consecutive strings differ at exactly one bit. for n@?t@?2^n^-^1, an (n,t)-antipodal gray code is a gray code in which the complement of any string appears t steps away from the string, clockwise or counterclockwise. killian and savage proved that an (n,n)-antipodal gray code exists when n is a power of 2 or n=3, and does not exist for n=6 or odd n>3. motivated by these results, we prove that for odd n>=3, an (n,t)-antipodal gray code exists if and only if t=2^n^-^1-1. for even n, we establish two recursive constructions for (n,t) codes from smaller (n^',t^'). consequently, various (n,t)-antipodal gray codes are found for even n's. examples are for t=2^n^-^1-2^k with k odd and 1@?k@?n-3 when n>=4, for t=2^n^-^k when n>=2k with 1@?k@?3, for t=n when n=2^k>=2 (an alternative proof for killian and savage's result) ...etc.
weighted asynchronous cellular automata. we study weighted systems whose behavior is described as a formal power series over a free partially commutative or trace monoid. it is shown that the interleaving approach and the distributed approach are equivalent in this setting. this holds, both in the deterministic and in the nondeterministic case. consequently, we obtain a particularly simple class of sequential weighted automata that already have full expressive power.
ranks of graphs: the size of acyclic orientation cover for deadlock-free packet routing. given a graph g, the problem is to determine an acyclic orientation of g which minimizes the maximal number of changes of orientation along any shortest path in g. the corresponding value is called the rank of the graph g. the motivation for this graph theoretical problem comes from the design of deadlock-free packet routing protocols [g. tel, deadlock-free packet switching networks, in: introduction to distributed algorithms, cambridge university press, cambridge, uk, 1994 (chapter 5)]. this acyclic orientation covering problem on the shortest path systems has been studied in [j.-c. bermond, m. di ianni, m. flammini, s. perennes, acyclic orientations for deadlock prevention in interconnection networks, in: 23rd international workshop on graph-theoretic concepts in computer science (wg), in: lecture notes in computer science, vol. 1335, springer-verlag, 1997, pp. 52-64] where it was shown that the general problem of determining the rank is np-complete and some upper and lower bounds on the rank were presented for particular topologies, such as grids, tori and hypercubes. the main unresolved problem stated in [j.-c. bermond, m. di ianni, m. flammini, s. perennes, acyclic orientations for deadlock prevention in interconnection networks, in: 23rd international workshop on graph-theoretic concepts in computer science (wg), in: lecture notes in computer science, vol. 1335, springer-verlag, 1997, pp. 52-64] was to determine the rank values for other well-known interconnection networks and also for more general classes of graphs. in this paper we give a general lower bound argument for the rank problem and apply it to the class of involution-generated cayley graphs which among others include hypercubes, star graphs, pancake graphs and transposition-tree based graphs [s.b. akers, b. krishnamurthy, a group-theoretic model for symmetric interconnection networks, ieee transactions on computers 38 (4) (1989) 555-565]. we also present a large class lcp"("t","s"p") of graphs with constant rank. this class of graphs is defined as the layered cross product [s. even, a. litman, layered cross product-a technique to construct interconnection networks, networks 29 (1997) 219-223] of layered trees and series-parallel graphs and includes among others butterflies, benes networks, fat-trees and meshes of trees. for some special topologies, improved lower bounds on the rank are also presented. we consider some of the modified versions of the rank problem as well.