waashk/dblp huggingface dataset:
comparing notions of randomness. it is an open problem in the area of effective (algorithmic) randomness whether kolmogorov-loveland randomness coincides with martin-lof randomness. joe miller and andre nies suggested some variations of kolmogorov-loveland randomness to approach this problem and to provide a partial solution. we show that their proposed notion of injective randomness is still weaker than martin-lof randomness. since in this proof some of the ideas we use are clearer, we also show the weaker theorem that permutation randomness is weaker than martin-lof randomness.
a graph theoretic approach to general euler diagram drawing. euler diagrams are used in a wide variety of areas for representing information about relationships between collections of objects. recently, several techniques for automated euler diagram drawing have been proposed, contributing to the euler diagram generation problem: given an abstract description, draw an euler diagram with that description and which possesses certain properties, sometimes called well-formedness conditions. we present the first fully formalized, general framework that permits the embedding of euler diagrams that possess any collection of the six typically considered well-formedness conditions. our method first converts the abstract description into a vertex-labelled graph. an euler diagram can then be formed, essentially by finding a dual graph of such a graph. however, we cannot use an arbitrary plane embedding of the vertex-labelled graph for this purpose. we identify specific embeddings that allow the construction of appropriate duals. from these embeddings, we can also identify precisely which properties the drawn euler diagram will possess and 'measure' the number of times that each well-formedness condition is broken. we prove that every abstract description can be embedded using our method. moreover, we identify exactly which (large) class of euler diagrams can be generated.
theory of one-tape linear-time turing machines. a theory of one-tape two-way one-head off-line linear-time turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. this paper discusses structural-complexity issues of one-tape turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. we explore structural properties of one-tape linear-time turing machines and clarify how the machines' resources affect their computational patterns and power.
maximizing the minimum load for selfish agents. we consider the problem of maximizing the minimum load (completion time) for machines that are controlled by selfish agents, who are only interested in maximizing their own profit. unlike the classical load balancing problem, this problem has not been considered for selfish agents until now. the goal is to design a truthful mechanism, i.e., one in which all users have an incentive to tell the truth about the speeds of their machines. this then allows us to find good job assignments. it is known that this requires monotone approximation algorithms, in which the amount of work assigned to an agent does not increase if its bid (claimed cost per unit work) increases. for a constant number of machines, m, we show a monotone polynomial-time approximation scheme (ptas) with running time that is linear in the number of jobs. it uses a new technique for reducing the number of jobs while remaining close to the optimal solution. we use an fptas for the classical problem, i.e., where no selfish agents are involved, to give a monotone fptas. additionally, we give a monotone approximation algorithm with approximation ratio min(m,(2+@e)s"1/s"m) where @e>0 can be chosen arbitrarily small and s"i is the (real) speed of machine i. finally we give improved results for two machines.
compositions of maximal codes. the proposition ''for composable thin codes y and z, the composition y@?z is maximal if and only if y and z are maximal'' put forward by j. berstel and d. perrin in their book ''theory of codes'' is well known. is the proposition also true without the assumption that y and z are thin? we give an example showing that the answer is negative. furthermore, several generalizations of the above proposition are also given.
on a special class of primitive words. when representing dna molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its watson-crick complement @q(u), where @q denotes the watson-crick complementarity function. thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. in this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to @q or simply @q-primitive words, which cannot be expressed as such repeating sequences. for instance, we prove the existence of a unique @q-primitive root of a given word, and we give some constraints forcing two distinct words to share their @q-primitive root. also, we present an extension of the well-known fine and wilf theorem, for which we give an optimal bound.
cps-translation as adjoint. we show that there exist translations between polymorphic @l-calculus and a subsystem of minimal logic with existential types, which form a galois insertion (embedding). the translation from polymorphic @l-calculus into the existential type system is the so-called call-by-name cps-translation that can be expounded as an adjoint from the neat connection. the construction of an inverse translation is investigated from a viewpoint of residuated mappings. the duality appears not only in the reduction relations but also in the proof structures, such as paths between the source and the target calculi. from a programming point of view, this result means that abstract data types can interpret polymorphic functions under the cps-translation. we may regard abstract data types as a dual notion of polymorphic functions.
a mezei-wright theorem for categorical algebras. the main result of this paper is a generalization of the mezei-wright theorem, a result on solutions of a system of fixed point equations. in the typical setting, one solves a system of fixed point equations in an algebra equipped with a suitable partial order; there is a least element, suprema of @w-chains exist, the operations preserve the ordering and least upper bounds of @w-chains. in this setting, one solution of this kind of system is provided by least fixed points. the mezei-wright theorem asserts that such a solution is preserved by a continuous, order preserving algebra homomorphism. in several settings such as (countable) words or synchronization trees there is no well-defined partial order but one can naturally introduce a category by considering morphisms between the elements. the generalization of this paper consists in replacing ordered algebras by ''categorical algebras''; the least element is replaced by an initial element, and suprema of @w-chains are replaced by colimits of @w-diagrams. then the mezei-wright theorem for categorical algebras is that initial solutions are preserved by continuous morphisms. we establish this result for initial solutions of parametric fixed point equations. one use of the theorem is to characterize an ''algebraic'' element as one that can arise as a solution of some system of fixed point equations. in familiar examples, an algebraic element is one that is context-free, regular or rational. then, if h:a->b is a continuous morphism of categorical algebras, the algebraic objects in b are those isomorphic to h-images of algebraic objects in a.
on the computational power of blenx. we present some decidability and undecidability results for subsets of the blenx language, a process-calculi-based programming language developed for modelling biological processes. we show that for a core subset of the language (which considers only communication primitives) termination is decidable. moreover, we prove that by adding either global priorities or events to this core language, we obtain turing equivalent languages. the proof is through encodings of random access machines (rams), a well-known turing equivalent formalism, into our subsets of blenx. all the encodings are shown to be correct.
peek arc consistency. this paper studies peek arc consistency, a reasoning technique that extends the well-known arc consistency technique for constraint satisfaction. in contrast to other more costly extensions of arc consistency that have been studied in the literature, peek arc consistency requires only linear space and quadratic time and can be parallelized in a straightforward way such that it runs in linear time with a linear number of processors. we demonstrate that for various constraint languages, peek arc consistency gives a polynomial-time decision procedure for the constraint satisfaction problem. we also present an algebraic characterization of those constraint languages that can be solved by peek arc consistency, and study the robustness of the algorithm.
complexity and succinctness issues for linear-time hybrid logics. full linear-time hybrid logic (hl) is a non-elementary and equally expressive extension of standard ltl + past obtained by adding the well-known binder operators @7 and @?. we investigate complexity and succinctness issues for hl in terms of the number of variables and nesting depth of binder modalities. first, we present direct automata-theoretic decision procedures for satisfiability and model-checking of hl, which require space of exponential height equal to the nesting depth of the binder modalities. the proposed algorithms are proved to be asymptotically optimal by providing matching lower bounds. second, we show that, for the one-variable fragment of hl, the considered problems are elementary and, precisely, expspace-complete. finally, we show that, for all 0@?h
factorization forests for infinite words and applications to countable scattered linear orderings. the theorem of factorization forests of imre simon shows the existence of nested factorizations-a la ramsey-for finite words. this theorem has important applications in semigroup theory, and beyond. we provide two improvements to the standard result. first we improve on all previously known bounds. second, we extend it to 'every linear ordering'. we use this last variant in a simplified proof of the translation of recognizable languages over countable scattered linear orderings to languages accepted by automata.
complexity issues in color-preserving graph embeddings. in the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein-protein interaction graph (target graph) of another species with respect to (w.r.t.) orthologous proteins. we give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. for approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively.
some complexity results for prefix gröbner bases in free monoid rings. we establish the following complexity results for prefix grobner bases in free monoid rings: 1. |r|@?size(p) reduction steps are sufficient to normalize a given polynomial p w.r.t. a given right-normalized system r of prefix rules compatible with some total admissible well-founded ordering >. 2. o(|r|@?size(r)) basic steps are sufficient to transform a given terminating system r of prefix rules into an equivalent right-normalized system. 3. o(|r|^2@?size(r)) basic steps are sufficient to decide whether or not a given terminating system r of prefix rules is a prefix grobner basis. the latter result answers an open question posed by zeckzer (2000) [9].
extended strings and graphs for simple gene assembly. the simple intramolecular model for gene assembly in ciliates is particularly interesting because it can predict the correct assembly of all available experimental data, although it is not universal. the simple model also has a confluence property that is not shared by the general model. a previous formalization of the simple model through sorting of signed permutations is unsatisfactory because it effectively ignores one operation of the model and thus, it cannot be used to answer questions about parallelism in the model, or about measures of complexity. we propose in this paper a string-based model in which a gene is represented through its sequence of pointers and markers and its assembly is represented as a string rewriting process. we prove that this string-based model is equivalent to the permutation-based model as far as gene assembly is concerned, while it tracks all operations of the simple model. we also consider overlap graphs for these strings and prove the results with respect to the overlap of markers.
on notions of regularity for data languages. with motivation from considerations in xml database theory and model checking, data strings have been introduced as an extension of finite alphabet strings which carry, at each position, a symbol and a data value from an infinite domain. previous work has shown that it is difficult to come up with an expressive yet decidable automaton model for data languages. recently, such a model, data automata, was introduced. this paper introduces a simpler but equivalent model and investigates its expressive power, algorithmic and closure properties, and some extensions.
on blockwise symmetric signatures for matchgates. we give a classification of blockwise symmetric signatures in the theory of matchgate computations. the main proof technique uses matchgate identities, also known as useful grassmann-plucker identities.
real-time reversible iterative arrays. iterative arrays are one-dimensional arrays of interconnected interacting finite automata. the cell at the origin is equipped with a one-way read-only input tape. we investigate iterative arrays as acceptors for formal languages. in particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. this property is called real-time reversibility. it is shown that real-time reversible iterative arrays can simulate restricted variants of stacks and queues. it turns out that real-time reversible iterative arrays are strictly weaker than real-time reversible cellular automata. on the other hand, a non-semilinear language is accepted. we show that real-time reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts with the general case, where reversibility is decidable for one-dimensional devices. moreover, we prove the non-semidecidability of several other properties. several closure properties are also derived.
productivity of stream definitions. we give an algorithm for deciding productivity of a large and natural class of recursive stream definitions. a stream definition is called 'productive' if it can be evaluated continually in such a way that a uniquely determined stream in constructor normal form is obtained as the limit. whereas productivity is undecidable for stream definitions in general, we show that it can be decided for 'pure' stream definitions. for every pure stream definition the process of its evaluation can be modelled by the dataflow of abstract stream elements, called 'pebbles', in a finite 'pebbleflow net(work)'. and the production of a pebbleflow net associated with a pure stream definition, that is, the amount of pebbles the net is able to produce at its output port, can be calculated by reducing nets to trivial nets.
on the complexity of kings. a king in a directed graph is a vertex from which each vertex in the graph can be reached through paths of length at most two. there is a broad literature on tournaments (completely oriented digraphs), and it has been known for more than half a century that all tournaments have at least one king. recently, kings have proven useful in theoretical computer science, in particular in the study of the complexity of reachability problems and semifeasible sets. in this article, we study the complexity of recognizing kings. for each succinctly specified family of tournaments, the king problem is already known to belong to @p"2^p. we prove that the complexity of kingship problems is a rich enough vocabulary to pinpoint every nontrivial many-one degree in @p"2^p. that is, we show that every set in @p"2^p other than 0@? and @s^* is equivalent to a king problem under @?"m^p-reductions. indeed, we show that the equivalence can even be realized by relatively simple padding, and holds even if the notion of kings is redefined to refer to k-kings (for any fixed k>=2)-vertices from which all vertices can be reached through paths of length at most k. in contrast, we prove that for each succinctly specified family of tournaments the source problem (the problem of deciding whether a given vertex v has the property that there exists a k such that v is a k-king) also falls within @p"2^p, yet cannot be @p"2^p-complete-or even np-hard-unless p=np. using these and related techniques, we obtain a broad range of additional results about the complexity of king problems, diameter problems, and radius problems. it follows easily from our proof approach that the problem of testing kingship in succinctly specified graphs (which need not be tournaments) is @p"2^p-complete. we show that the radius problem for arbitrary succinctly represented graphs is @s"3^p-complete, but that in contrast the diameter problem for arbitrary succinctly represented graphs (or even tournaments) is @p"2^p-complete.
notions of hyperbolicity in monoids. we introduce a notion of hyperbolicity in monoids which is a restriction of that suggested by duncan and gilman. one advantage is that the notion gives rise to efficient algorithms for dealing with certain questions; for example, the word problem can be solved in time o(nlogn). we also introduce a new way of defining automatic monoids which provides a uniform framework for the discussion of these concepts. hyperbolic monoids (in the sense introduced here) turn out to be biautomatic.
recent developments in computer vision, second asian conference on computer vision, accv '95, singapore, december 5-8, 1995, invited session papers in this paper, we propose a new edge-based text verification approach for video. based on the investigation of the relation between candidate blocks and their neighbor areas, the proposed approach first detects background edges in candidate blocks, then erases them by an edge tracking technique, and finally the candidate blocks containing too few remaining edges are eliminated as false alarms. three measures for text detection evaluation in video were used to assess the performance of the proposed text verification approach. experimental results on 50 broadcast news video clips demonstrate the validity of our approach.
computer vision - accv'98, third asian conference on computer vision, hong kong, china, january 8-10, 1998, proceedings, volume i in this paper, we analyze the problem of network disconnection in the context of large-scale p2p networks and understand how both static and dynamic patterns of node failure affect the resilience of such graphs. we start by applying classical results from random graph theory to show that a large variety of deterministic and random p2p graphs almost surely (i.e., with probability 1-o(1)) remain connected under random failure if and only if they have no isolated nodes. this simple, yet powerful, result subsequently allows us to derive in closed-form the probability that a p2p network develops isolated nodes, and therefore partitions, under both types of node failure. we finish the paper by demonstrating that our models match simulations very well and that dynamic p2p systems are extremely resilient under node churn as long as the neighbor replacement delay is much smaller than the average user lifetime.
computer vision - accv'98, third asian conference on computer vision, hong kong, china, january 8-10, 1998, proceedings, volume ii this paper proposes an enhanced rvlc coder, context-adaptive reversible variable length coder (crvlc), for dct coefficients by using the techniques of data sub-partitioning and context modeling. the data sub-partitioning means that the data part of dct coefficients is split into several small sub-partitions. as each sub-partition can be reversibly decoded by rvlc, more data as well as higher error resilience can be obtained. the context modeling exploits the correlation of dct coefficients for further compression. this modeling defines the contexts by hierarchical-dependent information. the information is also available in the backward decoding, so that it supports the reversible decoding. and with it the data outputted by crvlc can be naturally placed into multiple sub-partitions.
computer vision - accv 2006, 7th asian conference on computer vision, hyderabad, india, january 13-16, 2006, proceedings, part i in this paper, a low-complexity 8times8/4times4 adaptive block-size transform (abt) scheme is tentatively proposed for the chinese audio and video coding standard (avs). in the proposed abt scheme, an integer 8times8 transform is derived from the integer 4times4 transform used in avs according to a transform extension principle. the 8times8 transform not only has high energy compacted property but also can be merely implemented within several additions and shifts, and all intermediate results are limited with 16-bit. the 8times8 transform and 4times4 transform can be merged together and share the same scale matrix so that the hardware units and storage resources are efficiently saved for both encoder and decoder. the experimental results on numerous sequences show that the proposed abt scheme can achieve significant performance improvement for avs
computer vision - accv 2006, 7th asian conference on computer vision, hyderabad, india, january 13-16, 2006, proceedings, part ii in this paper, a new threshold correction method for document image binarization that is forcused on ruled-line extraction is presented. this method enhances the binary image of a ruled line, which is often adversely influenced by adjacent text pixels or background noise. the threshold correction method consists of two submethods. one is a noise reduction method that is based on background determination, and the other is a threshold surface conversion method. both these methods use the aspect of local straightness feature to distinguish ruled-line pixels from background pixels.
computer vision - accv 2007, 8th asian conference on computer vision, tokyo, japan, november 18-22, 2007, proceedings, part i visual tracking could be formulated as a state estimation problem of target representation based on observations in image sequences. approaching visual tracking problem in the bayesian filter framework, how to sample the state evolution model to generate hypothesis of high confidence level is a critical factor. in this paper, we introduce an interacting multiple model estimation (imme) framework for adaptive visual tracking. the essence of the imme framework is that the state is estimated by integrating several different models in parallel and by interacting among those models' estimates probabilistically. based on the imme framework, we propose a new variation of particle filter named interacting multiple model particle filter (immpf), in which the hypotheses can be sampled from several different state evolution models adaptively. experiments show that, when compared with the standard particle filter, the immpf generates better hypotheses resulting in better tracking results, especially when the target behaves along several motion modes randomly.