Railway Interlocking Systems
and Gröbner Bases1

Eugenio Roanes-Lozano\dag Luis M. Laita\ddag
Eugenio Roanes-Macías\dag
\dagDept. Algebra, Universidad Complutense de Madrid
\ddagDept. I.A., Universidad Politécnica de Madrid


The information of a situation of trains, switches and signals (or semaphores) in a station can be represented in an oriented graph. This information can be translated into polynomial form (in a way relatively similar to Bayer's treatment of the 3-Color problem). The safety of the situation can then be decided by checking (using GB) whether or not a certain ideal is the whole polynomial ring. If a section is accessible by a train departing from another given section can also be checked this way (by testing an ideal membership). That trains could occupy more than one section is considered.


IMACS ACA'98 Electronic Proceedings