waashk/dblp huggingface dataset:
deterministic broadcasting time with partial knowledge of the network. we consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. each node υ knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from υ. apart from that, each node knows the maximum degree δ of the network. one node of the network, called the source, has a message which has to reach all other nodes. we adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. this is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time.we show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. while for knowledge radius 0, minimum broadcasting time is θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. our main results concern knowledge radius 1. we develop fast broadcasting algorithms and analyze their execution time. we also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.
a class of polynomially solvable range constraints for interval analysis without widenings. in this paper, we study the problem of solving integer range constraints that arise in many static program analysis problems. in particular, we present the first polynomial time algorithm for a general class of integer range constraints. in contrast with abstract interpretation techniques based on widenings and narrowings, our algorithm computes, in polynomial time, the optimal solution of the arising fixpoint equations. our result implies that "precise" range analysis can be performed in polynomial time without widening and narrowing operations.
towards the hierarchical verification of reactive systems. the hierarchical design approach for action based systems that is known as action refinement has been studied in the literature extensively. in a paper of m. huhn published in concur 1996 a refinement operator on a linear time logic is presented that mimics precisely a semantic action refinement on synchronisation structures. we present here an alternative approach where our starting point is a process algebraic setting with a syntactic action refinement. we present a refinement operator on the modal mu-calculus that conforms with the process algebraic refinement in the following sense: provided some reasonable conditions are met, the transition system induced by a process term <i>p</i> satisfies a modal mu-calculus-specification ϕ if and only if the system which is induced by a refinement of <i>p</i> satisfies a particular refinement of ϕ. alleviating these conditions, we show that each of the two implications in the equivalence assertion above can be separately proven valid for a particular fragment of the modal mu-calculus. we demonstrate that the obtained results can indeed be used as a hierarchical verification technique. as a further application of our results, we explain how they can be employed as an abstraction technique in order to enhance model checking techniques.
tree-width and the monadic quantifier hierarchy. it is well known that on classes of graphs of bounded tree-width, every monadic second-order property is decidable in polynomial time. the converse is not true without further assumptions. it follows from the work of robertson and seymour, that if a class of graphs k has unbounded tree-width and is closed under minors, then k contains all planar graphs. but on planar graphs, three-colorability is np-complete. hence, if p ≠ np and on k every existential monadic second-order property is in p, then k has bounded tree-width. in other words, for k closed under minors, k is of bounded tree-width iff all monadic second-order properties are decidable in p.in this note we prove that in order to characterize classes of graphs of bounded tree-width where the monadic quantifier hierarchy collapses, closure under minors can be replaced by closure under topological minors. closure under minors of k implies that k is in p, whereas we also note that there is a class of graphs k closed under topological minors which is not even r.e.we also show, that closure under induced subgraphs or even under subgraphs alone does not suffice to show that the collapse of the monadic quantifier hierarchy on k implies that k is of bounded tree-width or clique-width.other characterizations of classes of bounded tree-width in terms of collapses of the monadic quantifier hierarchy to levels above the existential are discussed.
complexity of some problems in positive and related calculi. a problem of recognizing important properties of propositional calculi is considered, and complexity bounds for some decidable properties are found. for a given logical system l, a property p of logical calculi is called decidable over l if there is an algorithm which for any finite set ax of new axiom schemes decides whether the calculus l + ax has the property p or not. in maksimova and voronkov (bull symbol. logic 6 (2000) 118) the complexity of tabularity, pretabularity, and interpolation problems over the intuitionistic logic (int) and over modal logic s4 was studied.in the present paper, positive and positively axiomatizable calculi are investigated. we prove np-completeness of tabularity, dp-hardness of pretabularity and pspace-completeness of interpolation and projective beth's property over the positive fragment int+ of the intuitionistic logic. some complexity bounds for properties of propositional calculi over the intuitionistic or the minimal logic are found.
lower bounds for some decision problems over c. lower bounds for some explicit decision problems over the complex numbers are given. the decision problems considered are certain zero-dimensional subsets of nc, and can be assimilated to a countable family of polynomials gi. more precisely, one should decide for input (i,x) if gi(x)=0. a lower bound for deciding if a polynomial gi vanishes at some x can be derived from a uniform lower bound for the evaluation of all f(gi). that bound is obtained by means of an arithmetic invariant of the roots of gi, the newton diagram of f and other known techniques.
context-free insertion-deletion systems. we consider a class of insertion-deletion systems which have not been investigated so far, those without any context controlling the insertion-deletion operations. rather unexpectedly, we found that context-free insertion-deletion systems characterize the recursively enumerable languages. moreover, this assertion is valid for systems with only one axiom, and also using inserted and deleted strings of a small length. as direct consequences of the main result we found that set-conditional insertion-deletion systems with two axioms generate any recursively enumerable language (this solves an open problem), as well as that membrane systems with one membrane having context-free insertion-deleletion rules without conditional use of them generate all recursively enumerable languages (this improves an earlier result). some open problems are also formulated.
minimizing finite automata is computationally hard. it is known that deterministic finite automata (dfas) can be algorithmically minimized, i.e., a dfa m can be converted to an equivalent dfa m' which has a minimal number of states. the minimization can be done efficiently (in: z. kohavi (ed.), theory of machines and computations, academic press, new york, 1971, pp. 189-196). on the other hand, it is known that unambiguous finite automata and nondeterministic finite automata can be algorithmically minimized too, but their minimization problems turn out to be np-complete and pspace-complete, respectively (siam j. comput. 22(6) (1993) 1117-1141). in this paper, the time complexity of the minimization problem for two restricted types of finite automata is investigated. these automata are nearly deterministic, since they only allow a small amount of nondeterminism to be used. the main result is that the minimization problems for these models are computationally hard, namely np-complete. hence, even the slightest extension of the deterministic model towards a nondeterministic one, e.g., allowing at most one nondeterministic move in every accepting computation or allowing two initial states instead of one, results in computationally intractable minimization problems.
on two-way communication in cellular automata with a fixed number of cells. the effect of adding two-way communication to k cells one-way cellular automata (kc-ocas) on their size of description is studied, kc-ocas are a parallel model for the regular languages that consists of an array of k identical deterministic finite automata (dfas), called cells, operating in parallel. each cell gets information from its right neighbor only. in this paper, two models with different amounts of two-way communication are investigated. both models always achieve quadratic savings when compared to dfas. when compared to a one-way cellular model, the result is that minimum two-way communication can achieve at most quadratic savings whereas maximum two-way communication may provide savings bounded by a polynomial of degree k.
model checking restricted sets of timed paths. in this paper, we study the complexity of model-checking formulas of four important real-time logics (tptl, mtl, mitl, and tctl) over restricted sets of timed paths. the classes of restricted sets of timed paths that we consider are (i) a single finite (or ultimately periodic) timed path, (ii) an infinite set of finite (or infinite) timed paths defined by a finite (or ultimately periodic) path in a region graph, (iii) an infinite set of finite (or infinite) timed paths defined by a finite (or ultimately periodic) path in a zone graph.several results are quite negative: tptl and mtl remain undecidable along region-and zone-paths. on the other hand, we obtained ptime algorithms for model-checking tctl along a region path, and for mtl along a single timed path.
hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations. the relationship between classes of tree-to-tree-series and o-tree-to-tree-series transformations computed by restricted deterministic bottom-up weighted tree transducers is investigated. essentially, these transducers are deterministic bottom-up tree series transducers, except that the former are defined over monoids whereas the latter are defined over semirings and only use the multiplicative monoid thereof. in particular, the common restrictions of nondeletion, linearity, totality, and homomorphism can equivalently be defined for deterministic bottom-up weighted tree transducers.using well-known results of classical tree transducer theory and also new results on deterministic weighted tree transducers, classes of tree-to-tree-series and o-tree-to-tree-series transformations computed by restricted deterministic bottom-up weighted tree transducers are ordered by set inclusion. more precisely, for every commutative monoid and all sensible combinations of the above mentioned restrictions, the inclusion relation of the classes of tree-to-tree-series and o-tree-to-tree-series transformations is completely conveyed by means of hasse diagrams.
compositions of tree series transformations. tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (functional) compositions of such transformations are investigated. it turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations. moreover, it is shown that the class of top-down tree series transformations over a commutative and complete semiring is closed under right-composition with linear, nondeleting top-down tree series transformations. finally, the composition of a boolean, deterministic, total top-down tree series transformation with a linear top-down tree series transformation is shown to be a top-down tree series transformation.
genomic distances under deletions and insertions. as more and more genomes are sequenced, evolutionary biologists are becoming increasingly interested in evolution at the level of whole genomes, in scenarios in which the genome evolves through insertions, deletions, and movements of genes along its chromosomes. in the mathematical model pioneered by sankoff and others, a unichromosomal genome is represented by a signed permutation of a multiset of genes; hannenhalli and pevzner showed that the edit distance between two signed permutations of the same set can be computed in polynomial time when all operations are inversions. el-mabrouk extended that result to allow deletions (or conversely, a limited form of insertions which forbids duplications). in this paper, we extend el-mabrouk's work to handle duplications as well as insertions and present an alternate framework for computing (near) minimal edit sequences involving insertions, deletions, and inversions. we derive an error bound for our polynomial-time distance computation under various assumptions and present preliminary experimental results that suggest that performance in practice may be excellent, within a few percent of the actual distance.
a tight analysis and near-optimal instances of the algorithm of anderson and woll. this paper shows an asymptotically tight analysis of the certified write-all algorithm called awt that was introduced by anderson and woll, siam j. comput. 26 (1997) 1277, and a method for creating near-optimal instances of the algorithm. this algorithm is the best known deterministic algorithm that can be used to simulate n synchronous parallel processors on n asynchronous processors. the algorithm is instantiated with q permutations on {1,...,q}, where q can be chosen from a wide range of values. when implementing a simulation on a specific parallel system with n processors, one would like to select the best possible value of q and the best possible q permutations, in order to maximize the efficiency of the simulation.this paper shows that work complexity of any instance of awt is θ (q2/c ċ n1+logq(c/q)), where q is the number of permutations selected, and c is a value related to their combinatorial properties. the choice of q turns out to be critical for obtaining an instance of the awt algorithm with near-optimal work. for any ε > 0, and any large enough n, work of any instance of the algorithm must be at least n1+(1+n)√2 ln ln n/ln n. under certain conditions, however, that q is about e√1/2 ln n ln ln n and for infinitely many large enough n, this lower bound can be nearly attained by instances of the algorithm that use certain q permutations and have work at most n1+(1+n)√2 ln ln n/ln n. the paper also shows a penalty for not selecting q well. when q is significantly away from e√1/2 ln n ln ln n, then work of any instance of the algorithm with this displaced q must be considerably higher than otherwise.
on the complexity of typechecking top-down xml transformations. we investigate the typechecking problem for xml transformations: statically verifying that every answer to a transformation conforms to a given output schema, for inputs satisfying a given input schema. as typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract xml documents as labeled ordered trees. we focus on simple top-down recursive transformations motivated by xslt and structural recursion on trees. we parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and dtds as input and output schemas. the complexity of the typechecking problems in this scenario ranges from ptime to exptime.
tissue p systems. starting from the way the inter-cellular communication takes place by means of protein channels (and also from the standard knowledge about neuron functioning), we propose a computing model called a tissue p system, which processes symbols in a multiset rewriting sense, in a net of cells. each cell has a finite state memory, processes multisets of symbol-impulses, and can send impulses ("excitations") to the neighboring cells. such cell nets are shown to be rather powerful: they can simulate a turing machine even when using a small number of cells, each of them having a small number of states. moreover, in the case when each cell works in the maximal manner and it can excite all the cells to which it can send impulses, then one can easily solve the hamiltonian path problem in linear time. a new characterization of the parikh images of etol languages is also obtained in this framework. besides such basic results, the paper provides a series of suggestions for further research.
on the computational complexity of reachability in 2d binary images and some basic problems of 2d digital topology. we study the computational complexity of some well-known problems of 2d digital topology. we prove that all considered problems (including reachability in 2d binary images, connectivity, lower homotopy and symmetric homotopy) are in logspace. we prove that reachability in 2d binary images and some other problems are nc1-hard. finally, we prove that most of the considered problems are not in ac0.
membrane systems with carriers. a membrane system is a model of computation which is inspired by some basic features of biological membranes. in this paper we consider another biologically inspired notion, viz., the notion of a carrier (or vehicle), as, e.g., used in gene cloning. we investigate the power of membrane systems where the rules for the evolving of objects are replaced by the rules that carry objects (by vehicles) through membranes. it turns out that these systems (even with a small number of membranes, a small number of carriers, and a small number of passengers taken by carriers) are computationally universal.
finite derivation type for rees matrix semigroups. this paper introduces the topological finiteness condition finite derivation type (fdt) on the class of semigroups. this notion is naturally extended from the monoid case. with this new concept we are able to prove that if a rees matrix semigroup m[s; i, j; p] has fdt then the semigroup s also has fdt. given a monoid s and a finitely presented rees matrix semigroup m[s; i, j; p] we prove that if the ideal of s generated by the entries of p has fdt, then so does m[s; i, j; p]. in particular, we show that, for a finitely presented completely simple semigroup m, the rees matrix semigroup m = m[s; i, j; p] has fdt if and only if the group s has fdt.
diffusion without false rumors: on propagating updates in a byzantine environment. we study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (byzantine) failures. we assume that strictly fewer than t replicas fail, and that each update is initially received by at least t correct replicas. the goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. to achieve this, each correct replica further propagates an update only after receiving it from at least t others. in this way, no correct replica will ever propagate or accept an update that only faulty replicas introduce, since it will receive that update from only the t - 1 faulty replicas.we provide the first analysis of diffusion protocols for such environments. this analysis is fundamentally different from known analyses for the benign case due to our treatment of fully byzantine failures--which, among other things, precludes the use of digital signatures for authenticating forwarded updates. we propose two measures that characterize the efficiency of diffusion algorithms, delay and fan-in, and prove general lower bounds with regards to these measures. we then provide a family of diffusion algorithms that have nearly optimal delay/fan-in product.
a simulation of cellular automata on hexagons by cellular automata on rings. we consider cellular automata on cayley graphs and compare their computational power according to their topology. we prove that cellular automata de)ned over a hexagonal grid can be simulated by cellular automata over a ring.
ideal models of spaces. ideal domains have an elementary order theoretic structure: every element is either compact or maximal. despite this, we establish that (1) they can model any space currently known to possess a countably based model, and (2) the metric spaces with ideal models are exactly the completely metrizable spaces.
minimal invariant sets in a vertex-weighted graph. a weighting of vertices of a graph is admissible if there exists an edge weighting such that the weight of each vertex equals the sum of weights of its incident edges. given an admissible vertex weighting of a graph, an invariant set is an edge set such that the sum of the weights of its edges is the same for every edge weighting, and a nonempty invariant set is minimal if none of its nonempty proper subsets is an invariant set. it is easily seen that every nonempty invariant set is a disjoint union of minimal invariant sets. a graphical characterisation of minimal invariant sets in a bipartite graph is known both in the case the vertex weights are reals and in the case the vertex weights are nonnegative reals. we shall state a graphical characterisation of minimal invariant sets in an arbitrary vertex-weighted graph. moreover, we give a linear algorithm to test an invariant set for minimality. finally, we state a complete axiomatisation of invariant sets and give a polynomial algorithm to find a set of minimal invariant sets that completely characterise the set of all invariant sets.
the regular spaces with countably based models. the regular spaces which may be realized as the set of maximal elements in an ω-continuous dcpo are the polish spaces. in addition, we give a new and conceptually simple model for complete metric spaces. these results enable us to prove that the probabilistic powerdomain of a countably based model of a metric space always contains a copy of the normalized borel measures in their weak topology, and to establish the hierarchy for countably based models.
quantum evolution of words. quantum evolution of words is defined. the existence of the evolution semigroup is proved. the spectrum of its generator is calculated for right-linear grammars and expansion-contraction evolutions.