waashk/dblp huggingface dataset:
measuring the performance of asynchronous systems with pafas. based on process algebra for faster asynchronous systems (pafas), a testing-based faster-than relation has previously been developed that compares the worst-case efficiency of asynchronous systems. this approach reveals that pipelining does not improve efficiency in general; that it does so in practice depends on assumptions about the user behaviour. as a case study for testing under such assumptions, we adapt the pafas-approach to a setting where user behaviour is known to belong to a specific, but often occurring class of request-response behaviours.just as the testing preorder in classical testing, the original faster-than relation is qualitative. we give it a quantitative reformulation for the general approach; based on this, we demonstrate in our case study how to determine an asymptotic performance measure for finite-state processes. with this result, we can show that pipelining indeed improves efficiency in our setting, and we discuss additional examples.
the permutation-path coloring problem on trees. in this paper we first show that the permutation-path coloring problem is np-hard even for very restrictive instances like involutions, which are permutations that contain only cycles of length at most two, on both binary trees and on trees having only two vertices with degree greater than two, and for circular permutations, which are permutations that contain exactly one cycle, on trees with maximum degree greater than or equal to 4. we calculate a lower bound on the average complexity of the permutation-path coloring problem on arbitrary networks. then we give combinatorial and asymptotic results for the permutation-path coloring problem on linear networks in order to show that the average number of colors needed to color any permutation on a linear network on n vertices is n/4 + o(n). we extend these results and obtain an upper bound on the average complexity of the permutation-path coloring problem on arbitrary trees, obtaining exact results in the case of generalized star trees. finally we explain how to extend these results for the involutions-path coloring problem on arbitrary trees.
operational and abstract semantics of the query language g-log. the amount and variety of data available electronically have dramatically increased in the last decade; however, data and documents are stored in different ways and do not usually show their internal structure. in order to take full advantage of the topological structure of digital documents, and particularly web sites, their hierarchical organization should be exploited by introducing a notion of query similar to the one used in database systems. a good approach, in that respect, is the one provided by graphical query languages, originally designed to model object bases and later proposed for semistructured data, like g-log. the aim of this paper is to provide suitable graph-based semantics to this language, supporting both data structure variability and topological similarities between queries and document structures. a suite of operational semantics based on the notion of bisimulation is introduced both at the concrete level (instances) and at the abstract level (schemata), giving rise to a semantic framework that benefits from the cross-fertilization of tools originally designed in quite different research areas (databases, concurrency, logics, static analysis).
pc grammar systems with five context-free components generate all recursively enumerable languages. parallel communicating grammar systems (pc grammar systems, in short) are language generating devices consisting of several context-free grammars which work synchronously on their own sentential forms and communicate the generated strings to each other by request. these systems with eleven components are known to have the power of the turing machines. we considerably improve this result, proving that five components suffice in order to generate any recursively enumerable language.
parallel communicating grammar systems with bounded resources. in this paper we study size properties of context-free returning parallel communicating grammar systems (pc grammar systems). we show that for each context-free returning pc grammar system an equivalent system of this type can be constructed, where the total number of symbols used for describing a component can be bounded by a reasonably small constant. since context-free returning pc grammar systems determine the class of recursively enumerable languages, the result also demonstrates that the recursively enumerable language class can be economically described in terms of parallel communicating grammar systems.
biinfinite words with maximal recurrent unbordered factors. a finite non-empty word z is said to be a border of a finite non-empty word w if w = uz = zυ for some non-empty words u and υ. a finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. in this paper, we give two characterizations of the biinfinite words of the form ωuυuω, where u and υ are finite words, in terms of its unbordered factors.the main result of the paper states that the words of the form ωuυuω are precisely the biinfinite words w=...a-2a-1a0a1a2... for which there exists a pair (l0, r0) of integers with l0 < r0 such that, for every integers l ≤ l0 and r ≥ r0, the factor al... al0...ar0...ar is a bordered word.the words of the form ωuυuω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences "to the left" in w) of maximal length that is also a right recurrent unbordered factor of maximal length. this last result is a biinfinite analogue of a result known for infinite words.
adding symbolic information to picture models: definitions and properties. in the paper we propose extensions of some picture models, such as colored, drawn and pixel pictures. such extensions are conceived by observing that a picture may embed more information than the shape, such as colors, labels, etc., which can be represented by a symbol from an alphabet and can be associated to segments, points or pixels. new interesting issues derived from the introduction of symbols will be investigated together with some complexity and decidability questions for the proposed extensions.
frozen development in graph coloring. we define the 'frozen development' of coloring random graphs. we identify two nodes in a graph as frozen if they are of the same color in all legal colorings and define the collapsed graph as the one in which all frozen pairs are merged. this is analogous to studies of the development of a backbone or spine in sat (the satisfiability problem). we first describe in detail the algorithmic techniques used to study frozen development. we present strong empirical evidence that freezing in 3-coloring is sudden. a single edge typically causes the size of the graph to collapse in size by 28%. we also use the frozen development to calculate unbiased estimates of probability of colorability in random graphs. this applies even where this probability is infinitesimal such as 10-300, although our estimates might be subject to very high variance. we investigate the links between frozen development and the solution cost of graph coloring. in sat, a discontinuity in the order parameter has been correlated with the hardness of sat instances, and our data for coloring are suggestive of an asymptotic discontinuity. the uncolorability threshold is known to give rise to hard test instances for graph-coloring. we present empirical evidence that the cost of coloring threshold graphs grows exponentially, when using either a specialist coloring program, or encoding into sat, or even when using the best of both techniques. hard instances seem to appear over an increasing range of graph connectivity as graph size increases. we give theoretical and empirical evidence to show that the size of the smallest uncolorable subgraphs of threshold graphs becomes large as the number of nodes in graphs increases. finally, we discuss some of the issues involved in applying our work to the statistical mechanics analysis of coloring.
the monadic second-order logic of graphs xiv: uniformly sparse graphs and edge set quantifications. we consider the class usk of uniformly k-sparse simple graphs, i.e., the class of finite or countable simple graphs, every finite subgraph of which has a number of edges bounded by k times the number of vertices. we prove that for each k, every monadic second-order formula (intended to express a graph property) that uses variables denoting sets of edges can be effectively translated into a monadic second-order formula where all set variables denote sets of vertices and that expresses the same property of the graphs in usk. this result extends to the class of uniformly k-sparse simple hypergraphs of rank at most m (for any k and m).it follows that every subclass of usk consisting of finite graphs of bounded clique-width has bounded tree-width. clique-width is a graph complexity measure similar to tree-width and relevant to the construction of polynomial algorithms for np-complete problems on special classes of graphs.
constructive metrisability in point-free topology. the notion of elementary diameter is introduced to provide, in the context of locale theory, a constructive notion of metrisability, besides foundational aspects, elementary diameters allow to express metrisability in locales more simply with respect to the existing (non-constructive) approach based on diameters. by relying on the presentation of locale theory provided by formal topology, the notions to be presented may be conceived as phrased within (martin-löf) type theory. a type-theoretic version of urysohn metrisation theorem is thus obtained. as an application, a set (data type) of indexes for the points of locally compact metrisable formal spaces is shown to exist.
the number of binary words avoiding abelian fourth powers grows exponentially. we show that the number of binary words of length n avoiding abelian fourth powers grows faster than rn, where r = 21/16.
pattern avoidance: themes and variations. we review results concerning words avoiding powers, abelian powers or patterns. in addition we collect/pose a large number of open problems.
on the size of the inverse neighborhoods for one-dimensional reversible cellular automata. in this paper we investigate the possible neighborhood size of the inverse automaton of some types of one-dimensional reversible cellular automata. considering only the case when the local function is a size two map, we give a quadratic upper bound for the neighborhood size of the inverse automaton. we show that this bound can be lowered in some particular cases, and give an algorithm for computing these better bounds.
the non-parametrizability of the word equation =: a short proof. although makanin proved the problem of satisfiability of word equations to be decidable, the general structure of solutions is difficult to describe. in particular, hmelevskii proved that the set of solutions of xyz = zvx cannot be described using only finitely many parameters, contrary to the case of equations in three unknowns. in this paper we give a short, elementary proof of hmelevskii's result.
on the power of parallel communicating watson-crick automata systems. parallel communicating watson-crick automata systems were introduced in [e. czeizler, e. czeizler, parallel communicating watson-crick automata systems, in: z. ésik, z. fülöp (eds.), proc. automata and formal languages, dobogókö, hungary, 2005, pp. 83-96] as possible models of dna computations. this combination of watson-crick automata and parallel communicating systems comes as a natural extension due to the new developments in dna manipulation techniques. it is already known, see [d. kuske, p. weigel, the role of the complementarity relation in watson-crick automata and sticker systems, dlt 2004, lecture notes in computer science, vol. 3340, auckland, new zealand, 2004, pp. 272-283], that for watson-crick finite automata, the complementarity relation plays no active role. however, this is not the case when considering parallel communicating watson-crick automata systems. in this paper we prove that non-injective complementarity relations increase the accepting power of these systems. we also prove that although watson-crick automata are equivalent to two-head finite automata, this equivalence is not preserved when comparing parallel communicating watson-crick automata systems and multi-head finite automata.
on polynomial-time approximation algorithms for the variable length scheduling problem. this paper may be viewed as a corrigendum as well as an extension of the paper by (czumaj et al., theoret. comput. sci. 262 (1-2), (2001) 569-582) where they deal with the variable length scheduling problem (vlsp) with parameters k1,k2, denoted vlsp(k1,k2). in the current paper, we first discuss an error in the analysis of one of the approximation algorithms described in (czumaj et al., theoret. comput. sci. 262 (1-2), (2001) 569-582), where an approximation algorithm for vlsp(k1,k2), k1 < k2, was presented and it was claimed that the algorithm achieves the approximation ratio of 1 + (k1(k2-k1))/k2. in this paper we give a problem instance for which the same algorithm obtains the approximation ratio ≈ k2/k1. we then present two simple approximation algorithms, one for the case k1 = 1 with an approximation ratio of 2, and one for the case k1 > 1 with an approximation ratio of 2 + (k2/2k1). this corrects the result claimed in (czumaj et al., theoret. comput. sci. 262 (1-2), (2001) 569-582).
testing hypergraph colorability. we study the problem of testing properties of hypergraphs. the goal of property testing is to distinguish between the case whether a given object has a certain property or is "far away" from the property. we prove that the fundamental problem of l-colorability of k-uniform hypergraphs can be tested in time independent of the size of the hypergraph. we present a testing algorithm that examines only (k l/ε)o(k) entries of the adjacency matrix of the input hypergraph, where ε is a distance parameter independent of the size of the hypergraph. the algorithm tests only a constant number of entries in the adjacency matrix provided that l, k, and ε are constants. this result is a generalization of previous results about testing graph colorability.
a combinatorial problem on trapezoidal words. in this paper, we investigate some combinatorial properties concerning the family of the so-called trapezoidal words. trapezoidal words, considered in de luca (theoret. comput. sci. 218 (1999) 13-39 are finite words over the two-letter alphabet a={a,b} whose subword complexity has the same behaviour as that of finite sturmian words. in de luca (theoret. comput. sci. 218 (1999) 13-39 it has been proved that the family of finite sturmian words is properly contained in that one of trapezoidal words. we carry on with the studying of the family of trapezoidal words and, in particular, of its relation with that one of finite sturmian words.
on quasi-open bisimulation. quasi-open bisimilarity is a variant of the open bisimilarity based on a closer examination of the observationality of local names. the paper investigates two alternative characterizations of the quasi-open bisimilarity and provides a complete system for the weak quasi-open congruence.
on the structure of the counting function of sparse context-free languages. we give an exact description of the counting function of a sparse context-free language. let l be a sparse context-free language and let fl be its counting function. then there exist polynomials p0, p1,...,pk - 1, with rational coefficients, and an integer constant k0, such that for any n ≥ k0 one has fl (n) = pj (n) where j is such that j ≡ n mod k. as a consequence one can easily show the decidability of some questions concerning sparse context-free languages. finally, we show that for any sparse context-free language l there exists a regular language l' such that for any n ≥ 0 one has fl (n) = fl' (n) and, therefore, fl is rational.
well quasi-orders and context-free grammars. let g be a context-free grammar and let l be the language of all the words derived from any variable of g. we prove the following generalization of higman's theorem: any division order on l is a well quasi-order on l. we also give applications of this result to some quasi-orders associated with unitary grammars.
additive symmetries: the non-negative case. an additive symmetric value b of a with respect to c satisfies c = (a + b)/2. existence and uniqueness of such b are basic properties in exact arithmetic that fail when a and b are floating point numbers and the computation of c performed in ieee-754-like arithmetic. we exhibit and prove conditions on the existence, the uniqueness and the consistency of an additive symmetric value when b and c have the same sign.
finite automata for compact representation of tuple dictionaries. a generalization of the dictionary data structure is described, called tuple dictionary. a tuple dictionary represents the mapping of n-tuples of strings to some value. this data structure is motivated by practical applications in speech and language processing, in which very large instances of tuple dictionaries are used to represent language models. a technique for compact representation of tuple dictionaries is presented. the technique can be seen as an application and extension of perfect hashing by means of finite-state automata. preliminary practical experiments indicate that the technique yields considerable and important space savings of up to 90% in practice.
determination of q-convex sets by x-rays. in this paper, the problem of the determination of lattice sets from x-rays is studied. we define the class of q-convex sets along a set d of directions which generalizes classical lattice convexity and we prove that for any d, the x-rays along d determine all the convex sets if and only if it determines all the q-convex sets along d. as a consequence, any algorithm which reconstructs q-convex sets from x-rays can be used to reconstruct convex lattice sets from x-rays along directions which provide uniqueness. this gives a constructive answer to the discrete version of hammer's x-ray problem.
the chords' problem. the chords' problem is a variant of an old problem of computational geometry: given a set of points of rn, one can easily build the multiset of the distances between the points of the set but the converse construction is known, for a longtime, as to be difficult. the problem that we are going to investigate is also a converse construction with the difference that it is not one of the distances' multisets but one of the chords' multisets. in dimension 1, the old distances' problem and the chords' problem coincide with each other whereas in other dimensions, the chords' multisets contain more information on the sets than their distances' multisets. this paper provides, in dimension 1, two different algorithms to reconstruct the set of points according to their chords' multiset. the first one is given for its effectiveness in spite of an uncertain complexity whereas the second one is the first polynomial algorithm solving the chords' problem. at least, we will explain how to transform a chords' problem in dimension n into an equivalent chords' problem in dimension 1.
some necessary clarifications about the chords' problem and the partial digest problem. we state in previous paper [a. daurat, y. gérard, m. nivat, the chords' problem, theoret. comput. sci. 282(2) (2002) 319-336] that the chords' problem can be solved in polynomial time. this result is however ambiguous and some people have been abused because the encoding of the data has not been given. the correctness of the result requires to specify the encoding of the data that we have used and to highlight the difference with the usual encoding implicitly considered in partial digest problem.
parallel construction of perfect matchings and hamiltonian cycles on dense graphs. the intensive study of fast parallel and distributed algorithms for various routing (and communications) problems on graphs with good expanding properties \ref{pu1}, \ref{pu2}, \ref{ss} is being carried out recently. the parallel solutions for expanders that already exist \ref{pu 2} required an extensive randomization and an application of a randomized subroutine for the maximum matching problem. in this paper we attack the problem of fast parallel algorithms for constructing perfect matchings and hamiltonian cycles on dense graph-networks (undirected graphs of minimal degree ${|v|\over 2}$). somewhat surprisingly, we design fast deterministic parallel algorithms for constructing both the perfect matchings and the hamiltonian cycles on the dense graphs. the algorithm for constructing perfect matchings on dense graphs works in $o(\log^2 n)$ parallel time and $o(n^8)$ processors or $o(\log^4 n)$ parallel time and $o(n^4)$ processors on a crew-pram. the algorithm for constructing hamiltonian cycles on dense graphs works in $o(\log^5 n)$ parallel time and $o(n^4)$ processors on a crew-pram. our method of the parallel solution involves a development of new dense graph combinatorics suitable for fast parallelization.
on the asymptotic behaviour of primitive recursive algorithms. this paper develops a new semantics (the trace of a computation) that is used to study intensional properties of primitive recursive algorithms. it gives a new proof of the "ultimate obstination theorem" of l. colson and extends it to the case when mutual recursion is permitted. the ultimate obstination theorem fails when other data types (e.g. lists) are used. i define another property (the backtracking property) of the same nature but which is weaker than the ultimate obstination. this property is proved for every primitive recursive algorithm using any kind of data types. copyright 2001 elsevier science b.v.
an efficient parallel algorithm for the minimal elimination ordering (meo) of an arbitrary graph. the first efficient parallel algorithm for computing minimal elimination ordering (meo) of an arbitrary graph is designed. the algorithm works in o(log/sup 3/n) parallel time and o(nm) processors on a concurrent-read-concurrent-write parallel random-access machine (crcw pram) for an n-vertex, m-edge graph and is optimal up to polylogarithmic factor with respect to the best sequential algorithm of d. rose et. al. (siam j. comput., vol.5, p.266-83, 1976). as an application, the first efficient parallel solution to the problem of minimal fill-in for arbitrary graphs is given. the method of solution involves the development of new techniques for solving the connected minimal set system problem and combining them with some new divide-and-conquer methods.
decidability results for primitive recursive algorithms. in this paper i use the notion of trace defined in (theoret. comput. sci. 266 (2001) 159) to extend coquand's constructive proof (c. r. acad. sci. ser. i 314 (1992)) of the ultimate obstination theorem of colson to the case when mutual recursion is allowed. as a by-product i get an algorithm that computes the value of a primitive recursive combinator applied to lazy integers (infinite or partially undefined arguments may appear). i also get, as coquand got from his proof, that, even when mutual recursion is allowed, there is no primitive recursive definition f such that f(sn(⊥)) = sn2 (⊥).