waashk/dblp huggingface dataset:
computational aspects of the 2-dimension of partially ordered sets. a well-known method to represent a partially ordered set p (order for short) consists in associating to each element of p a subset of a fixed set s = { 1,..., k} such that the order relation coincides with subset inclusion. such an embedding of p into 2s (the lattice of all subsets of s) is called a bit-vector encoding of p. these encodings provide an interesting way to store an order. they are economical with space and comparisons between elements can be performed efficiently via subset inclusion tests.given an order p, minimizing the size of the encoding, i.e. the cardinal of s, is however a difficult problem. the smallest size is called the 2-dimension of p and denoted by dim2(p). in the literature, the decision problem for the 2-dimension has been classified as np-complete and generating small bit-vector encodings is a challenging issue.several works deal with bit-vector encodings from a theoretical point of view in this article, we focus on computational complexity results. after a synthesis of known results, we come back on the np-completeness by detailing a proof and enforcing the conclusion with non-approximability ratios. besides this general result, we investigate the complexity of the 2-dimension for the class of trees. we describe a 4-approximation algorithm for this class. it uses an optimal balancing strategy which solves a conjecture of krall, vitek and horspool. several interesting open problems are listed.
periodicity in one-dimensional peg duotaire. we consider the single-hop version of one-dimensional peg duotaire, a two player version of peg solitaire in which players move alternatively and the last player to move wins. we determine the nim-values of all positions consisting of two sets of consecutive pegs separated by a hole. we show that two classes of positions produce periodic sequences of nim-values, and we conjecture that two other classes exhibit similar periodicity.
speeding up the detection of evolutive tandem repeats. we recently introduced evolutive tandem repeats with jump (using hamming distance) (proc. mfcs'02: the 27th internat. symp. mathematical foundations of computer science, warszawa, otwock, poland, august 2002, lecture notes in computer science, vol. 2420, springer, berlin, pp. 292-304) which consist in a series of almost contiguous copies having the following property: the hamming distance between two consecutive copies is always smaller than a given parameter e. in this article, we present a significative improvement that speeds up the detection of evolutive tandem repeats. it is based on the progressive computation of distances between candidate copies participating to the evolutive tandem repeat. it leads to a new algorithm, still quadratic in the worst case, but much more efficient on average, authorizing larger sequences to be processed.
a categorical model for the geometry of interaction. we consider the multiplicative and exponential fragment of linear logic (mell) and give a geometry of interaction (goi) semantics for it based on unique decomposition categories. we prove a soundness and finiteness theorem for this interpretation. we show that girard's original approach to goi 1 via operator algebras is exactly captured in this categorical framework.
bisimulation relations for dynamical, control, and hybrid systems. the fundamental notion of bisimulation equivalence for concurrent processes, has escaped the world of continuous, and subsequently, hybrid systems. inspired by the categorical framework of joyal, nielsen and winskel, we develop novel notions of bisimulation equivalence for dynamical systems as well as control systems. we prove that these notions can be captured by the abstract notion of bisimulation as developed by joyal, nielsen and winskel. this is the first unified notion of system equivalence that transcends discrete and continuous systems. furthermore, this enables the development of a novel and natural notion of bisimulation for hybrid systems, which is the final goal of this paper.
routing algorithm for multicast under multi-tree model in optical networks. to establish a multicast connection in a wavelength routed optical network, two steps are needed under the multi-tree model. one is to construct a set of light-trees rooted at the source node such that in each of them at most a specified number of destination nodes are allowed to receive the data and every destination node must be designated in one of them to receive the data. the other is to assign a wavelength to each of the produced light-trees in such a way that two light-trees must be assigned two distinct wavelengths if they use a common link. in this paper we mainly study how to construct a multicast routing of minimal cost under the multitree model in optical networks, where the routing cost is total costs of the produced light-trees. we propose a 4-approximation algorithm for this np-hard problem.
approximability results for stable marriage problems with ties. we consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. we show that, in such a setting, strong lower bounds hold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. we also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. in this setting, we prove that there are constants δ, δ' such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of δ, δ' (respectively) is np-hard, under strong restrictions. we also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. this significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. our results have applications to large-scale centralized matching schemes.
complexity analysis of the sat engine: dna algorithms as probabilistic algorithms. taking advantage of the power of dna molecules to spontaneously form hairpin structures, sakamoto et al. designed a molecular algorithm to solve instances of the satisfiability problem on boolean expressions in clausal form (the sat problem), and by developing new experimental techniques for molecular biology, they succeeded in solving a 6-variable, 10-clause instance of the 3-sat problem (sakamoto et al., science 288 (2000) 1223). sakamoto et al. call this computational architecture the sat engine. in this paper, we analyze the complexity of the sat engine as a probabilistic algorithm. we first estimate the time dependence of the probability of hairpin formation using standard chemical kinetics and the jacobson-stockmayer expression. we then estimate the number of dna molecules required to solve the satisfiability problem with a given error probability. by taking the number of dna molecules into account, we finally estimate the minimum total time and number of strands, respectively, required to achieve combined error rates of < ε1 (the probability of a false positive) and ε2 (the probability of a false negative). if the number of clauses is n, then the time required for solving the problem is proportional to n1.5(ln(1/ε1)+ln(ln(1/ε2)))+n2.5 ln(3+α),and the number of necessary dna molecules is proportional to (3 + α)n ln(1/ε2) with arbitrarily small α > 0.
algebraic aspects of emission tomography with absorption. in a previous paper the authors analysed the classical discrete tomography problem to construct a 0-1-matrix with given line sums in some given directions. one of the physical representations is that material at the lattice points corresponding to 1's emit units of radiation and that the radiation is measured along the given lines. in the present paper they extend their approach to the case that the intermediate material is absorbing the radiation. they generalise results obtained by kuba and nivat.
formal logics of discovery and hypothesis formation by machine. the following are the aims of the paper: (1) to call the attention of the community of discovery science (ds) to certain existing formal systems for ds developed in prague in the 1960s through the 1980s suitable for ds and unfortunately largely unknown. (2) to illustrate the use of the calculi in question by the example of the guha method of hypothesis generation by computer, subjecting this method to a critical evaluation in the context of contemporary data mining. (3) to stress the importance of fuzzy logic for ds and to present the state of mathematical foundations of fuzzy logic. (4) finally, to present a running research program of developing calculi of symbolic fuzzy logic for ds and for a fuzzy guha method.
on the max-flow min-cut ratio for directed multicommodity flows. we present a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. in addition, this combinatorial problem has applications in improving the approximation factor of the greedy algorithm for the maximum edge disjoint path problem. more precisely, our upper bound improves the approximation factor for this problem to o(n3/4).
binary (generalized) post correspondence problem. we give a new proof for the decidability of the binary post correspondence problem (pcp) originally proved in 1982 by ehrenfeucht, karhumki and rozenberg. our proof is complete and somewhat shorter than the original proof although we use the same basic. copyright 2002 elsevier science b.v. all rights reserved.
on a problem of fagin concerning multivalued dependencies in relational databases. multivalued dependencies (mvds) are an important class of relational constraints that is fundamental to relational database design. reflexivity axiom, complementation rule, and pseudo-transitivity rule form a minimal set of inference rules for the implication of mvds. the complementation rule plays a distinctive role as it takes into account the underlying relation schema r which the mvds are defined on. the r-axiom 0 ↠--r is much weaker than the complementation rule, but is sufficient to form a minimal set of inference rules together with augmentation and pseudo-difference rule. fagin has asked whether it is possible to reduce the power of the complementation rule and drop the augmentation rule at the same time and still obtain a complete set. it was argued that there is a trade-off between complementation rule and augmentation rule, and one can only dispense with one of these rules at the same time. it is shown in this paper that an affirmative answer to fagin's problem can nevertheless be achieved. in fact, it is proven that r-axiom together with a weaker form of the reflexivity axiom, pseudo-transitivity rule and exactly one of union, intersection or difference rule form such desirable minimal sets. the positive solution to this problem gives further insight into the difference between the notions of functional and multivalued dependencies.
a new routing algorithm for multirate rearrangeable clos networks. in this paper, we study the problem of finding routing algorithms on the multirate rearrangeable clos networks which use as few number of middle-stage switches as possible. we propose a new routing algorithm called the "grouping algorithm". this is a simple algorithm which uses fewer middle-stage switches than all known strategies, given that the number of input-stage switches and output-stage switches are relatively small compared to the size of input and output switches. in particular, the grouping algorithm implies that m = 2n + [(n - 1)/2k] is a sufficient number of middle-stage switches for the symmetric three-stage clos network c(n, m, r) to be multirate rearrangeable, where k is any positive integer and r ≤ n/(2k - 1).
online independent sets. we study the online version of the independent set problem in graphs. the vertices of an input graph are given one by one along with their edges to previous vertices, and the task is to decide whether to add each given vertex to an independent set solution. the goal is to maximize the size of the independent set, relative to the size of the optimal independent set. since it is known that no online algorithm can attain competitive ratio better than n - 1, where n denotes the number of vertices, we study here relaxations where the algorithm can hedge its bets by maintaining multiple alternative solutions.we introduce two models. in the first model, the algorithm can maintain a multiple number (r(n)) of solutions (independent sets) and choose the largest one as the final solution. we show that the best competitive ratio for this model is θ(n/logn) when r(n) is a polynomial and θ(n) when r(n) is a constant. in the second more powerful model, the algorithm can copy intermediate solutions and extend the copied solutions in different ways. we obtain an upper bound o(n/logn) and a lower bound ω(n/log3n) for the best possible competitive ratio when r(n) is a polynomial. furthermore, we show a tight θ(n) bound when r(n) is a constant. lower bound results of this paper hold also for randomized online algorithms against an oblivious adversary.
deciding implication for functional dependencies in complex-value databases. modern applications increasingly require the storage of data beyond relational structure. the challenge of providing well-founded data models that can handle complex objects such as lists, sets, multisets, unions and references has not been met yet in a completely satisfactory way. the success of such data models will greatly depend on the existence of automated database design techniques that generalise achievements from relational databases. in this paper, we study the implication problem of functional dependencies (fds) in the presence of records, sets, multisets and lists. database schemata are defined as nested attributes, database instances as nested relations and fds are defined in terms of subattributes of the database schema. the expressiveness of fds deviates fundamentally from previous approaches in different data models including the nested relational data model and xml.the implication problem is to decide whether for an arbitrary database schema, and an arbitrary set σ ∪ {σ} of fds defined on that schema, every database instance that satisfies all fds in σ also satisfies σ. the difficulty in generalising the solution from the relational data model to the presence of sets and multisets is caused by the fact that the value on the join of subattributes is no longer determined by the values on the subattributes. based on the notion of a unit, we propose to decompose the database schema in such a way that the closure of a set of nested attributes can be computed on the components of the schema. the implementation of the algorithm is based on a representation theorem for brouwerian algebras. the main contribution is the proof that the algorithm works correctly and in polynomial-time in the size of the input. defining the size of the input is not trivial since the measure should both generalise the one that is used for relational databases and do justice to the presence of sets and multisets. our solution to the implication problem allows to solve other important problems that occur in database design. we present polynomial-time algorithms to determine non-redundant covers of sets of fds, and to decide whether a given set of subattributes forms a superkey.
graphs determined by polynomial invariants. many polynomials have been defined associated to graphs, like the characteristic, matchings, chromatic and tutte polynomials. besides their intrinsic interest, they encode useful combinatorial information about the given graph. it is natural then to ask to what extent any of these polynomials determines a graph and, in particular, whether one can find graphs that can be uniquely determined by a given polynomial. in this paper we survey known results in this area and, at the same time, we present some new results.
randomized approximation of the stable marriage problem. while the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. either variation is polynomially solvable, but it has recently been shown to be np-hard to find a maximum cardinality stable matching when both of the variations are allowed. it is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. in this paper, we give a randomized approximation algorithm randbrk and show that its expected approximation ratio is at most 10/7 (< 1.4286) for a restricted but still np-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. we also show that our analysis is nearly tight by giving a lower bound 32/23(≥ 1.3913) for randbrk. furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much.
axiomatisations of functional dependencies in the presence of records, lists, sets and multisets. we investigate functional dependencies in databases that support complex values such as records, lists, sets anu multisets. therefore, an abstract algebraic framework is proposed that classifies data models according to the underlying types they support. this allows to emphasise the impact of the data types rather than the specifics of a particular data model.the main results are finite, minimal, sound and complete sets of inference rules for the implication of functional dependencies in the presence of records and all combinations of lists, sets and multisets. the inference rules are similar to armstrong's original axioms for the relational data model, thanks to the algebraic framework. the completeness result, however, requires a deep analysis in the case of sets and, in particular, multisets.
unsupervised learning in neural computation. in this article, we consider unsupervised learning from the point of view of applying neural computation on signal and data analysis problems. the article is an introductory survey, concentrating on the main principles and categories of unsupervised learning. in neural computation, there are two classical categories for unsupervised learning methods and models: first, extensions of principal component analysis and factor analysis, and second, learning vector coding or clustering methods that are based on competitive learning. these are covered in this article. the more recent trend in unsupervised learning is to consider this problem in the framework of probabilistic generative models. if it is possible to build and estimate a model that explains the data in terms of some latent variables, key insights may be obtained into the true nature and structure of the data. this approach is also briefly reviewed.
the minimum-entropy set cover problem. we consider the minimum entropy principle for learning data generated by a random source and observed with random noise.in our setting we have a sequence of observations of objects drawn uniformly at random from a population. each object in the population belongs to one class. we perform an observation for each object which determines that it belongs to one of a given set of classes. given these observations, we are interested in assigning the most likely class to each of the objects.this scenario is a very natural one that appears in many real life situations. we show that under reasonable assumptions finding the most likely assignment is equivalent to the following variant of the set cover problem. given a universe u and a collection i = (s1, ..., st) of subsets of u, we wish to find an assignment f : u → i such that u ∈ f(u) and the entropy of the distribution defined by the values |f-1 (si)| is minimized.we show that this problem is np-hard and that the greedy algorithm for set cover s with an additive constant error with respect to the optimal cover. this sheds a new light on the behavior of the greedy set cover algorithm. we further enhance the greedy algorithm and show that the problem admits a polynomial time approximation scheme (ptas).finally, we demonstrate how this model and the greedy algorithm can be useful in real life scenarios, and in particular, in problems arising naturally in computational biology.
the propositional dynamic logic of deterministic, well-structured programs. we consider a restricted propositional dynamic logic, strict deterministic propositional dynamic logic (sdpdl), which is appropriate for reasoning about deterministic well-structured programs. in contrast to pdl, for which the validity problem is known to be complete in deterministic exponential time, the validity problem for sdpdl is shown to be polynomial space complete. we also show that sdpdl is less expressive than pdl. the results rely on structure theorems for models of satisfiable sdpdl formulas, and the proofs give insight into the effects of nondeterminism on intractability and expressiveness in program logics.
two applications of analytic functors. we apply the theory of analytic functors to two topics related to theoretical computer science. one is a mathematical foundation of certain syntactic well-quasi-orders and well-orders appearing in graph theory, the theory of term rewriting systems, and proof theory. the other is a new verification of the lagrange-good inversion formula using several ideas appearing in semantics of lambda calculi, especially the relation between categorical traces and fixpoint operators. copyright 2002 elsevier science b.v.
competitive exploration of rectilinear polygons. exploring a polygon with robots when the robots do not have knowledge of the surroundings can be viewed as an online problem. typical for online problems is that decisions must be made based on past events without complete information about the future. in our case the robots do not have complete information about the environment. competitive analysis can be used to measure the performance of methods solving online problems. the competitive ratio of such a method is the ratio between the method's performance and the performance of the best method having full knowledge of the future. we prove constant competitive strategies and lower bounds for exploring a simple rectilinear polygon in the l1 metric.
two categories of effective continuous cpos. this paper presents two categories of effective continuous complete partial orders (cpos). we define a new criterion on the basis of a cpo so as to make the resulting category of consistently complete continuous cpos cartesian closed. we also generalise to continuous cpos the definition of a complete set, which was used as a definition of effective bifinite domains in hamrin and stoltenberg-hansen [cartesian closed categories of effective domains, in: h. schwichtenberg, r. steinbrüggen (eds.), proof and system-reliability, kluwer academic publishers, dordrecht, 2002, pp. 1-20], and investigate the closure results that can be obtained.
density results on floating-point invertible numbers. let fk denote the k-bit mantissa floating-point (fp) numbers. we prove a conjecture of muller according to which the proportion of numbers in fk with no fp-reciprocal (for rounding to the nearest element) approaches ½ - 3/2log4/3 ≈ 0.06847689 as k → ∞. we investigate a similar question for the inverse square root.