InterJournal Complex Systems, 591 Status: Accepted |
Manuscript Number: [591] Submission Date: 20627 |
Production-rule complexity of recursive structures |
Subject(s): CX.04.01.2, CX.07
Category: Article
Abstract:
Complex recursive structures, such as fractals, are usually described by sets of production rules, also known as L-systems. According to this description, a structure is characterized by a sequence of elements, or letters, from a finite alphabet; a production rule prescribes replacement of each letter by a sequence of other letters. Practical applications of rewriting systems however are quite restricted since the real structures are not exactly recursive: they involve casual deviations due to external factors. There exist fractals corresponding to the strings, invariant under the rewriting rules. Some strings which are not invariant may also characterize a fractal structure. Sometimes the sequence of symbolic descriptions of a structure is known while the rewriting rules yet to be discovered. Following the Kolmogorov's idea to separate regular and random factors while considering the system's complexity it may be possible to filter out the underlying recursive structure by solving an inverse L-systems problem: given a sequence of symbolic strings determine the simplest (if any) rule set performing the transformation. The current paper is a work-in-progress report, presented at the Fourth International Conference on Complex Systems (Nashua, 2002), in which I give a preliminary account for issues involved in solving the inverse problem, and discuss an algorithm for finding the shortest description of the symbolic strings (analogous to the Chaitin's algorithmic complexity).
Retrieve Manuscript |
Submit referee report/comment |