waashk/dblp huggingface dataset:
from nerode's congruence to suffix automata with mismatches. in this paper we focus on the minimal deterministic finite automaton s"k that recognizes the set of suffixes of a word w up to k errors. as first result we give a characterization of the nerode's right-invariant congruence that is associated with s"k. this result generalizes the classical characterization described in [a. blumer, j. blumer, d. haussler, a. ehrenfeucht, m. chen, j. seiferas, the smallest automaton recognizing the subwords of a text, theoretical computer science, 40, 1985, 31-55]. as second result we present an algorithm that makes use of s"k to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the repetition index of w. moreover, we give some experimental results on some well-known words, like prefixes of fibonacci and thue-morse words. finally, we state a conjecture and an open problem on the size and the construction of the suffix automaton with mismatches.
online parallel machines scheduling with two hierarchies. this paper investigates an online hierarchical scheduling problem on m parallel identical machines. each job, as well as each machine, has a hierarchy associated with it. a job can be scheduled on a machine only when its hierarchy is no higher than that of the machine. the objective is to minimize the makespan. in addition, we assume that there are only two hierarchies, and k machines have a higher hierarchy which can schedule all jobs. we present an online algorithm with a competitive ratio of 1+m^2-mm^2-km+k^2
a computational model for tiling recognizable two-dimensional languages. tiling systems are a well accepted model to define recognizable two-dimensional languages but they are not an effective device for recognition unless a scanning strategy for the pictures is fixed. we define a tiling automaton as a tiling system equipped with a scanning strategy and a suitable data structure. the class of languages accepted by tiling automata coincides with the rec family. in this framework it is possible to define determinism, non-determinism and unambiguity. then (deterministic) tiling automata are compared with the other known (deterministic) automata models for two-dimensional languages.
atomic routing games on maximum congestion. we study atomic routing games on networks in which players choose a path with the objective of minimizing the maximum congestion along the edges of their path. the social cost is the global maximum congestion over all edges in the network. we show that the price of stability is 1. the price of anarchy, poa, is determined by topological properties of the network. in particular, poa=o(@?+logn), where @? is the length of the longest path in the player strategy sets, and n is the size of the network. further, @k-1@?poa@?c(@k^2+log^2n), where @k is the length of the longest cycle in the network, and c is a constant.
a control flow analysis for beta-binders with and without static compartments. we introduce a control flow analysis, that statically approximates the dynamic behaviour of processes, expressed in the beta-binders calculus and in an extended version of the calculus modelling static compartments. our analysis of a system is able to describe the essential behaviour of each box, tracking all the possible bindings of variables, all the possible intra- and inter-boxes communications, and, finally, all the possible movements across compartments. the analysis offers a basis for establishing static checks of biological dynamic properties. we apply our analysis to an abstract specification of the interaction between a virus and cells of the immune system and to a model of the camp-signaling pathway in olfactory sensory neurons.
the "equal last letter" predicate for words on infinite alphabets and classes of multitape automata. we consider the first-order theory of the free infinitely generated monoid with the usual predicates ''prefix'' and ''equal length'' along with the predicate ''equal last letter''. the associated definable relations are related to the algebras of relations recognized by different types of multitape automata which are natural extensions of the famous rabin-scott multitape automata and the synchronous automata. we investigate these classes of automata and solve decision issues concerning them.
state-complexity hierarchies of uniform languages of alphabet-size length. we study the state complexity of certain simple languages. if a is an alphabet of k letters, then a k-language is a nonempty set of words of length k, that is, a uniform language of length k. we show that the minimal state complexity of a k-language is k+2, and the maximal, (k^k^-^1-1)/(k-1)+2^k+1. we prove constructively that, for every i between the minimal and maximal bounds, there is a language of state complexity i. we introduce a class of automata accepting sets of words that are permutations of a; these languages define a complete hierarchy of complexities between k^2-k+3 and 2^k+1. the languages of another class of automata, based on k-ary trees, define a complete hierarchy of complexities between 2^k+1 and (k^k^-^1-1)/(k-1)+2^k+1. this provides new examples of uniform languages of maximal complexity.
a process model of rho gtp-binding proteins. rho gtp-binding proteins play a key role as molecular switches in many cellular activities. in response to extracellular stimuli and with the help of regulators (gef, gap, effector, gdi), these proteins serve as switches that interact with their environment in a complex manner. based on the structure of a published ordinary differential equations (ode) model, we first present a generic process model for the rho gtp-binding proteins, and compare it with the ode model. we then extend the basic model to include the behaviour of the gdi regulators and explore the parameter space for the extended model with respect to biological data from the literature. we discuss the challenges this extension brings and the directions of further research. in particular, we present techniques for modular representation and refinement of process models, where, for example, different rho proteins with different rates for regulator interactions can be given as instances of the same parametric model.
synchronizing automata preserving a chain of partial orders. we present a new class of automata which strictly contains the class of aperiodic automata and shares with the latter certain synchronization properties. in particular, every strongly connected automaton in this new class is synchronizing and has a synchronizing word of length @?n(n+1)6@? where n is the number of states of the automaton.
on the runtime and robustness of randomized broadcasting. in this paper, we study the following randomized broadcasting protocol. at some time t an information r is placed at one of the nodes of a graph. in the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of r to it. we begin by developing tight lower and upper bounds on the runtime of the algorithm described above. first, it is shown that on @d-regular graphs this algorithm requires at least log"2"-"1"@dn+log"("@d"@d"-"1")"^"@dn-o(logn)~1.69log"2n rounds to inform all n nodes. together with a result of pittel [b. pittel, on spreading a rumor, siam journal on applied mathematics, 47 (1) (1987) 213-223] this bound implies that the algorithm has the best performance on complete graphs among all regular graphs. for general graphs, we prove a slightly weaker lower bound of log"2"-"1"@dn+log"4n-o(logn)~1.5log"2n, where @d denotes the maximum degree of g. we also prove two general upper bounds, (1+o(1))nlnn and o(n@d@d), respectively, where @d denotes the minimum degree. the second part of this paper is devoted to the analysis of fault-tolerance. we show that if the informed nodes are allowed to fail in some step with probability 1-p, then the broadcasting time increases by at most a factor 6/p. as a by-product, we determine the performance of agent based broadcasting in certain graphs and obtain bounds for the runtime of randomized broadcasting on cartesian products of graphs.
reactive systems, (semi-)saturated semantics and coalgebras on presheaves. the semantics of process calculi has traditionally been specified by labelled transition systems (ltss), but, with the development of name calculi, it turned out that reaction rules (i.e., unlabelled transition rules) are often more natural. this leads to the question of how behavioral equivalences (bisimilarity, trace equivalence, etc.) defined for lts can be transferred to unlabelled transition systems. recently, in order to answer this question, several proposals have been made with the aim of automatically deriving an lts from reaction rules in such a way that the resulting equivalences are congruences. furthermore, these equivalences should agree with the standard semantics, whenever one exists. in this paper, we propose saturated semantics, based on a weaker notion of observation and orthogonal to all the previous proposals, and we demonstrate the appropriateness of our semantics by means of two examples: logic programming and open petri nets. we also show that saturated semantics can be efficiently characterized through the so called semi-saturated games. finally, we provide coalgebraic models relying on presheaves.
continuant polynomials and worst-case behavior of hopcroft's minimization algorithm. this paper is concerned with the analysis of the worst case behavior of hopcroft's algorithm for minimizing deterministic finite state automata. we extend a result of castiglione, restivo and sciortino. they show that hopcroft's algorithm has a worst case behavior for the automata recognizing fibonacci words. in a previous paper, we have proved that this holds for all standard sturmian words having an ultimately periodic directive sequence (the directive sequence for fibonacci words is (1,1,...)). we prove here that the same conclusion holds for all standard sturmian words having a directive sequence with bounded elements. more precisely, we obtain in fact a characterization of those directive sequences for which hopcroft's algorithm has worst case running time. these are the directive sequences (d"1,d"2,d"3,...) for which the sequence of geometric means (d"1d"2...d"n)^1^/^n is bounded. as a consequence, we easily show that there exist directive sequences for which the worst case for the running time is not attained.
the degree of word-expansion of lexicalized rrww-automata - a new measure for the degree of nondeterminism of (context-free) languages. restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. we study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. this measure is based on the number of occurrences of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. this type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.
accelerating boyer-moore searches on binary texts. the boyer and moore (bm) pattern matching algorithm is considered as one of the best, but its performance is reduced on binary data. yet, searching in binary texts has important applications, such as compressed matching. the paper shows how, by means of some pre-computed tables, one may implement the bm algorithm also for the binary case without referring to bits, and processing only entire blocks such as bytes or words, thereby significantly reducing the number of comparisons. empirical comparisons show that the new variant performs better than regular binary bm and even than bdm.
determination of finite automata accepting subregular languages. we investigate the descriptional complexity of the nondeterministic finite automaton (nfa) to the deterministic finite automaton (dfa) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages. most of the bounds for the conversion problem are shown to be tight in the exact number of states, that is, the number is sufficient and necessary in the worst case. otherwise tight bounds in order of magnitude are shown.
prime algebraicity. a prime algebraic lattice can be characterised as isomorphic to the downwards-closed subsets, ordered by inclusion, of its complete primes. it is easily seen that the downwards-closed subsets of a partial order form a completely distributive algebraic lattice when ordered by inclusion. the converse also holds; any completely distributive algebraic lattice is isomorphic to such a set of downwards-closed subsets of a partial order. the partial order can be recovered from the lattice as the order of the lattice restricted to its complete primes. consequently prime algebraic lattices are precisely the completely distributive algebraic lattices. the result extends to scott domains. several consequences are explored briefly: the representation of berry's di-domains by event structures; a simplified form of information systems for completely distributive scott domains; and a simple domain theory for concurrency.
finding compact structural motifs. protein structural motif detection has important applications in structural genomics. compared with sequence motifs, structural motifs are more sensitive in revealing the evolutionary relationships among proteins. a variety of algorithms have been proposed to attack this problem. however, they are either heuristic without theoretical performance guarantee, or inefficient due to employing exhaustive search strategies. this paper studies a reasonably restricted version of this problem: the compact structural motif problem. we prove that this restricted version is still np-hard, and we present a polynomial-time approximation scheme to solve it. this is the first approximation algorithm with a guaranteed ratio for the protein structural motif problem.
accelerating certain outputs of merging and sorting networks. this work studies comparator networks in which several of the outputs are accelerated. that is, they are generated much faster than the other outputs, and this without hindering the other outputs. we study this acceleration in the context of merging networks and sorting networks. the paper presents a new merging technique, the tri-section technique, that separates, using a depth 1 network, two sorted sequences into three sets, such that every key in one set is smaller than or equal to any key in the following set. after this separation, each of these sets can be sorted separately, causing the above acceleration of certain outputs. an additional contribution of this paper concerns the well-known 0-1 principle [d.e. knuth, the art of computer programming vol. 3: sorting and searching, second edition, addison-wesley, 1998]. this principle is a powerful tool that simplifies the construction and analysis of comparator networks. the paper demonstrates that, in some cases, there is a better tool for achieving the same goal. in the case at hand, this new tool simplifies one of our proofs by having fewer special cases than the classical 0-1 principle. a second additional contribution concerns batcher's merging techniques. it was shown in [t. levy, a. litman, on merging networks, technical report cs-2007-16, technion, department of computer science, 2007] that all published merging networks, whose width is a power of 2, are a natural generalization of batcher's odd-even merging network. all these published merging networks are of minimal depth and have no degenerate comparators. this raises the following question. is there a merging network, having the above properties, that is not a natural generalization of batcher's odd-even merging network? the tri-section technique provides a positive answer to this question.
on the size of computationally complete hybrid networks of evolutionary processors. a hybrid network of evolutionary processors (an hnep) is a graph where each node is associated with an evolutionary processor (a special rewriting system), a set of words, an input filter and an output filter. every evolutionary processor is given with a finite set of one type of point mutations (an insertion, a deletion or a substitution of a symbol) which can be applied to certain positions of a string over the domain of the set of these rewriting rules. the hnep functions by rewriting the words that can be found at the nodes and then re-distributing the resulting strings according to a communication protocol based on a filtering mechanism. the filters are defined by certain variants of random-context conditions. hneps can be considered as both language generating devices (ghneps) and language accepting devices (ahneps). in this paper, by improving the previous results, we prove that any recursively enumerable language can be determined by a ghnep and an ahnep with 7 nodes. we also show that the families of ghneps and ahneps with 2 nodes are not computationally complete.
predictable semiautomata. we introduce a new class of nondeterministic semiautomata: a nondeterministic semiautomaton s is predictable if there exists k>=0 such that, if s knows the current input a and the next k inputs, the transition under a can be made deterministically. nondeterminism may occur only when the length of the unread input is @?k. we develop a theory of predictable semiautomata. we show that, if a semiautomaton with n states is k-predictable, but not (k-1)-predictable, then k@?(n^2-n)/2, and this bound can be reached for a suitable input alphabet. we characterize k-predictable semiautomata, and introduce the predictor semiautomaton, based on a look-ahead semiautomaton. the predictor is essentially deterministic and simulates a nondeterministic semiautomaton by finding the set of states reachable by a word w, if it belongs to the language l of the semiautomaton (i.e., if it defines a path from an initial state to some state), or by stopping as soon as it infers that w@?l. membership in l can be decided deterministically.
burrows-wheeler transform and palindromic richness. the investigation of the extremal case of the burrows-wheeler transform leads to study the words w over an ordered alphabet a={a"1,a"2,...,a"k}, with a"1
two equivalence relations on digital lines with irrational slopes. a continued fraction approach to upper mechanical words. we examine the influence of the elements of the continued fraction (cf) expansion of irrational positive a less than 1 on the construction of runs in the digitization of the positive half line y=ax or, equivalently, on the run-hierarchical structure of the upper mechanical word with slope a and intercept 0. special attention is given to the cf elements equal to 1. we define two complementary equivalence relations on the set of slopes, based on their cf expansions. a new description of digital lines is presented; we show how to define a straight line or upper mechanical word by two sequences of positive integers fulfilling some extra conditions. these equivalence relations and this new description enable us to analyze the construction of digital lines and upper mechanical words. the analysis of suprema of equivalence classes under one of these relations leads to a result which involves fibonacci numbers.
two non-holonomic lattice walks in the quarter plane. we present two classes of random walks restricted to the quarter plane with non-holonomic generating functions. the non-holonomicity is established using the iterated kernel method, a variant of the kernel method. this adds evidence to a recent conjecture on combinatorial properties of walks with holonomic generating functions [m. mishna, classifying lattice walks in the quarter plane, j. combin. theory ser. a 116 (2009) 460-477]. the method also yields an asymptotic expression for the number of walks of length n.
on the joint subword complexity of automatic sequences. let the (subword) complexity of a sequence u=(u(n))"n"="0^~ over a finite set @s be the function m@?p"u(m), where p"u(m) denotes the number of distinct blocks u(n)...u(n+m-1) of size m in u. in this paper, we study the complexity of u->(n)=(u"1(n),...,u"r(n))"n"="0^~ when each u"i=(u"i(n))"n"="0^~, i=1,...,r, is a q"i-automatic sequence over a finite set @s"i and q"1,...,q"r>=2 are pairwise coprime integers. as an application, we answer a question of allouche and shallit regarding morphic real numbers.
operational state complexity of nested word automata. we introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. we study the state complexity of boolean operations and obtain lower bounds that are tight within an additive constant. the results for union and complementation differ from corresponding bounds for ordinary finite automata. for reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.
fine and wilf words for any periods ii. given positive integers n, and p"1,...,p"r, we establish a fast word combinatorial algorithm for constructing a word w=w"1...w"n of length n, with periods p"1,...,p"r, and on the maximal number of distinct letters. moreover, we show that the constructed word, which is unique up to word isomorphism, is a pseudo-palindrome - i.e. it is a fixed point of an involutory antimorphism.
configuration structures, event structures and petri nets. in this paper the correspondence between safe petri nets and event structures, due to nielsen, plotkin and winskel, is extended to arbitrary nets without self-loops, under the collective token interpretation. to this end we propose a more general form of event structure, matching the expressive power of such nets. these new event structures and nets are connected by relating both notions with configuration structures, which can be regarded as representations of either event structures or nets that capture their behaviour in terms of action occurrences and the causal relationships between them, but abstract from any auxiliary structure. a configuration structure can also be considered logically, as a class of propositional models, or-equivalently-as a propositional theory in disjunctive normal from. converting this theory to conjunctive normal form is the key idea in the translation of such a structure into a net. for a variety of classes of event structures we characterise the associated classes of configuration structures in terms of their closure properties, as well as in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated petri nets.