r-format vs table-format

[litwr]

Google wiki page (http://code.google.com/p/ruletablerepos ... /TheFormat) about n-state rules in xlife r-formats has a cite "The problem is that it doesn't provide enough compression." It asserts that table-format has better compression. I've just performed appropriate measurements. I use table2r utility from Xlife 6.5 distribution (http://http://litwr2.atspace.eu/xlife.php). This utility is written in Awk so it may be used at any platform. The results (sizes in bytes) are shown in the next table.

Code: Select all

Rules          |states|r-format|table-format|ratio
--------------------------------------------------
Byl-Loop       |6     |1487    |1493        |+0%
Chou-Reggia1   |8     |1683    |1689        |+0%
Chou-Reggia2   |8     |919     |925         |+0%
Codd           |8     |4816    |8001        |+66%
Codd2          |8     |5535    |8756        |+58%
Devore         |8     |3987    |6316        |+58%
Evoloop        |9     |3461    |4828        |+39%
Evoloop-finite |10    |2547    |3914        |+54%
F-sexyloop     |12    |6283    |9817        |+56%
HPP            |34    |4800    |2726        |-43%
Langton-Loops  |8     |1921    |1927        |+0%
Perrier        |64    |11917   |9737        |-18%
SDSR-loop      |9     |3717    |5019        |+35%
Sexyloop-M1    |10    |3555    |3528        |-0%
Sexyloop-M2    |10    |3430    |3403        |-0%

The table-format shows a slightly better compression only with automata with more than 30 states. So the wiki page phrase is incorrect in general. Eric Raymond's r-format may provide better compression in many cases. IMHO the table-format has a bit higher level and a bit more expressive. The table-format can easily use any number of states--the r-format is more inflexible here. Maybe the table-format has also better compression for Moore neighborhood but this is not tested--the current version of Xlife and table2r doesn't support such n-state automata.

The utility table2r may directly run from Unix like environment, e.g.,

Code: Select all

table2r INFILE OUTFILE

where INFILE must be input table-format file and OUTFILE must be the resulting r-format file.

Awk has several variants (bawk, gawk, mawk) which is freely available for Microsoft Windows and Apple OS. Run

Code: Select all

awk -f table2r INFILE OUTFILE

The table-format rules were taken from Golly distribution and from Nicolas Oros's website.

[Tim Hutton]

Hi litwr,

When I wrote this:

The adopted solution can be found in Gianluca Tempesti's thesis - using variables to stand for multiple states. Then, e.g. for a={1,2,3}, the rule 1,a,3 -> a would stand for three rules at once: 1,1,3 -> 1 and 1,2,3 -> 2 and 1,3,3 -> 3. This method gives all the compression of the XLife approach and then some more on top. (link)

I was talking about the number of transitions, not the overall file size. Sorry that wasn't clear. Any r-format transition can be expressed as a single table-format transition but some table-format transitions (those involving bound variables, as the example above) can only be expressed with two or more r-format transitions. Given 100 table-format transitions each using bound variables, we would need at least 200 r-format transitions. That's what I meant by compression.

The reason to be concerned about the number of transitions is that when running a CA we need to check each input against the list of transitions, so it is good to make as few checks as possible. (The rule tree format does an even better job.)

In retrospect though we haven't really seen much benefit from having bound variables - only Tempesti.table makes great use of them, as I recall. And the compressor I wrote (make-ruletable.cpp, which produced some of the table files you analyzed) doesn't yet use them. And the RuleTable algorithm in Golly expands them out anyway, along with the various symmetries.

And since then we came up with make-ruletree.py, which converts rules expressed as Python code into rule trees. With this approach you get the best of both worlds: Python is a more natural way to express many rules, and rule trees are quick for running. In a way we've come back to the CDL approach but avoiding users needing a C or Java compiler to run the rules. The only downside is that the whole state-space must be traversed, which takes too long when there are many states (more than 50 or so).

I don't use XLife myself but it was useful for me when working on Codd's machine because some of ESR's work on it was still there. Let me know if I can help with anything. Is your version the one included in Debian?

Tim

[litwr]

Thank you very much for the answer.
I agree with your arguments. However there is other side.

Code: Select all

1[12][12][12][12]2

Code: Select all

var a={1,2}
var b={1,2}
var c={1,2}
var d={1,2}
1,a,b,c,d,2

Xlife v5.0.8 was with Debian until version 6 where it was replaced by Golly. I plan to reinclude updated xlife to the next Debian release. I also think about OpenBSD which still distributes v5.3 of xlife. I don't have experience in this field so it may be a bit slow. Could somebody give some advice (vol.litwr at gmail dot com)?

Thank you again
Yours sincerely,
Vladimir (vol litwr)

[litwr]

I have an idea how to optimize the table-format. IMHO The best way is to use a special symbol (like $) to force equality of states in a rule. So the next text
var a={1,2}
var b={1,2}
1,a,b,2,a,4

maybe replaced by
var a={1,2}
1,$a,a,2,$a,4

To preserve existing table-files we had to use the special symbol (e.g., *) for the opposite case.
var a={1,2}
1,a,*a,2,a,4
This notation is compatible with existing format, has good readablity and gives the compression. It is possible to support the usage of both special signs---it is only impossible, of course, to use both in one rule.

[litwr]

I've tested make-ruletable.cpp---it is a very useful program. However I'm curious. Where rules in the format like
1,[0,2],0 -> 3
are used? It maybe useful to support them by Golly. IMHO the support of "the unbound sign" (e.g., *) for the variables may be a bit better.
BTW ESR may continue the development of Xlife! He has unpublished version 5.4 and 5.5.

[Tim Hutton]

Hi litwr,

There was some discussion of unbound variables, here:
http://code.google.com/p/ruletablerepos ... dVariables

To see the different neighborhoods that the rule table format supports, see here:
http://code.google.com/p/ruletablerepos ... ki/RoadMap

Tim

[litwr]

Thank you very much for the link. I've just added a comment to UnboundVariables topic. BTW I have question about ruletree rules format. Is it precompiled, unreadable form of table-format? It looks so. Why does Golly ask to select between ruletree and table formats? IMHO it would be convinient to seek automatically a corresponded ruletree.