Journal article icon

Journal article

Low algorithmic complexity entropy-deceiving graphs

Abstract:

A common practice in the estimation of the complexity of objects, in particular of graphs, is to rely on graph- and information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which a single object, such a graph, can be described. From descriptions that can reconstruct the same graph and are therefore essentially translations of the same description, we will see that not only is it neces...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1103/PhysRevE.96.012308

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Role:
Author
Swedish Research Council More from this funder
Publisher:
American Physical Society Publisher's website
Journal:
Physical Review E Journal website
Volume:
96
Pages:
012308
Publication date:
2017-08-02
Acceptance date:
2017-03-19
DOI:
Pubs id:
pubs:640721
URN:
uri:01b08691-9e3b-4505-acc2-07084740b00c
UUID:
uuid:01b08691-9e3b-4505-acc2-07084740b00c
Local pid:
pubs:640721

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP