geometry_tools.automata

Work with finite-state automata.

The automata package provides tools meant to manipulate finite-state automata, via the geometry_tools.automata.fsa.FSA class. Below, we manually construct an automaton for the group $(\mathbb{Z}/2) * (\mathbb {Z}/3) \simeq \mathrm{PSL}(2, \mathbb{Z})$:

from geometry_tools.automata import fsa

# make the automaton from a python dictionary
z2_z3_aut = fsa.FSA({
    0: {'b': 1, 'B': 2, 'a': 3},
    1: {'a': 3},
    2: {'a': 3},
    3: {'b': 1, 'B':2}
}, start_vertices=[0])


# list accepted words
list(z2_z3_aut.enumerate_fixed_length_paths(3))

    ['bab', 'baB', 'Bab', 'BaB', 'aba', 'aBa']

For more details, see the documentation for fsa.

This package also provides a handful of word-acceptor automata for various hyperbolic groups. You can get a list of available automata by running:

from geometry_tools.automata import fsa
fsa.list_builtins()

The package does not provide any tools to produce finite-state automata from an arbitrary group presentation. You can, however, produce automata for word-hyperbolic groups in this way by running the kbmag program (which is not included with geometry_tools). kbmag will produce automata files which you can load and manipulate using geometry_tools.automata:

from geometry_tools.automata import fsa

# "automaton_file.wa" is the output of the kbmag "autgroup" command
my_fsa = fsa.load_kbmag_file("automaton_file.wa")

# python dictionary describing the automaton
my_fsa.graph_dict

Thanks to code provided by Florian Stecker, it is also possible to construct an automaton recognizing geodesic (and shortlex-geodesic) words in an arbitrary Coxeter group. See the documentation for coxeter.CoxeterGroup.automaton().

 1r"""Work with finite-state automata.
 2
 3The `automata` package provides tools meant to manipulate finite-state
 4automata, via the `geometry_tools.automata.fsa.FSA` class. Below, we manually
 5construct an automaton for the group $(\mathbb{Z}/2) * (\mathbb
 6{Z}/3) \simeq \mathrm{PSL}(2, \mathbb{Z})$:
 7
 8```python
 9from geometry_tools.automata import fsa
10
11# make the automaton from a python dictionary
12z2_z3_aut = fsa.FSA({
13    0: {'b': 1, 'B': 2, 'a': 3},
14    1: {'a': 3},
15    2: {'a': 3},
16    3: {'b': 1, 'B':2}
17}, start_vertices=[0])
18
19
20# list accepted words
21list(z2_z3_aut.enumerate_fixed_length_paths(3))
22```
23	['bab', 'baB', 'Bab', 'BaB', 'aba', 'aBa']
24
25For more details, see the documentation for `fsa`.
26
27This package also provides a handful of word-acceptor automata for various
28hyperbolic groups. You can get a list of available automata by running:
29
30```python
31from geometry_tools.automata import fsa
32fsa.list_builtins()
33```
34
35The package does *not* provide any tools to produce finite-state
36automata from an arbitrary group presentation. You can, however,
37produce automata for word-hyperbolic groups in this way by running the
38[kbmag](https://gap-packages.github.io/kbmag/) program (which is not
39included with `geometry_tools`). `kbmag` will produce automata files
40which you can load and manipulate using `geometry_tools.automata`:
41
42```python
43from geometry_tools.automata import fsa
44
45# "automaton_file.wa" is the output of the kbmag "autgroup" command
46my_fsa = fsa.load_kbmag_file("automaton_file.wa")
47
48# python dictionary describing the automaton
49my_fsa.graph_dict
50```
51
52Thanks to code provided by Florian Stecker, it is also possible to
53construct an automaton recognizing geodesic (and shortlex-geodesic)
54words in an arbitrary Coxeter group. See the documentation for
55coxeter.CoxeterGroup.automaton().
56
57    """
58
59from . import fsa, kbmag_utils, coxeter_automaton, gap_parse