Title: The Pascal matroid as a home for generating sets of cellular automata configurations defined by quasigroups
Authors: BarbĂ©, AndrĂ© ×
von Haeseler, F #
Issue Date: Oct-2004
Publisher: Elsevier science bv
Series Title: Theoretical computer science vol:325 issue:2 pages:171-214
Abstract: Consider a one-dimensional CA whose local evolution rule is defined by a quasigroup (G, star). When the initial state is only known over a finite string of adjacent cells, the CA's orbit (state-time diagram) is only defined on a triangular array of cells. This well-defined triangular part of the orbit, in which each cell has a value in G, is called a (G, star)-configuration. A generating set is a subset of the triangular array such that any attribution of G-values to the cells of this subset determines a unique (G, star)-configuration. It turns out that the collection of all potential generating sets form a particular matroid, which we have called the Pascal matroid. The main subject of this work is related to the question whether every base of this matroid actually occurs as a generating set for a (G, star)-configuration. (C) 2004 Elsevier B.V. All rights reserved.
ISSN: 0304-3975
Publication status: published
KU Leuven publication type: IT
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science