waashk/dblp huggingface dataset:
general suffix automaton construction algorithm and space bounds. suffix automata and factor automata are efficient data structures for representing the full index of a set of strings. they are minimal deterministic automata representing the set of all suffixes or substrings of a set of strings. this paper presents a novel analysis of the size of the suffix automaton or factor automaton of a set of strings. it shows that the suffix automaton or factor automaton of a set of strings u has at most 2q-2 states, where q is the number of nodes of a prefix-tree representing the strings in u. this bound significantly improves over 2@?u@?-1, the bound given by blumer et al. [a. blumer, j. blumer, d. haussler, r.m. mcconnell, a. ehrenfeucht, complete inverted files for efficient text retrieval and analysis, journal of the acm 34 (1987) 578-589], where @?u@? is the sum of the lengths of all strings in u. more generally, we give novel and general bounds for the size of the suffix or factor automaton of an automaton as a function of the size of the original automaton and the maximal length of a suffix shared by the strings it accepts. we also describe in detail a linear-time algorithm for constructing the suffix automaton s or factor automaton f of u in time o(|s|). our algorithm applies in fact to any input suffix-unique automaton and strictly generalizes the standard on-line construction of a suffix automaton for a single input string. our algorithm can also be used straightforwardly to generate the suffix oracle or factor oracle of a set of strings, which has been shown to have various useful properties in string-matching. our analysis suggests that the use of factor automata of automata can be practical for large-scale applications, a fact that is further supported by the results of our experiments applying factor automata to a music identification task with more than 15,000 songs.
simple equations on binary factorial languages. we consider equations on the monoid of factorial languages on the binary alphabet. we use the notion of a canonical decomposition of a factorial language and previous results by avgustinovich and the author to solve several simple equations on binary factorial languages including x^n=y^n, the commutation equation xy=yx and the conjugacy equation xz=zy. at the end of the paper, we discuss the difficulties hindering the reduction of equations on factorial languages to equations on words and the extension of the alphabet considered.
on post correspondence problem for letter monotonic languages. we prove that for given morphisms g,h:{a"1,a"2,...,a"n}->b^*, it is decidable whether or not there exists a word w in the regular language a"1^*a"2^*...a"n^* such that g(w)=h(w). in other words, we prove that the post correspondence problem is decidable if the solutions are restricted to be from this special language. this yields a nice example of an undecidable problem in integral matrices which cannot be directly proved undecidable using the traditional reduction from the post correspondence problem.
on a generalization of christoffel words: epichristoffel words. sturmian sequences are well-known as the ones having minimal complexity over a 2-letter alphabet. they are also the balanced sequences over a 2-letter alphabet and the sequences describing discrete lines. they are famous and have been extensively studied since the 18th century. one of the extensions of these sequences over a k-letter alphabet, with k>=3, is the episturmian sequences, which generalizes a construction of sturmian sequences using the palindromic closure operation. there exists a finite version of the sturmian sequences called the christoffel words. they have been known since the works of christoffel and have interested many mathematicians. in this paper, we introduce a generalization of christoffel words for an alphabet with 3 letters or more, using the episturmian morphisms. we call them the epichristoffel words. we define this new class of finite words and show how some of the properties of the christoffel words can be generalized naturally or not for this class.
sand automata as cellular automata. in this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. this relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. we show that the existing topological results for sand automata, including the hedlund-like representation theorem, still hold. in this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. furthermore, we deal with simple sand automata. we show that the classical definition of nilpotency is not meaningful for sand automata. then, we introduce the suitable new notion of flattening sand automata. finally, we prove that this simple dynamical behavior is undecidable.
an o(n) algorithm for l(2, 1)-labeling of trees. an l(2,1)-labeling of a graph g is an assignment f from the vertex set v(g) to the set of nonnegative integers such that |f(x)-f(y)|>=2 if x and y are adjacent and |f(x)-f(y)|>=1 if x and y are at distance 2 for all x and y in v(g). a k-l(2,1)-labeling is an l(2,1)-labeling f:v(g)->{0,...,k}, and the l(2,1)-labeling problem asks the minimum k, which we denote by @l(g), among all possible l(2,1)-labelings. it is known that this problem is np-hard even for graphs of treewidth 2. tree is one of a few classes for which the problem is polynomially solvable, but still only an o(@d^4^.^5n) time algorithm for a tree t has been known so far, where @d is the maximum degree of t and n=|v(t)|. in this paper, we first show that an existent necessary condition for @l(t)=@d+1 is also sufficient for a tree t with @d=@w(n), which leads to a linear time algorithm for computing @l(t) under this condition. we then show that @l(t) can be computed in o(@d^1^.^5n) time for any tree t. combining these, we finally obtain an o(n^1^.^7^5) time algorithm, which substantially improves upon previously known results.
hierarchy and equivalence of multi-letter quantum finite automata. multi-letter quantum finite automata (qfas) are a new one-way qfa model proposed recently by belovs, rosmanis, and smotrovs [a. belovs, a. rosmanis, j. smotrovs, multi-letter reversible and quantum finite automata, in: proceedings of the 13th international conference on developments in language theory, dlt'2007, harrachov, czech republic, in: lecture notes in computer science, vol. 4588, springer, berlin, 2007, pp. 60-71], and they showed that multi-letter qfas can accept with no error some regular languages ((a+b)^*b) that are unacceptable by the one-way qfas. in this paper, we continue to study multi-letter qfas. we mainly focus on two issues: (1) we show that (k+1)-letter qfas are computationally more powerful than k-letter qfas, that is, (k+1)-letter qfas can accept some regular languages that are unacceptable by any k-letter qfa. a comparison with the one-way qfas is made by some examples; (2) we prove that a k"1-letter qfa a"1 and another k"2-letter qfa a"2 are equivalent, if and only if, they are (n"1+n"2)^4+k-1-equivalent, and the time complexity of determining the equivalence of two multi-letter qfas using this method is o(n^1^2+k^2n^4+kn^8), where n"1 and n"2 are the numbers of states of a"1 and a"2, respectively, and k=max(k"1,k"2). some other issues are addressed for further consideration.
complexity of counting the optimal solutions. following the approach of hemaspaandra and vollmer, we can define counting complexity classes #@?c for any complexity class c of decision problems. in particular, the classes #@?@p"kp with k>=1 corresponding to all levels of the polynomial hierarchy, have thus been studied. however, for a large variety of counting problems arising from optimization problems, a precise complexity classification turns out to be impossible with these classes. in order to remedy this unsatisfactory situation, we introduce a hierarchy of new counting complexity classes #@?opt"kp and #@?opt"kp[logn] with k>=1. we prove several important properties of these new classes, like closure properties and the relationship with the #@?@p"kp-classes. moreover, we establish the completeness of several natural counting complexity problems for these new classes.
nondeterministic state complexity of nested word automata. we study the nondeterministic state complexity of boolean operations on regular languages of nested words. for union and intersection we obtain matching upper and lower bounds. for complementation of a nondeterministic nested word automaton with n states we establish a lower bound @w(n!) that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (nfa). we develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for nfas.
periodicity, repetitions, and orbits of an automatic sequence. we revisit a technique of s. lehr on automata and use it to prove old and new results in a simple way. we give a very simple proof of the 1986 theorem of honkala that it is decidable whether a given k-automatic sequence is ultimately periodic. we prove that it is decidable whether a given k-automatic sequence is overlap-free (or squarefree, or cubefree, etc.). we prove that the lexicographically least sequence in the orbit closure of a k-automatic sequence is k-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for sturmian words with slope @a, have automatic continued fraction expansions if @a does.
on the relative dominance of paging algorithms. in this paper, we give a finer separation of several known paging algorithms using a new technique called relative interval analysis. this technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size, rather than in the worst case alone. using this technique, we characterize the relative performance of lru and lru-2, as well as lru and fwf, among others. we also show that look-ahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.
two collapsing hierarchies of subregularly tree controlled languages. tree controlled grammars are context-free grammars where the associated language only contains those terminal words which have a derivation where the word of any level of the corresponding derivation tree belongs to a given regular language. in this paper, we consider first as control sets such regular languages which can be represented by finite unions of monoids. we show that the corresponding hierarchy of tree controlled languages collapses already at the second level. second, we restrict the number of states allowed in the accepting automaton of the regular control language. we prove that the associated hierarchy has at most five levels.
finite state automata representing two-dimensional subshifts. a new type of two-dimensional automaton has been defined to recognize a class of two-dimensional shifts of finite type having the property that every admissible block found within the related local picture language can be extended to a point of the subshift. here it is shown that this automaton accurately represents the image of the represented two-dimensional shift of finite type under a block code. it is then shown that these automata can be used to check for a certain type of two-dimensional transitivity in the factor language of the corresponding shift space and how this relates to periodicity in the two-dimensional case. the paper closes with a notion of ''follower sets'' that are used to reduce the size of the automata representing two-dimensional sofic shifts.
weighted automata and weighted logics with discounting. we introduce a weighted logic with discounting and we establish the buchi-elgot theorem for weighted automata over finite words and arbitrary commutative semirings. then we investigate buchi and muller automata with discounting over the max-plus and the min-plus semiring. we show their expressive equivalence with weighted mso-sentences with discounting. in this case our logic has a purely syntactic definition. for the finite case, we obtain a purely syntactically defined weighted logic if the underlying semiring is additively locally finite.
optimally competitive list batching. batching has been studied extensively in the offline case, but applications such as manufacturing or tcp acknowledgment often require online solutions. we consider online batching problems, where the order of jobs to be batched is fixed and where we seek to minimize the sum of the completion times of the jobs. we present optimally competitive online algorithms for both s-batch and p-batch problems, and we also derive results for certain naturally occurring special cases, such as the case of unit processing times.
characteristic morphisms of generalized episturmian words. in a recent paper with l.q. zamboni, the authors introduced the class of @q-episturmian words. an infinite word over a is standard @q-episturmian, where @q is an involutory antimorphism of a^*, if its set of factors is closed under @q and its left special factors are prefixes. when @q is the reversal operator, one obtains the usual standard episturmian words. in this paper, we introduce and study @q-characteristic morphisms, that is, morphisms which map standard episturmian words into standard @q-episturmian words. they are a natural extension of standard episturmian morphisms. the main result of the paper is a characterization of these morphisms when they are injective. in order to prove this result, we also introduce and study a class of biprefix codes which are overlap-free, i.e., any two code words do not overlap properly, and normal, i.e., no proper suffix (prefix) of any code-word is left (right) special in the code. a further result is that any standard @q-episturmian word is a morphic image, by an injective @q-characteristic morphism, of a standard episturmian word.
probabilistic analysis of upper bounds for 2-connected distance k-dominating sets in graphs. a small virtual backbone which is modeled as the minimum connected dominating set (cds) problem has been proposed to alleviate the broadcasting storm for efficiency in wireless ad hoc networks. in this paper, we consider a general fault tolerant cds problem, called an h-connected distance k-dominating set (hckds) to balance high efficiency and fault tolerance, and study the upper bound for hckds with a probabilistic method for small h and improve the current best results.
new permutation coding and equidistribution of set-valued statistics. a new coding for permutations is explicitly constructed and its association with the classical lehmer coding provides a bijection of the symmetric group onto itself serving to show that six bivariable set-valued statistics are equidistributed on that group. this extends a recent result due to cori valid for integer-valued statistics.
language operations with regular expressions of polynomial size. this work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. we prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. the circular shift operation can cause only a cubic increase in size and at least a quadratic bloat can be necessary in the worst case.
optimal strategies for maintaining a chain of relays between an explorer and a base camp. we envision a scenario with robots moving on a terrain represented by a plane. a mobile robot, called explorer is connected by a communication chain to a stationary base camp. the chain is expected to pass communication messages between the explorer and the base camp. it is composed of simple, mobile robots, called relays. we are investigating strategies for organizing and maintaining the chain, so that the number of relays employed is minimized and nevertheless the distance between neighbored relays in the chain remains bounded. we are looking for local and distributed strategies employed by restricted relays that have to base their decision (''where should i go?'') solely on the relative positions of its neighbors in the chain. we present the manhattan-hopper and the hopper strategy which improve the performance of all known solutions to this problem significantly. they are the first such strategies that are optimal in this setting, i.e., that allow the explorer to move with constant speed, independent of the length of the chain, and keep this length minimum up to a constant factor.
regulated nondeterminism in pushdown automata. a generalization of pushdown automata towards regulated nondeterminism is studied. the nondeterminism is governed in such a way that the decision, whether or not a nondeterministic rule is applied, depends on the whole content of the stack. more precisely, the content of the stack is considered as a word over the stack alphabet, and the pushdown automaton is allowed to act nondeterministically, if this word belongs to some given set r of control words. otherwise its behavior is deterministic. it turns out that non-context-free languages can be accepted if r is a context-free and non-regular language. on the other hand, if the control sets r are regular languages, then the resulting devices are not more powerful than nondeterministic pushdown automata. this raises the natural question of the relations between the structure and complexity of regular sets r on one hand and the computational capacity of the corresponding r-pda on the other hand. the main result of the paper shows that an infinite proper hierarchy of regular control sets leads to an infinite proper hierarchy of the corresponding language classes. additionally, closure properties and decision problems of these language classes are investigated.
adaptive routing with stale information. we investigate the behaviour of load-adaptive rerouting policies in the wardrop model where decisions must be made on the basis of stale information. in this model, each one of an infinite number of agents controls an infinitesimal amount of flow, thus contributing to a network flow which induces latency. in our dynamic extension of this model, agents are activated in a concurrent and asynchronous fashion and may reroute their flow with the aim of reducing their sustained latency. it is a well-known problem that in settings where latency information is not always up-to-date, such behaviour may lead to oscillation effects which seriously harm network performance. two quantities determine the difficulty of avoiding oscillation: the steepness of the latency functions and the maximum possible age of the information t. in this work we ask for conditions that the rerouting policies must adhere to in order to converge to an equilibrium despite the information being stale. we consider simple policies which sample another path in a first step and then migrate from the current path to the new one with a probability that is a function of the anticipated latency gain. in fact we can show that our class of policies guarantees convergence if the latter migration probability function satisfies a certain smoothness condition that resembles lipschitz continuity. it turns out that for smooth adaptation policies where the migration probability is chosen small enough relative to the inverse of the steepness of the latency functions and t, the population actually converges to an equilibrium. in addition, we analyse the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.
causal message sequence charts. scenario languages based on message sequence charts (mscs) have been widely studied in the last decade. the high expressive power of mscs renders many basic problems concerning these languages undecidable. however, several of these problems are decidable for languages that possess a behavioral property called ''existentially bounded''. unfortunately, collections of scenarios outside this class are frequently exhibited by systems such as sliding window protocols. we propose here an extension of mscs called causal message sequence charts and a natural mechanism for defining languages of causal mscs called causal hmscs (cahmscs). these languages preserve decidable properties without requiring existential bounds. further, they can model collections of scenarios generated by sliding window protocols. we establish here the basic theory of cahmscs as well as the expressive power and complexity of decision procedures for various subclasses of cahmscs. we also illustrate the modeling power of our formalism with the help of a realistic example based on the tcp sliding window feature.
on the uniqueness of shuffle on words and finite languages. we investigate a special variant of the shuffle decomposition problem for regular languages; namely, when the given regular language is the shuffle of finite languages. the shuffle decomposition into finite languages is, in general, not unique. that is, there are l"1,l"2,l"3,l"4 with but {l"1,l"2}
stochastic biological modelling in the presence of multiple compartments. the application of concurrent calculi to the formalisation of biological systems constitutes a promising approach to the analysis of biological phenomena in silico. the peculiar nature of such systems inspired the introduction of specific features in biologically-oriented calculi, such as compartments to model more faithfully their highly organised structure. in this paper we present s@p@, a conservative extension of the stochastic @p-calculus which allows an intuitive and concise formalisation of multi-compartment systems with dynamic structure, despite retaining the simplicity of the original @p-calculus. the possibility to encode into s@p@ several bio-inspired, compartmentalised languages demonstrates its expressive power and flexibility. the calculus is accompanied by an extended version of gillespie's stochastic simulation algorithm, able to handle multiple compartments with varying volumes. an enhanced formalisation of the algorithm is also presented, in order to provide efficient simulation in the presence of a high number of compartments and reactions.
a new characteristic property of rich words. originally introduced and studied by the third and fourth authors together with j. justin and s. widmer (2008), rich words constitute a new class of finite and infinite words characterized by containing the maximal number of distinct palindromes. several characterizations of rich words have already been established. a particularly nice characteristic property is that all 'complete returns' to palindromes are palindromes. in this note, we prove that rich words are also characterized by the property that each factor is uniquely determined by its longest palindromic prefix and its longest palindromic suffix.
compressed string-matching in standard sturmian words. we present a simple algorithm which for an explicitly given input string pat (a pattern) and a standard sturmian word x described by the recurrences of size n computes, in time o(|pat|+n), the set of all occurrences of pat in x as a single arithmetic progression (modulo the length of x). the algorithm can be extended to the case when some letters of the pattern are replaced by a don't care symbol. in this case the set of all occurrences does not need to be a single arithmetic progression and our algorithm produces linearly many (with respect to the size of pat) arithmetic progressions. it is an example of fast computations for the input given in a compressed form. in our special case the length of the standard sturmian word x is usually exponential with respect to the size of the input.