waashk/dblp huggingface dataset:
generalized approximate counting revisited. a large class of q-distributions is defined on the stochastic model of bernoulli trials in which the probability of success (= advancing to the next level) depends geometrically on the number of trials and the level already reached. if the dependency is only on the level already reached, this is an algorithm called approximate counting. two random variables, x"n (level reached after n trials) and y"k (number of trials to reach level k) are of interest. we rederive known results and obtain new ones in a consistent way, based on generating functions. we also discuss asymptotics. the classical instance of approximate counting is more interesting from a mathematical point of view. on the other hand, if the number of trials also decreases the probability of success (advancing to the next level), then the limits are constants which are straightforward to compute.
on periodicity of two-dimensional words. a two-dimensional word is a function on z^2 with finite number of values. the main problem we are interested in is the periodicity of two-dimensional words satisfying some local conditions. in this paper we prove that every bounded centered function on the infinite rectangular grid is periodic. a function is called centered if the sum of its values in every ball is equal to 0. similar results are obtained for the infinite triangular and hexagonal grids.
optimal computation with non-unitary quantum walks. quantum versions of random walks on the line and the cycle show a quadratic improvement over classical random walks in their spreading rates and mixing times, respectively. non-unitary quantum walks can provide a useful optimisation of these properties, producing a more uniform distribution on the line, and faster mixing times on the cycle. we investigate the interplay between quantum and random dynamics by comparing the resources required, and examining numerically how the level of quantum correlations varies during the walk. we show numerically that the optimal non-unitary quantum walk proceeds such that the quantum correlations are nearly all removed at the point of the final measurement. this requires only o(logt) random bits for a quantum walk of t steps.
an algorithm for recognition of n-collapsing words. a word w over a finite alphabet @s is n-collapsing if for an arbitrary deterministic finite automaton a=, the inequality |@d(q,w)|@?|q|-n holds provided that |@d(q,u)|@?|q|-n for some word u@?@s^+ (depending on a). we prove that the property of n-collapsing is algorithmically recognizable for any given positive integer n. we also prove that the language of all n-collapsing words is context-sensitive.
multiple constraints on three and four words. in this paper we consider several questions related to the defect theorem for sets of three and four words. we start by investigating how large systems of pairwise independent or pairwise non-equivalent equations over three unknowns possessing purely non-periodic solutions can be. in other words, we analyze how weak the cumulative defect effect of such systems is. then, we investigate the maximal size of chains of equations over three or four words such that every time we add a new equation the set of solutions strictly decreases.
completing circular codes in regular submonoids. let m be an arbitrary submonoid of the free monoid a^*, and let x@?m be a variable length code (for short a code). x is weakly m-complete iff any word in m is a factor of some word in x^* [j. neraud, c. selmi, free monoid theory: maximality and completeness in arbitrary submonoids, internat. j. algebra comput. 13 (5) (2003) 507-516]. given a regular submonoid m, and given an arbitrary code x@?m, we are interested in the existence of a weakly m-complete code x@? that contains x. actually, in [j. neraud, completing a code in a regular submonoid, in: acts of mcu'2004, lect. notes comput. sci. 3354 (2005) 281-291; j. neraud, completing a code in a submonoid of finite rank, fund. inform. 74 (2006) 549-562], by presenting a general formula, we have established that, in any case, such a code x@? exists. in the present paper, we prove that any regular circular code x@?m may be embedded into a weakly m-complete one iff the minimal automaton with behavior m has a synchronizing word. as a consequence of our result an extension of the famous theorem of schutzenberger is stated for regular circular codes in the framework of regular submonoids. we study also the behaviour of the subclass of uniformly synchronous codes in connection with these questions.
shuffle operations on discrete paths. we consider the shuffle operation on paths and study some parameters. in the case of square lattices, shuffling with a particular periodic word (of period 2) corresponding to paperfoldings reveals some characteristic properties: closed paths remain closed; the area and perimeter double; the center of gravity moves under a 45^@? rotation and a 2 zoom factor. we also observe invariance properties for the associated dragon curves. moreover, replacing square lattice paths by paths involving 2k@p/n-turns, we find analogous results using more general shuffles.
a conversion algorithm based on the technique of singularization. we present a simple conversion algorithm which allows to rewrite the two-dimensional brun algorithm in terms of the podsypanin algorithm. further, we demonstrate how this conversion process can be used to transfer certain (statistical, approximation) properties from the original to the resulting algorithm.
on undecidability bounds for matrix decision problems. in this paper we consider several reachability problems such as vector reachability, membership in matrix semigroups and reachability problems in piecewise linear maps. since all of these questions are undecidable in general, we work on lowering the bounds for undecidability. in particular, we show an elementary proof of undecidability of the reachability problem for a set of 5 two-dimensional affine transformations. then, using a modified version of a standard technique, we also prove that the vector reachability problem is undecidable for two (rational) matrices in dimension 11. the above result can be used to show that the system of piecewise linear functions of dimension 12 with only two intervals has an undecidable set-to-point reachability problem. we also show that the ''zero in the upper right corner'' problem is undecidable for two integral matrices of dimension 18 lowering the bound from 23.
regular languages and their generating functions: the inverse problem. the technique of determining a generating function for an unambiguous context-free language is known as the schutzenberger methodology. for regular languages, elena barcucci et al. proposed an approach for inverting this methodology based on soittola's theorem. this idea allows a combinatorial interpretation (by means of a regular language) of certain positive integer sequences that are defined by c-finite recurrences. in this paper we present a maple implementation of this inverse methodology and describe various applications. we give a short introduction to the underlying theory, i.e., the question of deciding n-rationality. in addition, some aspects and problems concerning the implementation are discussed; some examples from combinatorics illustrate its applicability.
a characterization of fine words over a finite alphabet. to any infinite word t over a finite alphabet a we can associate two infinite words min(t) and max(t) such that any prefix of min(t) (resp. max(t)) is the lexicographically smallest (resp. greatest) amongst the factors of t of the same length. we say that an infinite word t over a is fine if there exists an infinite word s such that, for any lexicographic order, min(t)=as where a=min(a). in this paper, we characterize fine words; specifically, we prove that an infinite word t is fine if and only if t is either a strict episturmian word or a strict ''skew episturmian word''. this characterization generalizes a recent result of g. pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) sturmian.
cobham-semenov theorem and n-subshifts. we give a new proof of cobham's first theorem using ideas from symbolic dynamics and of cobham-semenov theorem (in the primitive case) using ideas from tiling dynamics.
words avoiding repetitions in arithmetic progressions. carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. we show a connection between carpi's construction and the paperfolding words. we extend carpi's result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. we also construct infinite words avoiding overlaps and infinite words avoiding all sufficiently large squares in arithmetic progressions of odd difference. we use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels.
self-dual tilings with respect to star-duality. the concept of star-duality is described for self-similar cut-and-project tilings in arbitrary dimensions. this generalises thurston's concept of a galois-dual tiling. the dual tilings of the penrose tilings as well as the ammann-beenker tilings are calculated. conditions for a tiling to be self-dual are obtained.
cancellation and periodicity properties of iterated morphisms. in this note we prove two cancellation properties of iterated morphisms and use these properties to give a simple method for deciding whether or not a given infinite d0l word is ultimately periodic.
semi-online scheduling on two uniform processors. in this paper we consider the problem of semi-online scheduling on two uniform processors, in the case where the total sum of the tasks is known in advance. tasks arrive one at a time and have to be assigned to one of the two processors before the next one arrives. the assignment cannot be changed later. the objective is the minimization of the makespan. assume that the speed of the fast processor is s, while the speed of the slow one is normalized to 1. as a function of s, we derive general lower bounds on the competitive ratio achievable with respect to offline optimum, and design on-line algorithms with guaranteed upper bound on their competitive ratio. the algorithms presented for s>=3 are optimal, as well as for s=1 and for 1+174@?s@?1+32.
sound and complete computational interpretation of symbolic hashes in the standard model. this paper provides one more step towards bridging the gap between the formal and computational approaches to the verification of cryptographic protocols. we extend the well-known abadi-rogaway logic with probabilistic hashes and give a precise semantic interpretation to it using canetti's oracle hashes. these are probabilistic polynomial-time hashes that hide all partial information. we show that, under appropriate conditions on the encryption scheme, this interpretation is computationally sound and complete. this can be used to port security results from the formal world to the computational world when considering passive adversaries. we also give an explicit example showing that oracle hashing is not strong enough to obtain such a result for active adversaries.
unconditional competitive auctions with copy and budget constraints. this paper investigates a new auction model in which bidders have both copy and budget constraints. this new model has extensive and interesting applications in auctions of online ad-words, software licenses, etc. we consider the following problem: supposing all participators are rational, how does one allocate the objects and at what price so as to maximize the auctioneer's revenue. we introduce new kinds of mechanisms called auctioneer-advantaged mechanisms and present the notion of unconditional competitive auctions. a notably interesting property of auctioneer-advantaged mechanisms is that each bidder's self-interested strategy brings better utility not only to himself but also to the auctioneer. then we present auctioneer-advantaged mechanisms for multi-unit auctions with copy and budget constraints. we prove that these auctions are unconditional competitive under the situation of both limited and unlimited supply.
mixed nash equilibria in selfish routing problems with dynamic constraints. we study the problem of routing traffic through a congested network consisting of m parallel links, each having a certain speed. moreover, we are given n selfish (non-cooperative) agents, each of them willing to route her own piece of traffic on exactly one link. agents are selfish in that they only pick a link which minimize the delay of their own piece of traffic. in this context much effort has been lavished in the framework of mixed nash equilibria where the agent's routing choices are regulated by probability distributions, one for each agent, which let the system thus enter a steady state from which no agent is willing to unilaterally deviate. in this work we consider situations in which some agents have constraints on the routing choice: in a sense they are forbidden to route their traffic on some links. we show that at most one nash equilibrium may exist and, in some cases with equal speed links and where each agent is forbidden to route on at most one link, we give necessary and sufficient conditions on its existence; these conditions correlate the traffic load of the agents. we consider also a dynamic behaviour of the network when the constraints may vary, in particular when a constraint is removed: we establish under which conditions the network is still in equilibrium. these conditions are all effective in the sense that, given a set of yes/no routing constraints on each link for each agent, we provide the probability distributions corresponding to the unique nash equilibrium associated to the constraints (if it exists). moreover these conditions and the possible nash equilibrium are computed in time o(mn).
fibrations and universal view updatability. maintainability and modifiability of information system software can be enhanced by the provision of comprehensive support for views, since view support allows application programs to continue to operate unchanged when the underlying information system is modified. supporting views depend upon a solution to the view update problem. this paper presents a new treatment of view updates for formally specified semantic data models based on the category theoretic sketch data model. the sketch data model has been the basis of a number of successful major information system consultancies. we define view updates by a universal property in models of the formal specification, and explain why this indeed gives a complete and correct treatment of view updatability, including a solution to the view update problem. however, a definition of updatability which is based on models causes some inconvenience in applications, so we prove that in a variety of circumstances updatability is guaranteed independently of the current model. this is done first with a very general criterion, and then for some specific cases relevant to applications. we include some details about the sketch data model, noting that it involves extensions of algebraic data specification techniques.
gemcell: a generic platform for modeling multi-cellular biological systems. the mass and complexity of biological information requires computer-aided simulation and analysis to help scientists achieve understanding and guide experimentation. although living organisms are composed of cells, actual genomic and proteomic data have not yet led to a satisfactory model of working cell in silico. we have set out to devise a user-friendly generic platform, gemcell, for generic executable modeling of cells, based on whole, functioning cells. starting with the cell simplifies life, because all cells expresses essentially five generic types of behavior: replication, death, movement (including change of shape and adherence), export (secretion, signaling, etc.) and import (receiving signals, metabolites, phagocytosis, etc.). the details of these behaviors are specified in gemcell for particular kinds of cells as part of a database of biological specifics (the dbs), which specifies the cell properties and functions that depend on the cell's history, state, environment, etc. the dbs is designed in an intuitive fashion, so users are able to easily insert their data of interest. the generic part of gemcell, built using statecharts, is a fully dynamic model of a cell, its interactions with the environment and its resulting behavior, individually and collectively. model specificity emerges from the dbs, so that model execution is carried out by the statecharts executing with the aid of specific data extracted from the dbs dynamically. our long term goal is for gemcell to serve as a broadly applicable platform for biological modeling and analysis, supporting user-friendly in silico experimentation, animation, discovery of emergent properties, and hypothesis testing, for a wide variety of biological systems.
a multiset-based model of synchronizing agents: computability and robustness. we introduce a modelling framework and computational paradigm called colonies of synchronizing agents (csas) inspired by the intracellular and intercellular mechanisms in biological tissues. the model is based on a multiset of agents in a common environment. each agent has a local state stored in the form of a multiset of atomic objects, which is updated by global multiset rewriting rules either independently or synchronously with another agent. we first define the model then study its computational power, considering trade-offs between internal rewriting (intracellular mechanisms) and synchronization between agents (intercellular mechanisms). we also investigate dynamic properties of csas, including behavioural robustness (ability to generate a core behaviour despite agent loss or rule failure) and safety of synchronization (ability of an agent to synchronize with some other agent whenever needed).
temporal constraints in the logical analysis of regulatory networks. starting from the logical description of gene regulatory networks developed by r. thomas, we introduce an enhanced modeling approach based on timed automata. we obtain a refined qualitative description of the dynamical behavior by exploiting not only information on ratios of kinetic parameters related to synthesis and decay, but also constraints on the time delays associated with the operations of the system. we develop a formal framework for handling such temporal constraints using timed automata, discuss the relationship with the original thomas formalism, and demonstrate the potential of our approach by analyzing an illustrative gene regulatory network of bacteriophage @l.
on process rate semantics. we provide translations between process algebra and systems of chemical reactions. we show that the translations preserve discrete-state (stochastic) and continuous-state (concentration) semantics, and in particular that the continuous-state semantics of processes corresponds to the differential equations of chemistry based on the law of mass action. the novel semantics of processes so obtained equates processes that have the same state occupation dynamics, but which may have different interaction interfaces.
probabilistic model checking of complex biological pathways. probabilistic model checking is a formal verification technique that has been successfully applied to the analysis of systems from a broad range of domains, including security and communication protocols, distributed algorithms and power management. in this paper we illustrate its applicability to a complex biological system: the fgf (fibroblast growth factor) signalling pathway. we give a detailed description of how this case study can be modelled in the probabilistic model checker prism, discussing some of the issues that arise in doing so, and show how we can thus examine a rich selection of quantitative properties of this model. we present experimental results for the case study under several different scenarios and provide a detailed analysis, illustrating how this approach can be used to yield a better understanding of the dynamics of the pathway. finally, we outline a number of exact and approximate techniques to enable the verification of larger and more complex pathways and apply several of them to the fgf case study.
making the use of maximal ideals constructive. the purpose of this paper is to decipher constructively a lemma of suslin which played a central role in his second solution of serre's problem on projective modules over polynomial rings. this lemma says that for a commutative ring a if =a[x] where v"1 is monic and n>=3, then there exist @c"1,...,@c"@?@?e"n"-"1(a[x]) such that, denoting by w"i the first coordinate of @c"it(v"2,...,v"n), we have =a. by the constructive proof we give, suslin's proof of serre's problem becomes fully constructive. moreover, the new method with which we treat this academic example may be a model for miming constructively abstract proofs in which one works modulo a generic maximal ideal in order to prove that an ideal contains 1.
reeb graphs for shape analysis and applications. reeb graphs are compact shape descriptors which convey topological information related to the level sets of a function defined on the shape. their definition dates back to 1946, and finds its root in morse theory. reeb graphs as shape descriptors have been proposed to solve different problems arising in computer graphics, and nowadays they play a fundamental role in the field of computational topology for shape analysis. this paper provides an overview of the mathematical properties of reeb graphs and reconstructs its history in the computer graphics context, with an eye towards directions of future research.
uniform approximation of near-singular surfaces. we consider the problem of a piecewise-polynomial (spline) approximation of algebraic surfaces of a given degree. conventional accuracy estimates in such approximations include bounds on the high-order derivatives, or on the surface curvature. as an algebraic surface degenerates to a singular one, the curvature blows up. consequently, the same happens with the complexity of the approximation: to keep the required accuracy, we need more and more patches at near-singular (high curvature) areas. this indeed happens in any conventional ''triangulation'' algorithm. nevertheless, using ''c^k-reparametrization'' theorem (which originally appeared in dynamical applications) we show in this paper that for such near-singular families of surfaces there exist approximations of any fixed accuracy and of a uniformly bounded complexity. to give an example of a situation, where our construction becomes explicit, we consider one of the possible models for singular (and near-singular) surfaces. in this model, developed in [y. yomdin, generic singularities of surfaces, in: d. cheniot, n. dutertre, c. murolo, d. trotman, a. pichon, (eds), singularity theory, dedicated to j.-p. brasselet on his 60-th birthday (proceedings of the 2005 marseille singularity school and conference, marseille, france), 2005, pp. 24.1-25.2; d. haviv, ma thesis, weizmann institute, 2006] a surface appears as a part of the level surface f=c, with f=f"1f"2...f"m having a product form. the advantage of this approach is that ''edges'' and ''corners'' appear in a generic and stable way, as well as ''near-edges'' and ''near-corners''. using special model-based representation developed in [y. yomdin, generic singularities of surfaces, in: d. cheniot, n. dutertre, c. murolo, d. trotman, a. pichon, (eds), singularity theory, dedicated to j.-p. brasselet on his 60-th birthday (proceedings of the 2005 marseille singularity school and conference, marseille, france), 2005, pp. 24.1-25.2; d. haviv, ma thesis, weizmann institute, 2006], we produce explicit formulae for the uniform c^2-reparametrization of some of these near-singularities.