waashk/dblp huggingface dataset:
finite automata encoding geometric figures. finite automata are used for the encoding and compression of images. for black-and-white images, for instance, using the quad-tree representation, the black points correspond to @w-words defining the corresponding paths in the tree that lead to them. if the @w-language consisting of the set of all these words is accepted by a deterministic finite automaton then the image is said to be encodable as a finite automaton. for grey-level images and colour images similar representations by automata are in use. in this paper we address the question of which images can be encoded as finite automata with full infinite precision. in applications, of course, the image would be given and rendered at some finite resolution-this amounts to considering a set of finite prefixes of the @w-language-and the features in the image would be approximations of the features in the infinite precision rendering. we focus on the case of black-and-white images-geometrical figures, to be precise-but treat this case in a d-dimensional setting, where d is any positive integer. we show that among all polygons and convex polyhedra in d-dimensional space exactly those with rational corner points are encodable as finite automata. in the course of proving this we show that the set of images encodable as finite automata is closed under rational affine transformations. several properties of images encodable as finite automata are consequences of this result. finally we show that many simple geometric figures such as circles and parabolas are not encodable as finite automata.
enumeration and random generation of accessible automata. we present a bijection between the set a"n of deterministic and accessible automata with n states on a k-letters alphabet and some diagrams, which can themselves be represented as partitions of a set of kn+1 elements into n non-empty subsets. this combinatorial construction shows that the asymptotic order of the cardinality of a"n is related to the stirling number {knn}. our bijective approach also yields an efficient random sampler, for the uniform distribution, of automata with n states, its complexity is o(n^3^/^2), using the framework of boltzmann samplers.
non-unique probe selection and group testing. a minimization problem that has arisen from the study of non-unique probe selection with group testing technique is as follows: given a binary matrix, find a d-disjunct submatrix with the minimum number of rows and the same number of columns. we show that when every probe hybridizes to at most two viruses, i.e., every row contains at most two 1s, this minimization is still max snp-complete, but has a polynomial-time approximation with performance ratio 1+2/(d+1). this approximation is constructed based on an interesting result that the above minimization is polynomial-time solvable when every probe hybridizes to exactly two viruses.
on the spanning connectivity and spanning laceability of hypercube-like networks. let u and v be any two distinct nodes of an undirected graph g, which is k-connected. for 1@?w@?k, a w-containerc(u,v) of a k-connected graph g is a set of w-disjoint paths joining u and v. a w-container c(u,v) of g is a w^*-container if it contains all the nodes of g. a graph g is w^*-connected if there exists a w^*-container between any two distinct nodes. a bipartite graph g is w^*-laceable if there exists a w^*-container between any two nodes from different parts of g. let g"0=(v"0,e"0) and g"1=(v"1,e"1) be two disjoint graphs with |v"0|=|v"1|. let e={(v,@f(v))|v@?v"0,@f(v)@?v"1, and @f:v"0->v"1 is a bijection}. let g=g"0@?g"1=(v"0@?v"1,e"0@?e"1@?e). the set of n-dimensional hypercube-like graph h"n^' is defined recursively as (a) h"1^'={k"2}, k"2= complete graph with two nodes, and (b) if g"0 and g"1 are in h"n^', then g=g"0@?g"1 is in h"n"+"1^'. let b"n^'={g@?h"n^' and g is bipartite} and n"n^'=h"n^'@?b"n^'. in this paper, we show that every graph in b"n^' is w^*-laceable for every w, 1@?w@?n. it is shown that a constructed n"n^'-graph h can not be 4^*-connected. in addition, we show that every graph in n"n^' is w^*-connected for every w, 1@?w@?3.
the increase of the instability of networks due to quasi-static link capacities. in this work, we study the impact of the dynamic changing of the network link capacities on the stability properties of packet-switched networks. especially, we consider the adversarial, quasi-static queuing theory model, where each link capacity may take on only two possible (integer) values, namely 1 and c>1 under a (w,@r)-adversary. we obtain the following results: *allowing such dynamic changes to the link capacities of a network with just ten nodes that uses the lis (longest-in-system) protocol for contention-resolution results in instability at rates @r>2-1 and for large enough values of c. *the combination of dynamically changing link capacities with compositions of contention-resolution protocols on network queues suffices for similar instability bounds: the composition of lis with any of sis (shortest-in-system), nts (nearest-to-source), and ftg (furthest-to-go) protocols is unstable at rates @r>2-1 for large enough values of c. *the instability bound of the network subgraphs that are forbidden for stability is affected by the dynamic changes to the link capacities: we present improved instability bounds for all the directed subgraphs that were known to be forbidden for stability on networks running a certain greedy protocol.
bicriteria scheduling on a batching machine to minimize maximum lateness and makespan. this paper studies the bicriteria problem of scheduling n jobs on a batching machine to minimize maximum lateness and makespan simultaneously. a parallel-batching machine is a machine that can handle up to b jobs in a batch. the jobs in a batch start and complete at the same time, respectively, and the processing time of a batch is equal to the largest processing time of jobs in the batch. we analyse the unbounded model, where b>=n. we present a polynomial-time algorithm for finding all pareto optimal solutions of this bicriteria scheduling problem.
some approximation algorithms for the clique partition problem in weighted interval graphs. interval graphs play important roles in analysis of dna chains in benzer [s. benzer, on the topology of the genetic fine structure, proceedings of the national academy of sciences of the united states of america 45 (1959) 1607-1620], restriction maps of dna in waterman and griggs [m.s. waterman, j.r. griggs, interval graphs and maps of dna, bulletin of mathematical biology 48 (2) (1986) 189-195] and other related areas. in this paper, we study a new combinatorial optimization problem, named the minimum clique partition problem with constrained bounds, in weighted interval graphs. for a weighted interval graph g and a bound b, partition the weighted intervals of this graph g into the smallest number of cliques, such that each clique, consisting of some intervals whose intersection on a real line is not empty, has its weight not beyond b. we obtain the following results: (1) this problem is np-hard in a strong sense, and it cannot be approximated within a factor 32-@e in polynomial time for any @e>0; (2) we design three approximation algorithms with different constant factors for this problem; (3) for the version where all intervals have the same weights, we design an optimal algorithm to solve the problem in linear time.
the linear arboricity of planar graphs with no short cycles. the linear arboricity of a graph g is the minimum number of linear forests which partition the edges of g. akiyama, exoo and harary conjectured that @?@d(g)2@?@?la(g)@?@?@d(g)+12@? for any simple graph g. in the paper, it is proved that if g is a planar graph with @d>=7 and without i-cycles for some i@?{4,5}, then la(g)=@?@d(g)2@?.
efficient algorithms for generalized stable marriage and roommates problems. we consider a generalization of the stable roommates problem (sr), in which preference lists may be partially ordered and forbidden pairs may be present, denoted by srpf. this includes, as a special case, a corresponding generalization of the classical stable marriage problem (sm), denoted by smpf. by extending previous work of feder, we give a two-step reduction from srpf to 2-sat. this has many consequences, including fast algorithms for a range of problems associated with finding ''optimal'' stable matchings and listing all solutions, given variants of sr and sm. for example, given an smpf instance i, we show that there exists an o(m) ''succinct'' certificate for the unsolvability of i, an o(m) algorithm for finding all the super-stable pairs in i, an o(m+kn) algorithm for listing all the super-stable matchings in i, an o(m^1^.^5) algorithm for finding an egalitarian super-stable matching in i, and an o(m) algorithm for finding a minimum regret super-stable matching in i, where n is the number of men, m is the total length of the preference lists, and k is the number of super-stable matchings in i. analogous results apply in the case of srpf.
bounds on the bisection width for random d -regular graphs. in this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the bisection width of random d-regular graphs, for any value of d. the upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find bisections of d-regular graphs. we provide bounds for 5&le;d&le;12. we also give empirical values of the size of the bisection found by the algorithm for some small values of d and compare them with numerical approximations of our theoretical bounds. our analysis also gives asymptotic lower bounds for the size of the maximum bisection.
model checking mobile stochastic logic. the temporal mobile stochastic logic (mosl) has been introduced in previous work by the authors for formulating properties of systems specified in stoklaim, a markovian extension of klaim. the main purpose of mosl is to address key functional aspects of global computing such as distribution awareness, mobility, and security and their integration with performance and dependability guarantees. in this paper, we present mosl^+, an extension of mosl, which incorporates some basic features of the modal logic for mobility (momo), a logic specifically designed for dealing with resource management and mobility aspects of concurrent behaviours. we also show how mosl^+ formulae can be model-checked against stoklaim specifications. for this purpose, we show how existing state-based stochastic model-checkers, like e.g. the markov reward model checker (mrmc), can be exploited by using a front-end for stoklaim that performs appropriate pre-processing of mosl^+ formulae. the proposed approach is illustrated by modelling and verifying a sample system.
complexity of the bisection method. the bisection method is the consecutive bisection of a triangle by the median of the longest side. in this paper we prove a subexponential asymptotic upper bound for the number of similarity classes of triangles generated on a mesh obtained by iterative bisection, which previously was known only to be finite. the relevant parameter is &gamma;/&sigma;, where &gamma; is the biggest and &sigma; is the smallest angle of the triangle. we get this result by introducing a taxonomy of triangles that precisely captures the behaviour of the bisection method. we also prove that the number of directions on the plane given by the sides of the triangles generated is finite. additionally, we give purely geometrical and intuitive proofs of classical results for the bisection method.
on dejean's conjecture over large alphabets. the (maximal) exponent of a non-empty finite word is the ratio of its length to its period. dejean (1972) conjectured that for any n≥5 there exists an infinite word over n letters with no factor of its exponent larger than n/(n-1). we prove that this conjecture is true for n≥33.
mixing logics and rewards for the component-oriented specification of performance measures. formal notations for system performance modeling need to be equipped with suitable notations for specifying performance measures. these companion notations have been traditionally based on reward structures and, more recently, on temporal logics. in this paper we propose an approach that combines logics and rewards, together with a definition mechanism that allows performance measures to be specified in a component-oriented way, thus facilitating the task for non-experts. the resulting measure specification language (msl) is interpreted both on action-labeled continuous-time markov chains and on stochastic process algebras. the latter interpretation provides a compositional framework for performance-sensitive model manipulations and emphasizes the increased expressiveness with respect to traditional reward structures for implicit-state modeling notations.
csl model checking algorithms for qbds. we present an in-depth treatment of model checking algorithms for a class of infinite-state continuous-time markov chains known as quasi-birth death processes. the model class is described in detail, as well as the logic csl to express properties of interest. using a new property-independency concept, we provide model checking algorithms for all the csl operators. special emphasis is given to the time-bounded until operator for which we present a new and efficient computational procedure named uniformization with representatives. by the use of an application-driven dynamic stopping criterion, the algorithm stops whenever the property to be checked can be certified (or falsified). a comprehensive case study of a connection management system shows the versatility of our new algorithms.
learning intersection-closed classes with signatures. intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. in this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. we give a learning algorithm in the exact model with equivalence queries for such classes. this algorithm utilizes a novel encoding scheme, which we call a signature.
learning tree languages from positive examples and membership queries. we investigate regular tree languages' exact learning from positive examples and membership queries. input data are trees of the language to infer. the learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. from the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. this paradigm was introduced by angluin in the seminal work [d. angluin, a note on the number of queries needed to identify regular languages, information and control 51 (1981) 76-87] for the case of regular word languages. neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm. we describe an efficient algorithm which is polynomial in the size of the examples for learning the whole class of regular tree languages. the convergence is ensured when the set of examples contains a representative sample of the language to guess. a finite subset of a regular tree language is representative for if every transition of the minimal tree automaton for is used at least once for the derivation of an element of the set .
on the complexity of working set selection. the decomposition method is currently one of the major methods for solving the convex quadratic optimization problems being associated with support vector machines (svm-optimization). a key issue in this approach is the policy for working set selection. we would like to find policies that realize (as well as possible) three goals simultaneously: ''(fast) convergence to an optimal solution'', ''efficient procedures for working set selection'', and ''a high degree of generality'' (including typical variants of svm-optimization as special cases). in this paper, we study a general policy for working set selection that has been proposed in [nikolas list, hans ulrich simon, a general convergence theorem for the decomposition method, in: proceedings of the 17th annual conference on computational learning theory, 2004, pp. 363-377] and further analyzed in [nikolas list, hans ulrich simon, general polynomial time decomposition algorithms, in: proceedings of the 17th annual conference on computational learning theory, 2005, pp. 308-322]. it is known that it efficiently approaches feasible solutions with minimum cost for any convex quadratic optimization problem. here, we investigate its computational complexity when it is used for svm-optimization. it turns out that, for a variable size of the working set, the general policy poses an np-hard working set selection problem. but a slight variation of it (sharing the convergence properties with the original policy) can be solved in polynomial time. for working sets of fixed size 2, the situation is even better. in this case, the general policy coincides with the ''rate certifying pair approach'' (introduced by hush and scovel). we show that maximum rate certifying pairs can be found in linear time, which leads to a quite efficient decomposition method with a polynomial convergence rate for svm-optimization.
formalization of the standard uniform random variable. continuous random variables are widely used to mathematically describe random phenomena in engineering and the physical sciences. in this paper, we present a higher-order logic formalization of the standard uniform random variable as the limit value of the sequence of its discrete approximations. we then show the correctness of this specification by proving the corresponding probability distribution properties within the hol theorem prover, summarizing the proof steps. the formalized standard uniform random variable can be transformed to formalize other continuous random variables, such as uniform, exponential, normal, etc., by using various non-uniform random number generation techniques. the formalization of these continuous random variables will enable us to perform an error free probabilistic analysis of systems within the framework of a higher-order-logic (hol) theorem prover. for illustration purposes, we present the formalization of the continuous uniform random variable based on the formalized standard uniform random variable, and then utilize it to perform a simple probabilistic analysis of roundoff error in hol.
complexity of pattern classes and the lipschitz property. rademacher and gaussian complexities are successfully used in learning theory for measuring the capacity of the class of functions to be learnt. one of the most important properties for these complexities is their lipschitz property: a composition of a class of functions with a fixed lipschitz function may increase its complexity by at most twice the lipschitz constant. the proof of this property is non-trivial (in contrast to the case for the other properties) and it is believed that the proof in the gaussian case is conceptually more difficult than the one for the rademacher case. in this paper we give a detailed proof of the lipschitz property for the general case of a symmetric complexity measure that includes the rademacher and gaussian complexities as special cases. we also consider the rademacher complexity of a function class consisting of all the lipschitz functions with a given lipschitz constant. we show that the complexity of the class is surprisingly low in the one-dimensional case. finally, we introduce a relaxation of the definition of rademacher complexity to rademacher free complexity and show that not only can this complexity replace the standard definition in the key theorem, but also the bounds for composed function classes are tighter.
approximation schemes for a class of subset selection problems. in this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. special cases that are covered by our result show up in many places in the literature. for every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. we demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. as a special case, we derive the existence of an fptas for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. the approximability status of this problem has been open for some time.
revising threshold functions. a revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. such an algorithm is considered efficient if its complexity (in terms of the resource one is interested in) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. we give an efficient revision algorithm in the model of learning with equivalence and membership queries for threshold functions, and some negative results showing, for instance, that threshold functions cannot be revised efficiently from either type of query alone. the algorithms work in a general revision model where both deletion and addition type revision operators are allowed.
on the data consumption benefits of accepting increased uncertainty. in the context of learning paradigms of identification in the limit, we address the question: why is uncertainty sometimes desirable? we use mind change bounds on the output hypotheses as a measure of uncertainty and interpret 'desirable' as reduction in data memorization, also defined in terms of mind change bounds. the resulting model is closely related to iterative learning with bounded mind change complexity, but the dual use of mind change bounds - for hypotheses and for data - is a key distinctive feature of our approach. we show that situations exist where the more mind changes the learner is willing to accept, the less the amount of data it needs to remember in order to converge to the correct hypothesis. we also investigate relationships between our model and learning from good examples, set-driven, monotonic and strong-monotonic learners, as well as class-comprising versus class-preserving learnability.
on the (im)possibility of non-interactive correlation distillation. we study the problem of non-interactive correlation distillation (nicd). suppose that alice and bob each have a string, denoted by a=a0a1&hellip;an-1 and b=b0b1&hellip;bn-1, respectively. furthermore, for every k=0,1,&hellip;,n-1, (ak,bk) is drawn independently from a distribution , known as the 'noise model'. alice and bob wish to 'distill' the correlation non-interactively, i.e., they wish to each apply a function to their strings, and output one random bit, denoted by x and y, such that pr[x=y] can be made as close to 1 as possible. the problem is, for what noise models can they succeed? this problem is related to various topics in computer science, including information reconciliation and random beacons. in fact, if nicd is indeed possible for some general class of noise models, then some of these topics would, in some sense, become straightforward corollaries. we prove two negative results on nicd for various noise models. we prove that, for these models, it is impossible to distill the correlation to be arbitrarily close to 1. we also give an example where alice and bob can increase their correlation with one bit of communication (in this case they need to each output two bits). this example, which may be of interest on its own, demonstrates that even the smallest amount of communication is provably more powerful than no communication.