waashk/dblp huggingface dataset:
transition complexity of language operations. the number of transitions required by a nondeterministic finite automaton (nfa) to accept a regular language is a natural measure of the size of that language. there has been a significant amount of work related to the trade-off between the number of transitions and other descriptional complexity measures for regular languages. in this paper, we consider the effect of language operations on the number of transitions required to accept a regular language. this work extends previous work on descriptional complexity of regular language operations, in particular, under the measures of deterministic state complexity, nondeterministic state complexity and regular expression size.
learning multiple languages in groups. we consider a variant of gold's learning paradigm where a learner receives as input n different languages (in the form of one text where all input languages are interleaved). our goal is to explore the situation when a more ''coarse'' classification of input languages is possible, whereas more refined classification is not. more specifically, we answer the following question: under which conditions, a learner, being fed n different languages, can produce m grammars covering all input languages, but cannot produce k grammars covering input languages for any k>m. we also consider a variant of this task, where each of the output grammars may not cover more than r input languages. our main results indicate that the major factor affecting classification capabilities is the difference n-m between the number n of input languages and the number m of output grammars. we also explore the relationship between classification capabilities for smaller and larger groups of input languages. for the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n (the number of input languages), m (number of output grammars), and r (bound on the number of languages represented by each output grammar). this picture includes a combinatorial characterization of classification capabilities for the parameters n,m,r of certain types.
optimal lower bounds for rank and select indexes. we develop a new lower bound technique for data structures. we show an optimal @w(nlglgn/lgn) space lower bounds for storing an index that allows to implement rank and select queries on a bit vector b provided that b is stored explicitly. these results improve upon [peter bro miltersen, lower bounds on the size of selection and rank indexes, in: proceedings of the 16th annual acm-siam symposium on discrete algorithms, 2005, pp. 11-12]. we show @w((m/t)lgt) lower bounds for storing rank/select index in the case where b has m 1-bits in it and the algorithm is allowed to probe t bits of b. we also present an improved data structure that implements both rank and select queries with an index of size (1+o(1))(nlglgn/lgn)+o(n/lgn), that is, compared to existing results we give an explicit constant for storage in the ram model with word size lgn. an advantage of this data structure is that both rank and select indexes share the most space consuming part of order @q(nlglgn/lgn) making it more practical for implementation.
regulated rna rewriting: modelling rna editing with guided insertion. rna editing is an important alternative genetic processing event that is known to take place in all higher eukaryotes. we study a model of string rewriting based on the sophisticated rna editing mechanism found in trypanosome kinetoplasts. we demonstrate basic properties of three principal variants of this model which we show to form a strict hierarchy in terms of expressive power. we also present a method and software for simulating real biological rna editing via this model and apply the theoretical results to suggest real biological constraints on this process.
non-asymptotic calibration and resolution. we analyze a new algorithm for probability forecasting of binary observations on the basis of the available data, without making any assumptions about the way the observations are generated. the algorithm is shown to be well-calibrated and to have good resolution for long enough sequences of observations and for a suitable choice of its parameter, a kernel on the cartesian product of the forecast space [0, 1] and the data space. our main results are non-asymptotic: we establish explicit inequalities, shown to be tight, for the performance of the algorithm.
an infinite hierarchy induced by depth synchronization. depth-synchronization measures the number of parallel derivation steps in a synchronized context-free (scf) grammar. when not bounded by a constant the depth-synchronization measure of an scf grammar is at least logarithmic and at most linear with respect to the word length. languages with linear depth-synchronization measure and languages with a depth-synchronization measure in between logarithmic and linear are proven to exist. this gives rise to a strict infinite hierarchy within the family of scf (and et0l) languages.
stochastic complexity for mixture of exponential families in generalized variational bayes. the variational bayesian learning, proposed as an approximation of the bayesian learning, has provided computational tractability and good generalization performance in many applications. however, little has been done to investigate its theoretical properties. in this paper, we discuss the variational bayesian learning of the mixture of exponential families and derive the asymptotic form of the stochastic complexities in a generalized setting of the prior distribution. we show that the stochastic complexities become smaller than those of regular statistical models, which implies that the advantage of the bayesian learning still remains in the variational bayesian learning. stochastic complexity, which is called the marginal likelihood or the free energy, not only becomes important in addressing the model selection problem but also enables us to discuss the accuracy of the variational bayesian approach as an approximation of the true bayesian learning. the main result also shows the effects of the prior distribution under the generalized setting.
fast bwt in small space by blockwise suffix sorting. we present a new space- and time-efficient algorithm for computing the burrow-wheeler transform (bwt). for any choice of a parameter v@?[3,n^2^/^3], the computation of bwt for a text of length n takes o(nlogn+vn) worst-case time and o(nlogn+vn) average-case time using o(nlogn/v) bits of space in addition to the text and the bwt. for example, if v=log^2n, the time is o(nlog^2n) in the worst case and o(nlogn) on an average with the additional space requirement of o(n) bits. the algorithm is alphabet-independent: it uses only character comparisons, and the complexities do not depend on the alphabet size unless v does. a practical implementation is 2-3 times slower than one of the fastest and most space-efficient previous algorithms while needing only one-third of the main memory. the algorithm is based on suffix arrays, but unlike any other algorithm, it can construct the suffix array a small block at a time without storing the rest of the suffix array anywhere.
quantum automata for some multiperiodic languages. we exhibit small size measure-once one-way quantum finite automata (mo-1qfa's) inducing multiperiodic stochastic events. moreover, for certain classes of multiperiodic languages, we exhibit: (i) isolated cut point mo-1qfa's whose size logarithmically depends on the periods; (ii) monte carlo mo-1qfa's whose size logarithmically depends on the periods and polynomially on the inverse of the error probability.
adaptive searching in succinctly encoded binary relations and tree-structured documents. the methods most heavily used by search engines to answer conjunctive queries on binary relations (such as one associating keywords with web-pages) are based on computing the intersection of postings lists stored as sorted arrays and using variants of binary search. we show that a succinct representation of the binary relation permits much better results, while using less space than traditional methods. we apply our results not only to conjunctive queries on binary relations, but also to queries on semi-structured documents such as xml documents or file-system indexes, using a variant of an adaptive algorithm used to solve conjunctive queries on binary relations.
rank and select revisited and extended. the deep connection between the burrows-wheeler transform (bwt) and the so-called rank and select data structures for symbol sequences is the basis of most successful approaches to compressed text indexing. rank of a symbol at a given position equals the number of times the symbol appears in the corresponding prefix of the sequence. select is the inverse, retrieving the positions of the symbol occurrences. it has been shown that improvements to rank/select algorithms, in combination with the bwt, turn into improved compressed text indexes. this paper is devoted to alternative implementations and extensions of rank and select data structures. first, we show that one can use gap encoding techniques to obtain constant time rank and select queries in essentially the same space as what is achieved by the best current direct solution (and sometimes less). second, we extend symbol rank and select to substring rank and select, giving several space/time trade-offs for the problem. an application of these queries is in position-restricted substring searching, where one can specify the range in the text where the search is restricted to, and only occurrences residing in that range are to be reported. in addition, arbitrary occurrences are reported in text position order. several byproducts of our results display connections with searchable partial sums, chazelle's two-dimensional data structures, and grossi et al.'s wavelet trees.
on the existence of regular approximations. we approximate context-free, or more general, languages using finite automata. the degree of approximation is measured, roughly speaking, by counting the number of incorrect answers an automaton gives on inputs of length m and observing how these values behave for large m. more restrictive variants are obtained by requiring that the automaton never accepts words outside the language or that it accepts all words in the language. a further distinction is whether a given (context-free) language has a regular approximation which is optimal under the measure of approximation degree or an approximation which is arbitrarily close to optimal. we study closure and decision properties of the approximation measure.
burrows-wheeler compression: principles and reflections. after a general description of the burrows-wheeler transform and a brief survey of recent work on processing its output, the paper examines the coding of the zero-runs from the mtf recoding stage, an aspect with little prior treatment. it is concluded that the original scheme proposed by wheeler is extremely efficient and unlikely to be much improved. the paper then proposes some new interpretations and uses of the burrows-wheeler transform, with new insights and approaches to lossless compression, perhaps including techniques from error correction.
a general comparison of language learning from examples and from queries. in language learning, strong relationships between gold-style models and query models have recently been observed: in some quite general setting gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. these 'equalities' hold in the context of learning indexable classes of recursive languages. former studies on gold-style learning of such indexable classes have shown that, in many settings, the enumerability of the target class and the recursiveness of its languages are crucial for learnability. moreover, studying query learning, non-indexable classes have been mainly neglected up to now. so it is conceivable that the recently observed relations between gold-style and query learning are not due to common structures in the learning processes in both models, but rather to the enumerability of the target classes or the recursiveness of their languages. in this paper, the analysis is lifted onto the context of learning arbitrary classes of recursively enumerable languages. still, strong relationships between the approaches of gold-style and query learning are proven, but there are significant changes to the former results. though in many cases learners of one type can still be replaced by learners of the other type, in general this does not remain valid vice versa. all results hold even for learning classes of recursive languages, which indicates that the recursiveness of the languages is not crucial for the former 'equality' results. thus we analyze how constraints on the algorithmic structure of the target class affect the relations between two approaches to language learning.
learning attribute-efficiently with corrupt oracles. we study learning in a modified exact model, where the oracles are corrupt and only few of the presented attributes are relevant. both modifications were already studied in the literature [dana angluin, martins krikis, learning with malicious membership queries and exceptions (extended abstract), in: colt '94: proceedings of the seventh annual conference on computational learning theory, acm press, 1994, pp. 56-57 [3]; dana angluin, martins krikis, robert h. sloan, gyorgy turan, malicious omissions and errors in answers to membership queries, machine learning 28 (1997) 211-255; laurence bisht, nader h. bshouty, lawrance khoury, learning with errors in answers to membership queries (extracted abstract), in: focs '04: proceedings of the 45th annual ieee symposium on foundations of computer science, focs'04, ieee computer society, 2004, pp. 611-620; nader h. bshouty, lisa hellerstein, attribute-efficient learning in query and mistake-bound models, j. comput. system sci. 56 (3) (1998) 310-319 [12]; nick littlestone, learning quickly when irrelevant attributes abound: a new linear-threshold algorithm, machine learning 2 (4) (1988) 285-318; robert h. sloan, gyorgy turan, learning with queries but incomplete information (extended abstract), in: colt '94: proceedings of the seventh annual conference on computational learning theory, acm press, 1994, pp. 237-245 [5]], and efficient solutions were found to most of their variants. nonetheless, their reasonable combination is yet to be studied, and integrating the existing solutions either fails or works with a complexity that can be significantly improved. in this paper we prove the equivalence of exact learning attribute-efficiently with and without corrupt oracles. for each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. we also generalize and improve previous non-attribute-efficient algorithms for learning with corrupt oracles.
faster suffix sorting. we propose a fast and memory-efficient algorithm for lexicographically sorting the suffixes of a string, a problem that has important applications in data compression as well as string matching. our algorithm eliminates much of the overhead of previous specialized approaches while maintaining their robustness for degenerate inputs. for input size n, our algorithm operates in only two integer arrays of size n, and has worst-case time complexity o(nlogn). we demonstrate experimentally that our algorithm has stable performance compared with other approaches.
enumeration and generation with a string automata representation. the representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. in this work, we present a unique string representation for complete initially-connected deterministic automata (icdfas) with n states over an alphabet of k symbols. for these strings we give a regular expression and show how they are adequate for exact and random generation, allow an alternative way for enumeration and lead to an upper bound for the number of icdfas. the exact generation algorithm can be used to partition the set of icdfas in order to parallelize the counting of minimal automata, and thus of regular languages. a uniform random generator for icdfas is presented that uses a table of pre-calculated values. based on the same table, an optimal coding for icdfas is obtained.
an extension of the burrows-wheeler transform. we describe and highlight a generalization of the burrows-wheeler transform (bwt) to a multiset of words. the extended transformation, denoted by ebwt, is reversible. moreover, it allows to define a bijection between the words over a finite alphabet a and the finite multisets of conjugacy classes of primitive words in a^*. besides its mathematical interest, the extended transform can be useful for applications in the context of string processing. in the last part of this paper we illustrate one such application, providing a similarity measure between sequences based on ebwt.
pac-learnability of probabilistic deterministic finite state automata in terms of variation distance. we consider the problem of pac-learning distributions over strings, represented by probabilistic deterministic finite automata (pdfas). pdfas are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. recent work on learning pdfas from random examples has used the kl-divergence as the error measure; here we use the variation distance. we build on recent work by clark and thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.
a complete characterization of deterministic regular liveness properties. many systems can be modeled formally by nondeterministic buchi-automata. the complexity of model checking then essentially depends on deciding subset conditions on languages that are recognizable by these automata and that represent the system behavior and the desired properties of the system. the involved complementation process may lead to an exponential blow-up in the size of the automata. we investigate a rich subclass of properties, called deterministic regular liveness properties, for which complementation at most doubles the automaton size if the properties are represented by deterministic buchi-automata. in this paper, we will present a decomposition theorem for this language class that entails a complete characterization of the deterministic regular liveness properties, and extend an existing incomplete result which then, too, characterizes the deterministic regular liveness properties completely.
from first principles to the burrows and wheeler transform and beyond, via combinatorial optimization. we introduce a combinatorial optimization framework that naturally induces a class of optimal word permutations with respect to a suitably defined cost function taking into account various measures of relatedness between words. the burrows and wheeler transform (bwt) (cf. [m. burrows, d. wheeler, a block sorting lossless data compression algorithm, technical report 124, digital equipment corporation, 1994]), and its analog for labelled trees (cf. [p. ferragina, f. luccio, g. manzini, s. muthukrishnan, structuring labeled trees for optimal succinctness, and beyond, in: proc. of the 45th annual ieee symposium on foundations of computer science, 2005, pp. 198-207]), are special cases in the class. we also show that the class of optimal word permutations defined here is identical to the one identified by ferragina et al. for compression boosting [p. ferragina, r. giancarlo, g. manzini, m. sciortino, boosting textual compression in optimal linear time, journal of the acm 52 (2005) 688-713]. therefore, they are all highly compressible. we also provide, by using techniques from combinatorics on words, a fast method to compute bwt without using any end-of-string symbol. we also investigate more general classes of optimal word permutations, where relatedness of symbols may be measured by functions more complex than context length. for this general problem we provide an instance that is max-snp hard, and therefore unlikely to be solved or approximated efficiently. the results presented here indicate that a key feature of the burrows and wheeler transform seems to be, besides compressibility, the existence of efficient algorithms for its computation and inversion.
on the average state and transition complexity of finite languages. we investigate the average-case state and transition complexity of deterministic and nondeterministic finite automata, when choosing a finite language of a certain ''size'' n uniformly at random from all finite languages of that particular size. here size means that all words of the language are either of length n, or of length at most n. it is shown that almost all deterministic finite automata accepting finite languages over a binary input alphabet have state complexity @q(2^nn), while nondeterministic finite automata are shown to perform better, namely the nondeterministic state complexity is in @q(2^n). interestingly, in both cases the aforementioned bounds are asymptotically like in the worst case. however, the nondeterministic transition complexity is shown to be again @q(2^nn). the case of unary finite languages is also considered. moreover, we develop a framework that allows us to investigate the average-case complexity of operations like, e.g., union, intersection, complementation, and reversal, on finite languages in this setup.
on the number of components for some parallel communicating grammar systems. in natural languages, there occur phenomena like multiple agreements, crossed agreements and replication. these aspects are represented by the three languages k"1={a^nb^nc^n|n>=1}, k"2={a^nb^mc^nd^m|m,n>=1} and k"3={ww|w@?{a,b}^+}, respectively. these languages are of interest, when modeling natural languages. in the present paper, we give parallel communicating grammar systems (pc grammar systems) that generate the languages k"1, k"2 and k"3 but use less or less-powerful components than those used by systems published so far.