Power-series automaton
The automaton τ(x)(n) = x(n) - t x(n + 1) over the ring K[[t]] of formal power series on a ring.
- Name:
power_series_automaton - Field:
computer_science/automata - Formalism: lattice dynamics
- References: Ceccherini-Silberstein and Coornaert 2023
Select this system
from skcomplex.systems import create_simulation, create_system, describe
system = create_system('power_series_automaton')
entry = describe('power_series_automaton')
trajectory = create_simulation('power_series_automaton').prepare().run().trajectory_
Factory
@register_system(
field='computer_science/automata',
tags=('lattice', 'infinite alphabet', 'power series', 'bijective'),
references=('Ceccherini-Silberstein and Coornaert 2023',),
defaults={'until': 12, 'dt': 1},
)
def power_series_automaton(
size: int = 31,
*,
order: int = 8,
field: str = 'QQ',
initial: npt.ArrayLike | None = None,
) -> System:
"""Return the automaton `τ(x)(n) = x(n) - t x(n + 1)` over the ring `K[[t]]` of formal power series on a ring.
The alphabet `K[[t]]` has infinite dimension, and the automaton is bijective with the inverse
`sigma(y)(n) = sum_j t^j y(n + j)`, which is not continuous, so it is no cellular automaton
(Ceccherini-Silberstein and Coornaert 2023, Exercise 1.37). The cells hold the series truncated at the order, which
keeps every coefficient below it exact, since the coefficient of `t^i` of the image reads coefficients of `t^i` and
`t^(i - 1)` alone. From the constant series 1 at one cell, the cells at step `s` hold
`C(s, k) (-t)^k` at the `k`-th cell to the left, as long as `k` stays below the order.
Args:
size:
The number of cells of the ring.
order:
The number of coefficients kept.
field:
The field `K`, `'QQ'`, `'RR'`, or `'GF(p)'`.
initial:
The initial coefficients, an array of shape `(size, order)`, or `None` for the series 1 in the middle cell.
Returns:
system:
The system, with the coefficients `cells.value`.
Examples:
>>> from skcomplex.systems.computer_science.automata import power_series_automaton
>>> power_series_automaton(5, order=3).elements[0].values['value'].shape
(5, 3)
"""
ring = PowerSeriesSpec(order, field)
if initial is None:
values = np.zeros((size, order))
values[size // 2, 0] = 1.0
else:
values = np.asarray(initial, dtype=float)
rule = functools.partial(
_power_series_difference,
ring=ring,
variable=ring.coefficients_of(ring.ring.gen()),
)
return System(
elements=[
LatticeElement(
'cells',
element=PowerSeriesCellElement,
space=LatticeSpace(size),
values={'ring': ring, 'value': values},
),
],
interactions=[
LocalRuleInteraction('difference', target='cells', state='value', rule=rule, neighborhood=FORWARD),
],
)
Components
Elements:
PowerSeriesCellElement, fromDeclaredElement
Interactions:
LocalRuleInteraction
class PowerSeriesCellElement(DeclaredElement):
"""Cell of an automaton over a ring `K[[t]]` of formal power series truncated at an order.
The cell declares the state `value` in the ring it is given, so it holds the coefficients `a_0, ..., a_{order - 1}`
of a series, which a local rule reads as one row per cell.
Args:
label:
The label of the cell or the lattice group.
visual:
How the element is drawn, or `None` for `default_visual_`.
ring:
The truncated power series ring of the values.
variables:
Declared states and parameters besides `value`, or values that replace its default, by name.
Examples:
>>> from skcomplex.core.specs import PowerSeriesSpec
>>> from skcomplex.systems.computer_science.automata import PowerSeriesCellElement
>>> PowerSeriesCellElement('cell', ring=PowerSeriesSpec(3)).get_value('value').tolist()
[0.0, 0.0, 0.0]
"""
def __init__(
self,
label: str,
visual: VisualSpec | None = None,
*,
ring: PowerSeriesSpec = RATIONAL_SERIES,
variables: Mapping[str, DeclaredVariableSpec] | None = None,
) -> None:
super().__init__(label, visual=visual, variables=variables)
self.ring = ring
def _declare_variables(self) -> Mapping[str, DeclaredVariableSpec]:
"""Return the state `value` in the ring, with the zero series as its default, and the given variables."""
value = DeclaredVariableSpec(np.zeros(self.ring.order), StateSpec(domain=self.ring))
return {'value': value, **(self.variables or {})}
class LocalRuleInteraction(Interaction):
"""Local rule of a cellular automaton, which sets the next value of every cell from its ordered neighbourhood.
The rule is a table of the next value of every configuration of the neighbourhood, `TableSpec`, a rule of the sum
of the neighbourhood, `TotalisticSpec`, a rule of the cell and the sum of its neighbours, `OuterTotalisticSpec`, an
object whose `table()` returns a `TableSpec`, or a function. A function receives one array per neighbour of every
read state, in neighbourhood order, with one value per cell, the uniform array `random` when the rule is stochastic,
and the parameters of the bound group it names, and returns the next values of the states, one array per state. A
state of several components per cell, such as a truncated power series of `PowerSeriesSpec`, reaches a function as
one row of components per cell. A `StateTranslationNeighborhood` reads a group space at the product of every site
and the group element that the first read state holds there.
Args:
label:
The label of the interaction, unique among the parts of its system.
target:
The path of the group on the cells of a lattice, the nodes of a network, or a Cayley graph.
state:
The name of the state the rule sets, or a tuple of the names of the states it sets together.
rule:
The table, the totalistic rule, or the function.
neighborhood:
The ordered neighbourhood of every cell, such as `VonNeumannNeighborhood(center=True)`.
reads:
The names of the states whose neighbourhoods a function reads, or `None` for the states it sets.
schedule:
`'synchronous'`, `'random-sequential'`, `'random-site'`, `'checkerboard'`, or `'colored'`.
stochastic:
Whether a function receives the uniform random array `random`.
Raises:
ValidationError:
The state or the read states are not names, or the neighbourhood is not a neighbourhood.
Examples:
>>> from skcomplex.core.components.interactions import LocalRuleInteraction
>>> from skcomplex.core.components.spaces import VonNeumannNeighborhood
>>> from skcomplex.core.specs import TotalisticSpec
>>> parity = TotalisticSpec({1: 1, 3: 1})
>>> around = VonNeumannNeighborhood(n_dim=1, center=True)
>>> rule = LocalRuleInteraction('parity', target='cells', state='cell', rule=parity, neighborhood=around)
>>> rule.schedule
'synchronous'
"""
law_classes: ClassVar[tuple[type[BaseLaw], ...]] = (LocalRuleLaw,)
def __init__(
self,
label: str,
*,
target: Annotated[str, RoleSpec(elements=(ElementKind.ANY,), states=('state', 'reads'))],
state: str | tuple[str, ...],
rule: object,
neighborhood: BaseNeighborhood,
reads: Sequence[str] | None = None,
schedule: str = 'synchronous',
stochastic: bool = False,
) -> None:
super().__init__(label)
self.target = target
self.state = state
self.rule = rule
self.neighborhood = neighborhood
self.reads = reads
self.schedule = schedule
self.stochastic = stochastic
def _get_names(self) -> tuple[str, ...]:
"""Return the names of the states the rule sets."""
return (self.state,) if isinstance(self.state, str) else tuple(self.state)
def _check(self) -> None:
"""Raise an error for states that are not names, or a neighbourhood that is not one.
Raises:
ValidationError:
The state or the read states are not names, or the neighbourhood is not a neighbourhood.
"""
super()._check()
names = [*self._get_names(), *(self.reads or ())]
if not names or not all(isinstance(name, str) and name.isidentifier() for name in names):
error_msg = f'The local rule {self.label!r} sets {self.state!r} and reads {self.reads!r}. Give state names.'
raise ValidationError(error_msg)
if not isinstance(self.neighborhood, BaseNeighborhood):
error_msg = f'The neighbourhood of the local rule {self.label!r} is {self.neighborhood!r}. Give one.'
raise ValidationError(error_msg)
def _get_laws(self, namespace: SimpleNamespace) -> list[BaseLaw]:
"""Return the local rule law of the states of the target.
Args:
namespace:
The namespace of the symbols the laws can use, with `namespace.target`.
Returns:
laws:
The local rule law.
"""
targets = tuple(getattr(self._get_member(namespace, 'target'), name) for name in self._get_names())
reads = (
None
if self.reads is None
else tuple(getattr(self._get_member(namespace, 'target'), name) for name in self.reads)
)
return [
LocalRuleLaw(
targets[0] if isinstance(self.state, str) else targets,
self.neighborhood,
self.rule,
reads=reads,
schedule=self.schedule,
stochastic=self.stochastic,
label=self.label,
),
]