waashk/dblp huggingface dataset:
nfa reduction algorithms by means of regular inequalities. we present different techniques for reducing the number of states and transitions in nondeterministic automata. these techniques are based on the two preorders over the set of states, related to the inclusion of left and right languages. since their exact computation is np-hard, we focus on polynomial approximations which enable a reduction of the nfa all the same. our main algorithm relies on a first approximation, which can be easily implemented by means of matrix products with an o(mn3) time complexity, and optimized to an o(mn) time complexity, where m is the number of transitions and n is the number of states. this first algorithm appears to be more efficient than the known techniques based on equivalence relations as described by lucian ilie and sheng yu. afterwards, we briefly describe some more accurate approximations and the exact (but exponential) calculation of these preorders by means of determinization.
enumeration of l-convex polyominoes by rows and columns. in this paper, we consider the class of l-convex polyominoes, i.e. the convex polyominoes in which any two cells can be connected by a path of cells in the polyomino that switches direction between the vertical and the horizontal at most once.using the eco method, we prove that the number fn of l-convex polyominoes with perimeter 2(n + 2) satisfies the rational recurrence relation fn = 4fn-1 - 2fn-2, with f0 = 1, f1 = 2, f2 = 7. moreover, we give a combinatorial interpretation of this statement. in the last section, we present some open problems.
a reconstruction algorithm for l-convex polyominoes. we give an algorithm that uniquely reconstruct an l-convex polyomino from the size of some special paths, called bordered l-paths.
canonical derivatives, partial derivatives and finite automaton constructions. let e be a regular expression. our aim is to establish a theoretical relation between two well-known automata recognizing the language of e, namely the position automaton pe constructed by glushkov or mcnaughton and yamada, and the equation automaton ee constructed by mirkin or antimirov. we define the notion of c-derivative (for canonical derivative) of a regular expression e and show that if e is linear then two brzozowski's derivatives of e are aci-similar if and only if the corresponding c-derivatives are identical. it allows us to represent the berry-sethi's set of continuations of a position by a unique c-derivative, called the c-continuation of the position. hence the definition of ce, the c-continuation automaton of e, whose states are pairs made of a position of e and of the associated c-continuation. if states are viewed as positions, ce is isomorphic to pe. on the other hand, a partial derivative, as defined by antimirov, is a class of c-derivatives for some equivalence relation, thus ce reduces to ee. finally ce makes it possible to go from pe to ee, while this cannot be achieved directly (from the state graphs). these theoretical results lead to an o(|e|2) space and time algorithm to compute the equation automaton, where |e| is the size of the expression. this is the complexity of the most efficient constructions yielding the position automaton, while the size of the equation automaton is not greater and generally much smaller than the size of the position automaton.
solution of some conjectures about topological properties of linear cellular automata. we study two dynamical properties of linear d-dimensional cellular automata over zm namely, denseness of periodic points and topological mixing. for what concerns denseness of periodic points, we complete the work initiated in (theoret. comput. sci. 174 (1997) 157, theoret. comput. sci. 233 (1-2) (2000) 147, 14th annual symp. on theoretical aspects of computer science (stacs '97), lncs n. 1200, springer, berlin, 1997, pp. 427-438) by proving that a linear cellular automata has dense periodic points over the entire space of configurations if and only if it is surjective (as conjectured in (cattaneo et al., 2000)). for non-surjective linear ca we give a complete characterization of the subspace where periodic points are dense. for what concerns topological mixing, we prove that this property is equivalent to transitivity and then easily checkable. finally, we classify linear cellular automata according to the definition of chaos given by devaney in (an introduction to chaotic dynamical systems, 2nd ed., addison-wesley, reading, ma, usa, 1989).
new resource augmentation analysis of the total stretch of srpt and sjf in multiprocessor scheduling. this paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms shortest remaining processing time first (srpt) and shortest job first (sjf) for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. srpt is perhaps the most well-studied algorithm for minimizing total flow time or stretch. this paper gives the first resource augmentation analysis of the total stretch of srpt, showing that it is indeed o(1)-speed 1-competitive. this paper also gives a simple lower bound result showing that srpt is not s-speed 1-competitive for any s < 1.5.this paper also makes contribution to the analysis of sjf. extending the work of [l. becchetti, s. leonardi, a. marchetti-spaccamela, k. pruhs, online weighted flow time and deadline scheduling, in: random-approx, 2001, pp. 36-47], we are able to show that sjf is o(1)-speed 1-competitive for minimizing total stretch. more interestingly, we find that the competitiveness of sjf can be reduced arbitrarily by increasing the processor speed (precisely, sjf is o(s)-speed (1/s)-competitive for any s ≥ 1). we conjecture that srpt also admits a similar result.
on-line stream merging in a general setting. this paper is concerned with on-line scheduling algorithms for merging streams in a video-on-demand system so as to minimize the server bandwidth. we present the first algorithm that has a constant competitive factor (precisely, 5). our algorithm, unlike previous ones, is not limited to the scenario where clients are equipped with large buffer and client receiving bandwidth. it remains 5-competitive in all settings of buffer size and receiving bandwidth. technically speaking, our algorithm is based on a novel observation that the behavior of any schedule can be modeled by a rectilinear (binary) tree on a grid. this observation eases the analysis of our algorithm as well as the optimal algorithm.
presheaf models for ccs-like languages. the aim of this paper is to harness the mathematical machinery around presheaves for the purposes of process calculi. joyal, nielsen and winskel proposed a general definition of bisimulation from open maps. here we show that open-map bisimulations within a range of presheaf models are congruences for a general process language, in which ccs and related languages are easily encoded. the results are then transferred to traditional models for processes. by first establishing the congruence results for presheaf models, abstract, general proofs of congruence properties can be provided and the awkwardness caused through traditional models not always possessing the cartesian liftings, used in the breakdown of process operations, are side stepped. the abstract results are applied to show that hereditary history-preserving bisimulation is a congruence for ccs-like languages to which is added a refinement operator on event structures as proposed by van glabbeek and goltz.
generating and characterizing the perfect elimination orderings of a chordal graph. we develop a constant time transposition "oracle" for the set of perfect elimination orderings of chordal graphs. using this oracle, we can generate a gray code of all perfect elimination orderings in constant amortized time using known results about antimatroids. using clique trees, we show how the initialization of the algorithm can be performed in linear time. we also develop two new characterizations of perfect elimination orderings: one in terms of chordless paths, and the other in terms of minimal u-v separators.
on infinite transition graphs having a decidable monadic theory. we define a family of graphs whose monadic theory is (in linear space) reducible to the monadic theory s2s of the complete ordered binary tree. this family contains strictly the context-free graphs investigated by muller and schupp, and also the equational graphs defined by courcelle. using words as representations of vertices, we give a complete set of representatives by prefix rewriting of rational languages. this subset of possible representatives is a boolean algebra preserved by transitive closure of arcs and by rational restriction on vertices.
on the transition graphs of turing machines. as for pushdown automata, we consider labelled turing machines with ε-rules. with any turing machine m and with a rational set c of configurations, we associate the restriction to c of the ε-closure of the transition set of m. we get the same family of graphs by using the labelled word rewriting systems. we show that this family is the set of graphs obtained from the binary tree by applying an inverse mapping into f followed by a rational restriction, where f is any family of recursively enumerable languages containing the rational closure of all linear languages. we show also that this family is obtained from the rational graphs by inverse rational mappings. finally we show that this family is also the set of graphs recognized by (unlabelled) turing machines with labelled final states, and even if we restrict to deterministic turing machines.
wide-sense nonblocking for symmetric or asymmetric 3-stage clos networks under various routing strategies. benes established the notion of wide-sense nonblocking by constructing an example on the symmetric 3-stage clos network under packing which requires less hardware compared to strict nonblocking. this has remained the only example of a wide-sense non-blocking 3-stage clos network which is not strictly nonblocking. in this paper, we study packing as well as several other routing strategies which have been studied in the literature and proved that no other example exists for the symmetric 3-stage clos network. we then extend the study to asymmetric 3-stage clos network for the first time. in particular, we extend benes example to asymmetric 3-stage clos network and show that these are the only two possible examples for the strategies under study.
periodicity, morphisms, and matrices. in 1965, fine and wilf proved the following theorem: if (fn)n≥0 and (gn)n≥0 are periodic sequences of real numbers, of period lengths h and k, respectively, and fn = gn for 0 ≤ n > h + k - gcd(h,k), then fn = gn for all n ≥ 0. furthermore, the constant h + k - gcd(h,k) is best possible. in this paper, we consider some variations on this theorem. in particular, we study the case where fn ≤ gn, instead of fn = gn. we also obtain generalizations to more than two periods.we apply our methods to a previously unsolved conjecture on iterated morphisms, the decreasing length conjecture: if h : σ* → σ* is a morphism with |σ|= n, and w is a word with |w| < |h(w)| < |h2(w)| < ... < |hk(w)|, then k ≤ n.
oblivious polynomial evaluation and oblivious neural learning. we study the problem of oblivious polynomial evaluation (ope). there are two parties, alice who has a polynomial p, and bob who has an input x. the goal is for bob to compute p(x) in such a way that alice learns nothing about x and bob learns only what can be inferred from p(x). previously existing protocols were based on some newly-invented intractability assumptions that have not been well studied, so one may have doubts about the security of these protocols. in this paper, we propose ope protocols which are only based on the standard primitive oblivious transfer, and still our protocols are more efficient in several natural cases. our protocols can also be easily modified to handle multivariate polynomials and polynomials over floating-point numbers. as an application, we study the problem of oblivious neural learning, where one party has a neural network and the other, with some training set, wants to train the neural network in an oblivious way. we provide a protocol for this problem, which is based on our protocol for ope.
evolution and observation--a non-standard way to generate formal languages. in biology and chemistry a standard proceeding is to conduct an experiment, observe its progress, and then take the result of this observation as the final output. inspired by this, we have introduced p/o systems (a. alhazov, c. martín-vide, gh. paun, pre-proc. of the workshop on membrane computing 2003, tarrragona, spain; http://pizarro.fll.urv.es/continguts/linguistica/ proyecto/reports/wmc03.html), where languages are generated by multiset automata that observe the evolution of membrane systems.now we apply this approach also to more classical devices of formal language theory. namely, we use finite automata observing the derivations of grammars or of lindenmayer systems. we define several modes of operation for grammar/observer systems. in two of these modes a context-free grammar (or even a locally commutative context-free grammar) with a finite automaton as observer suffices to generate any recursively enumerable language. in a third case, we obtain a class of languages between the context-free and context-sensitive ones.
cartesian authentication codes from functions with optimal nonlinearity. in this paper, we present several classes of authentication codes using functions with perfect nonlinearity and optimum nonlinearity. some of the authentication codes are optimal. on the other hand, these authentication codes are easy to implement due to their simple algebraic structures.
an algorithm for reporting maximal -cliques. given two graphs, a fundamental task faced by matching algorithms consists of computing either the (connected) maximal common induced subgraphs ((c)mcis) or the (connected) maximal common edge subgraphs ((c)mces). in particular, computing the cmcis or cmces reduces to reporting so-called c-connected cliques in product graphs, a problem for which an algorithm has been presented in i. koch, fundamental study: enumerating all connected maximal common subgraphs in two graphs, theoret. comput. sci. 250 (1-2), (2001) 1-30. this algorithm suffers from two problems which are corrected in this note.
model checking mobile ambients. we settle the complexity bounds of the model checking problem for the ambient calculus with public names against the ambient logic. we show that if either the calculus contains replication or the logic contains the guarantee operator, the problem is undecidable. in the case of the replication-free calculus and guarantee-free logic we prove that the problem is pspace-complete. for the complexity upper bound, we devise a new representation of processes that remains of polynomial size during process execution; this allows us to keep the model checking procedure in polynomial space. moreover, we prove pspace-hardness of the problem for several quite simple fragments of the calculus and the logic; this suggests that there are no interesting fragments with polynomial-time model checking algorithms.
finding frequent items in data streams. we present a 1-pass algorithm for estimating the most frequent items in a data stream using limited storage space. our method relies on a data structure called a count sketch, which allows us to reliably estimate the frequencies of frequent items in the stream. our algorithm achieves better space bounds than the previously known best algorithms for this problem for several natural distributions on the item frequencies. in addition, our algorithm leads directly to a 2-pass algorithm for the problem of estimating the items with the largest (absolute) change in frequency between two data streams. to our knowledge, this latter problem has not been previously studied in the literature.
on factorization forests of finite height. simon (theoret. comput. sci. 72 (1990) 65-94) has proved that every morphism from a free semigroup to a finite semigroup s admits a ramseyan factorization forest of height at most 9|s|. in this paper, we prove the same result of simon with an improved bound of 7|s|. we provide a simple algorithm for constructing a factorization forest. in addition, we show that the algorithm cannot be improved significantly. we give examples of semigroup morphism such that any ramseyan factorization forest for the morphism would require a height not less than |s|.
probabilistic analysis of algorithms for the dutch national flag problem. a detailed probabilistic analysis is given of algorithms for the dutch national flag problem. we derive central and local limit theorems for the cost, as well as probabilities of large deviations. performance of a related algorithm is also studied.
on the entropy of regular languages. let l be an irreducible regular language. let w be a non-empty set of words (or sub-words) of l and denote by lw = {v ∈ l:w ⊏ v, ∀w ∈ w} the language obtained from l by forbidding all the words w in w. then the entropy decreases strictly: ent(lw) < ent(l). in this note we present a new proof of this fact, based on a method of gromov, which avoids the perron-frobenius theory. this result applies to the regular languages of finitely generated free groups and an additional application is presented.
subset construction complexity for homogeneous automata, position automata and zpc-structures. the aim of this paper is to investigate how subset construction performs on specific families of automata. a new upper bound on the number of states of the subset-automaton is established in the case of homogeneous automata. the complexity of the two basic steps of subset construction, i.e. the computation of deterministic transitions and the set equality tests, is examined depending on whether the nondeterministic automaton is an unrestricted one, an homogeneous one, a position one or a zpc-structure, which is an implicit construction for a position automaton. copyright 2001 elsevier science b.v.
growth-sensitivity of context-free languages. a language l over a finite alphabet σ is called growth-sensitive if forbidding any set of subwords f yields a sub-language lf whose exponential growth rate is smaller than that of l. it is shown that every (essentially) ergodic non-linear context-free language of convergent type is growth-sensitive. "ergodic" means that the dependency di-graph of the generating context-free grammar is strongly connected, and "essentially ergodic" means that there is only one nonregular strong component in that graph. the methods combine (1) an algorithm for constructing from a given grammar one that generates the associated 2-block language and (2) a generating function technique regarding systems of algebraic equations. furthermore, the algorithm of (1) preserves unambiguity as well as the number of non-regular strong components of the dependency di-graph.
minimizing the size of an identifying or locating-dominating code in a graph is np-hard. let g = (v,e) be an undirected graph and c a subset of vertices. if the sets br(υ) ∩ c, υ ∈ v (respectively, υ ∈ v\c), are all nonempty and different, where br(υ) denotes the set of all points within distance r from υ, we call c an r-identifying code (respectively, an r-locating-dominating code). we prove that, given a graph g and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in g, is np-complete for any r.
on the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity. an interval [a, a + d] of natural numbers verifies the property of no coprimeness if and only if every element a + 1, a + 2,..., a + d - 1 has a common prime divisor with extremity a or a + d. we show the set of such a and the set of such d are recursive. the computation of the first d leads to rise a lot of open problems.
an inexact-suffix-tree-based algorithm for detecting extensible patterns. given an input sequence of data, a rigid pattern is a repeating sequence, possibly interspersed with dont-care characters. the data could be a sequence of characters or sets of characters or even real values. in practice, the patterns or motifs of interest are the ones that also allow a variable number of gaps (or dont-care characters): these are patterns with spacers termed extensible patterns in a bioinformatics context, similar patterns have also been called flexible patterns or motifs. the extensibility is succinctly defined by a single integer parameter d ≥ 1 which is interpreted as the allowable space to be between 1 and d characters between two successive solid characters in a reported motif. we introduce a data structure called the inexact-suffix tree and present an algorithm based on this data structure. this has been tested on primarily biological data such as dna and protein sequences. however the generality of the system makes it equally applicable in other data mining, clustering, and knowledge extraction applications.
effectively closed sets and graphs of computable real functions. in this paper, we compare the computability and complexity of a continuous real function f with the computability and complexity of the graph g of the function f. a similar analysis will be carried out for functions on subspaces of the real line such as the cantor space, the baire space and the unit interval. in particular, we define four basic types of effectively closed sets c depending on whether (i) the set of closed intervals which with nonempty intersection with c is recursively enumerable (r.e.), (ii) the set of closed intervals with empty intersection with c is r.e., (iii) the set of open intervals which with nonempty intersection with c is r.e., and (iv) the set of open intervals with empty intersection with c is r.e. we study the relationships between these four types of effectively closed sets in general and the relationships between these four types of effectively closed sets for closed sets which are graphs of continuous functions.
probable innocence revisited. in this paper we propose a formalization of probable innocence, a notion of probabilistic anonymity that is associated to "realistic" protocols such as crowds. we analyze critically two different definitions of probable innocence from the literature. the first one, corresponding to the property that reiter and rubin have proved for crowds, aims at limiting the probability of detection. the second one, by halpern and o'neill, aims at constraining the attacker's confidence. our proposal combines the spirit of both these definitions while generalizing them. in particular, our definition does not need symmetry assumptions, and it does not depend on the probabilities of the users to perform the action of interest. we show that, in case of a symmetric system, our definition corresponds exactly to the one of reiter and rubin. furthermore, in the case of users with uniform probabilities, it amounts to a property similar to that of halpern and o'neill.another contribution of our paper is the study of probable innocence in the case of protocol composition, namely when multiple runs of the same protocol can be linked, as in the case of crowds.
actions, wreath products of -varieties and concatenation product. the framework of c-varieties, introduced by the third author, extends the scope of eilenberg's variety theory to new classes of languages. in this paper, we first define c-varieties of actions, which are closely related to automata, and prove their equivalence with the original definition of c-varieties of stamps. next, we complete the study of the wreath product initiated by ésik and ito by extending its definition to c-varieties in two different ways, which are proved to be equivalent. we also state an extension of the wreath product principle, a standard tool of language theory. finally, our main result generalizes to c-varieties the algebraic characterization of the closure under product of a variety of languages.