waashk/dblp huggingface dataset:
least-recently-used caching with dependent requests. we investigate a widely popular least-recently-used (lru) cache replacement algorithm with semi-markov modulated requests. semi-markov processes provide the flexibility for modeling strong statistical correlation, including the widely reported long-range dependence in the world wide web page request patterns. when the frequency of requesting a page n is equal to the generalized zipf's law c/nα, α > 1, our main result shows that the cache fault probability is asymptotically, for large cache sizes, the same as in the corresponding lru system with i.i.d. requests. the result is asymptotically explicit and appears to be the first computationally tractable average-case analysis of lru caching with statistically dependent request sequences. the surprising insensitivity of lru caching performance demonstrates its robustness to changes in document popularity. furthermore, we show that the derived asymptotic result and simulation experiments are in excellent agreement, even for relatively small cache sizes.
characterisations of balanced words via orderings. three new characterisations of balanced words are presented. each of these characterisations is based on the ordering of a shift orbit, either lexicographically or with respect to the norm |ċ|1 (which counts the number of occurrences of the symbol 1).
a lower bound on compression of unknown alphabets. many applications call for universal compression of strings over large, possibly infinite, alphabets. however, it has long been known that the resulting redundancy is infinite even for i.i.d distributions. it was recently shown that the redundancy of the strings' patterns, which abstract the values of the symbols, retaining only their relative precedence, is subliner in the blocklength n, hence the per-symbol redundancy diminishers to zero. in this paper we show that pattern redundancy is at least (1.5log2e)n1/3 bits to do so, we construct a generating function whose coefficients lower bound the redundancy, and use hayman's saddle-point approximation technique to determine the coefficients' asymptotic behavior.
scheduling linear deteriorating jobs with an availability constraint on a single machine. we consider a single machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time and the machine is subject to an availability constraint. we consider the non-resumable case. the objectives are to minimize the makespan and the total completion time. we show that both problems are np-hard and present pseudopolynomial time optimal algorithms to solve them. furthermore, for the makespan problem, we present an optimal approximation algorithm for the on-line case, and a fully polynomial time approximation scheme for the off-line case. for the total completion time problem, we provide a heuristic and evaluate its efficiency by computational experiments.
unification and extension of weighted finite automata applicable to image compression. weighted finite automata (wfa), including the linear wfa due to culik and kari and the acyclic wfa due to hafner, have been under investigation over the years for their applications to image compression. we shall in this work first examine in great details the underlying wfa structure and propose the most systematic extension, along with its full legitimacy analysis, to the wfa that are applicable to image compression. a new mechanism based on the concept of resolution-wise and resolution-driven image mappings is developed to create rich families of legitimate similarity images so as to reduce the overall wfa size, a property that is critically related the performance of wfa-based compression codecs. moreover, we shall also unify the relevant wfa by showing an acyclic wfa can always be merged into a linear wfa but not vice versa.
on liveness and boundedness of asymmetric choice nets. this paper concerns two important techniques, characterization and property-preserving transformation, for verifying some basic properties of asymmetric choice petri nets (ac nets). in the literature, a majority of the characterizations are for ordinary free choice nets. this paper presents many extended (from free choice nets) and new characterizations for four properties: liveness with respect to an initial marking, liveness monotonicity with respect to an initial marking, well-formedness, liveness and boundedness with respect to an initial marking. the nets involved are extended to homogeneous free choice nets, ordinary ac nets and homogeneous ac nets. this paper also investigates the transformation of merging a set of places of an ordinary ac net and proposes the conditions for it to preserve the siphon-trap-property (st-property), liveness, boundedness and reversibility. the results are then applied to the verification of resource-sharing systems. at present, the major approaches for solving this problem are based on state machines or marked graphs and are not based on property preservation. our approach extends the scopes of the underlying nets to ac nets and the verification techniques. it is found that the st-property plays a very important role in many of the results. furthermore, mainly through examples, the importance of the assumptions in the proposed characterizations and transformation and the limitation on further extensions are pointed out.
on the -path cover problem for cacti. in this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. the k-path cover problem for general graphs is np-complete. though notable applications of this problem to database design, network, vlsi design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. in order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called steiner version of the k-path cover problem, and develop an efficient algorithm for the steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time.
state complexity of some operations on binary regular languages. we investigate the state complexity of some operations on binary regular languages. in particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. we prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.
creol: a type-safe object-oriented model for distributed concurrent systems. object-oriented distributed computing is becoming increasingly important for critical infrastructure in society. in standard object-oriented models, objects synchronize on method calls. these models may be criticized in the distributed setting for their tight coupling of communication and synchronization; network delays and instabilities may locally result in much waiting and even deadlock. the creol model targets distributed objects by a looser coupling of method calls and synchronization. asynchronous method calls and high-level local control structures allow local computation to adapt to network instability. object variables are typed by interfaces, so communication with remote objects is independent from their implementation. the inheritance and subtyping relations are distinct in creol. interfaces form a subtype hierarchy, whereas multiple inheritance is used for code reuse at the class level. this paper presents the creol syntax, operational semantics, and type system. it is shown that runtime type errors do not occur for well-typed programs.
recognizing frozen variables in constraint satisfaction problems. in constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. we study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the instances. we show that the complexity of such problems is determined by certain algebraic properties of these relations. under the assumption that np ≠ conp (and consequently ptime ≠ np), we characterize all tractable problems, and describe large classes of np-complete, conp-complete, and dp-complete problems. as an application of these results, we completely classify the complexity of the problem in two cases: (1) with domain size 2; and (2) when all unary relations are present. we also give a rough classification for domain size 3.
a note on the strong and weak generative powers of formal systems. this paper is a note on some relationships between the strong and weak generative powers of formal systems, in particular, from the point of view of squeezing more strong power out of a formal system without increasing its weak generative power. we will comment on some old and new results from this perspective. our main goal of this note is to comment on the strong generative power of context-free grammars, lexicalized tree-adjoining grammars (and some of their variants) and lambek grammars, especially in the context of crossing dependencies, in view of the recent work of tiede (ph.d. dissertation, indiana university, bloomington, 1999).
an efficient deterministic parallel algorithm for two processors precedence constraint scheduling. we present here a new deterministic parallel algorithm for the two-processor scheduling problem. the algorithm uses only o(n3) processors and takes o(log2n) time on a crew pram. in order to prove the above bounds we show how to compute in nc the lexicographically first matching for a special kind of convex bipartite graphs.
restarting automata with restricted utilization of auxiliary symbols. the restarting automaton is a restricted model of computation that was introduced by jančar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyse sentences of natural languages. the most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. in fact, we consider two types of restrictions. first, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. we establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.
episturmian words and episturmian morphisms. infinite episturmian words are a generalization of sturmian words which includes the arnoux-rauzy sequences. we continue their study and that of episturmian morphisms, begun previously, in relation with the action of the shift operator. palindromic and periodic factors of these words are described. we consider, in particular, the case where these words are generated by morphisms and introduce then a notion of intercept generalizing that of sturmian words. finally, we prove that the frequencies of the factors in a strong sense do exist for all episturmian words.
general linear relations between different types of predictive complexity. in this paper we introduce a general method of establishing tight linear inequalities between different types of predictive complexity. predictive complexity is a generalization of kolmogorov complexity and it bounds the ability of an algorithm to predict elements of a sequence. our method relies upon probabilistic considerations and allows us to describe explicitly the sets of coefficients which correspond to true inequalities. we apply this method to two particular types of predictive complexity, namely, logarithmic complexity, which coincides with a variant of kolmogorov complexity, and square-loss complexity, which is interesting for applications.
loss functions, complexities, and the legendre transformation. the paper introduces a way of re-constructing a loss function from predictive complexity. we show that a loss function and expectations of the corresponding predictive complexity w.r.t. the bernoulli distribution are related through the legendre transformation. it is shown that if two loss functions specify the same complexity then they are equivalent in a strong sense. the expectations are also related to the so-called generalized entropy.
maximal pattern complexity of two-dimensional words. the maximal pattern complexity of one-dimensional words has been studied in several papers [t. kamae, l. zamboni, sequence entropy and the maximal pattern complexity of infinite words, ergodic theory dynam. systems 22(4) (2002) 1191-1199; t. kamae, l. zamboni, maximal pattern complexity for discrete systems, ergodic theory dynam. systems 22(4) (2002) 1201-1214; t. kamae, h. rao, pattern complexity over l letters, e. comb. j., to appear; t. kamae, y.m. xue, two dimensional word with 2k maximal pattern complexity, osaka j. math. 41(2) (2004) 257-265]. we study the maximal pattern complexity pα(k) of two-dimensional words α. a two-dimensional version of the notion of strong recurrence is introduced. it is shown that if α is strongly recurrent, then either α is doubly periodic or pα(k≥2k (k = 1, 2,...). accordingly, we define a two-dimensional pattern sturmian word as a strongly recurrent word α with pα(k = 2k. examples of pattern sturmian words are given.
automatic semigroups and categories. we consider various automata-theoretic properties of semigroupoids and small categories and their relationship to the corresponding properties in semigroups and monoids. we introduce natural definitions of finite automata and regular languages over finite graphs, generalising the usual notions over finite alphabets. these allow us to introduce a definition of automaticity for semi-groupoids and small categories, which generalises those introduced for semigroups by hudson and for groupoids by epstein. we also introduce a definition of prefix-automaticity for semigroupoids and small categories, generalising that for certain monoids introduced by silva and steinberg.we study the relationship between automaticity properties in a semigroupoid and in a certain associated semigroup. this allows us to extend to semigroupoids and small categories a number of results about automatic and prefix-automatic semigroups and monoids. in the course of our study, we also prove some new results about automaticity and prefix-automaticity in semigroups and monoids. these include the fact that prefix-automaticity is preserved under the taking of cofinite subsemigroups.
word problems recognisable by deterministic blind monoid automata. we consider blind, deterministic, finite automata equipped with a register which stores an element of a given monoid, and which is modified by right multiplication by monoid elements. we show that, for monoids m drawn from a large class including groups, such an automaton accepts the word problem of a group h if and only if h has a finite index subgroup which embeds in the group of units of m. in the case that m is a group, this answers a question of elston and ostheimer.
strong normalizability of the non-deterministic catch/throw calculi. the catch/throw mechanism in common lisp provides a simple control mechanism for non-local exits. we study typed calculi by nakano and sato which formalize the catch/throw mechanism. these calculi correspond to classical logic through the curry-howard isomorphism, and one of their characteristic points is that they have non-deterministic reduction rules. these calculi can represent various computational meaning of classical proofs. this paper is mainly concerned with the strong normalizability of these calculi. namely, we prove the strong normalizability of these calculi, which was an open problem. we first formulate a non-deterministic variant of parigot's &lambda;&mu;-calculus, and show it is strongly normalizing. we then translate the catch/throw calculi to this variant. since the translation preserves typing and reduction, we obtain the strong normalization of the catch/throw calculi. we also briefly consider second-order extension of the catch/throw calculi. copyright 2002 elsevier science b.v
linear and affine logics with temporal, spatial and epistemic operators. a temporal spatial epistemic intuitionistic linear logic (tseill) is introduced, and the completeness theorem for this logic is proved with respect to kripke semantics. tseill has three temporal modal operators: [f] (any time in the future), [n] (next time) and [p] (past), some spatial modal operators [li] (locations), two epistemic modal operators; [k] (know) and (k), and a linear modal operator ! (exponential). a basic normal modal intuitionistic affine logic (bial) and its normal extensions are also defined, and the completeness theorems for these logics are proved with respect to kripke semantics. in the proposed semantic framework of these normal extensions, a simple correspondence can be given between frame conditions and lemmon-scott axioms. a dynamic intuitionistic affine logic (dial) is proposed as an affine version of (test-free) dynamic logic, and the completeness theorem for this logic is shown with respect to kripke semantics. finally, some intuitive interpretations, such as resource and informational interpretations, are given for the proposed logics and semantics. by using these logics, semantics and interpretations, various kinds of fine-grained resource-sensitive reasoning can be expressed.
finite-memory automata. a model of computation dealing with infinite alphabets is proposed. the model is based on replacing the equality test by unification. it appears to be a natural generalization of the classical rabin-scott finite-state automata and possesses many of their properties.
default theories over monadic languages. in this paper we compare the semantical and syntactical definitions of extensions for open default theories. we prove that, over monadic languages, these definitions are equivalent and do not depend on the cardinality of the underlying infinite world. we also show that, under the domain closure assumption, one free variable open default theories are decidable.
lower bounds on the minus domination and k-subdomination numbers. a three-valued function f defined on the vertex set of a graph g=(v,e), f:v → {-1,0,1} is a minus dominating function if the sum of its function values over any closed neighborhood is at least one. that is, for every v ∈ v, f(n[v]) ≥ 1, where n[v] consists of v and all vertices adjacent to v. the weight of a minus function is f(v)= σv ∈ v f(v). the minus domination number of a graph g, denoted by γ-(g), equals the minimum weight of a minus dominating function of g. in this paper, sharp lower bounds on minus domination of a bipartite graph are given. thus, we prove a conjecture proposed by dunbar et al. (discrete math. 199 (1999) 35), and we give a lower bound on γks(g) of a graph g.
paired-domination in inflated graphs. the inflation g1 of a graph g with n(g) vertices and m(g) edges is obtained from g by replacing every vertex of degree d of g by a clique kd. a set s of vertices in a graph g is a paired dominating set of g if every vertex of g is adjacent to some vertex in s and if the subgraph induced by s contains a perfect matching. the paired domination number λp(g) is the minimum cardinality of a paired dominating set of g. in this paper, we show that if a graph g has a minimum degree δ(g) ≥ 2, then n(g) ≤ λp(g1) ≤ 4m(g)/[δ(g) + 1], and the equality λp(g1)=n(g) holds if and only if g has a perfect matching. in addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.
phase semantics for light linear logic. light linear logic (girard, inform. comput. 14 (1998) 175-204) is a refinement of the propositions-as-types paradigm to polynomial-time computation. a semantic setting for the underlying logical system is introduced here in terms of fibred phase spaces. strong completeness is established, with a purely semantic proof of cut elimination as a consequence. a number of mathematical examples of fibred phase spaces are presented that illustrate subtleties of light linear logic.
the aggregation and cancellation techniques as a practical tool for faster matrix multiplication. the main purpose of this paper is to present a fast matrix multiplication algorithm taken from the paper of laderman et al. (linear algebra appl. 162-164 (1992) 557) in a refined compact "analytical" form and to demonstrate that it can be implemented as quite efficient computer code. our improved presentation enables us to simplify substantially the analysis of the computational complexity and numerical stability of the algorithm as well as its computer implementation. the algorithm multiplies two n × n matrices using o(n2.7760) arithmetic operations. in the case where n = 18 ċ 48k, for a positive integer k, the total number of flops required by the algorithm is 4.894n2.7760 - 16.165n2, which may be compared to a similar estimate for the winograd algorithm, 3.732n2.8074 - 5n2 flops, n = 8 ċ 2k, the latter being current record bound among all known practical algorithms. moreover, we present a pseudo-code of the algorithm which demonstrates its very moderate working memory requirements, much smaller than that of the best available implementations of strassen and winograd algorithms. for matrices of medium-large size (say, 2000 ≤ n < 10,000) we consider one-level algorithms and compare them with the (multilevel) strassen and winograd algorithms. the results of numerical tests clearly indicate that our accelerated matrix multiplication routines implementing two or three disjoint product-based algorithm are comparable in computational time with an implementation of winograd algorithm and clearly outperform it with respect to working space and (especially) numerical stability. the tests were performed for the matrices of the order of up to 7000, both in double and single precision.
succinct representations of languages by dfa with different levels of reliability. in this paper, we propose qualitative measures for the reliability of representations of languages by deterministic finite automata. we analyze the relationships between different qualitative features and investigate tradeoffs between different qualitative levels of reliability. furthermore, we prove that the savings in the number of states between representations having different qualitative features cannot be bounded by any function. these results hold even when the descriptions are required to exceed any given fixed level of quantified reliability.
weak repetitions in sturmian strings. in this paper, we analyze the weak repetitions in sturmian strings and show that an optimally efficient algorithm to compute the weak repetitions in sturmian strings according to the output encodings defined in the literature is quadratic in the string length. finally, we present an encoding that leads to a linear-time algorithm.
computing by commuting. we consider the power of the following rewriting: given a finite or regular set x of words and an initial word w, apply iteratively the operation which deletes a word from x from one of the ends of w and simultaneously catenates another word from x to the opposite end of w. we show that if the deletion is always done at the beginning and the catenation at the end, and the choice of a word to be catenated does not depend on the word erased, then the generated language is always regular, though the derivability relation is not, in general, rational. if the deletion and the catenation are done arbitrarily at the opposite ends, the language need not be regular. if the catenation is done at the same end as the deletion, the relation of derivability is rational even if the catenated word can depend on the word erased.