Computer Science – Information Theory
Scientific paper
2010-05-13
Computer Science
Information Theory
The paper has been withdrawn due to the poor predictive performance of circuit complexity vs. universal data compression. Give
Scientific paper
We relate the computational complexity of finite strings to universal representations of their underlying symmetries. First, Boolean functions are classified using the universal covering topologies of the circuits which enumerate them. A binary string is classified as a fixed point of its automorphism group; the irreducible representation of this group is the string's universal covering group. Such a measure may be used to test the quasi-randomness of binary sequences with regard to first-order set membership. Next, strings over general alphabets are considered. The complexity of a general string is given by a universal representation which recursively factors the codeword number associated with a string. This is the complexity of the representation recursively decoding a Godel number having the value of the string; the result is a tree of prime numbers which forms a universal representation of the string's group symmetries.
No associations
LandOfFree
On Universal Complexity Measures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Universal Complexity Measures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Universal Complexity Measures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-640266