Computing on binary strings

DOI10.1016/J.TCS.2014.09.039zbMATH Open1303.68162arXiv1112.0278OpenAlexW2015718462MaRDI QIDQ476852FDOQ476852

Authors: Tian-Ming Bu, Chen Yuan, Peng Zhang 

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Many problems in Computer Science can be abstracted to the following question: given a set of objects and rules respectively, which new objects can be produced? In the paper, we consider a succinct version of the question: given a set of binary strings and several operations like conjunction and disjunction, which new binary strings can be generated? Although it is a fundamental problem, to the best of our knowledge, the problem hasn't been studied yet. In this paper, an O(m^2n) algorithm is presented to determine whether a string s is representable by a set W, where n is the number of strings in W and each string has the same length m. However, looking for the minimum subset from a set to represent a given string is shown to be NP-hard. Also, finding the smallest subset from a set to represent each string in the original set is NP-hard. We establishes inapproximability results and approximation algorithms for them. In addition, we prove that counting the number of strings representable is #P-complete. We then explore how the problems change when the operator negation is available. For example, if the operator negation can be used, the number is some power of 2. This difference maybe help us understand the problem more profoundly.

Full work available at URL: https://arxiv.org/abs/1112.0278

Recommendations

• Mathematical Foundations of Computer Science 2004
• Computing Minimum Length Representations of Sets of Words of Uniform Length
• Generation problems
• The complexity of some complementation problems
• Computing minimum length representations of sets of words of uniform length

zbMATH Keywords

NP-hardcombinatorial algorithmbinary stringsBoolean operation\(\#\)P-complete

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cites Work

• A threshold of ln n for approximating set cover
• Reducibility among combinatorial problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Theory of Representation for Boolean Algebras
• Title not available (Why is that?)

Cited In (5)

• Counting certain binary strings
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• Constant factor approximation for the weighted partial degree bounded edge packing problem
• The coolest way to generate binary strings
• Computing runs on a trie

This page was built for publication: Computing on binary strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476852)