Railway Interlocking Systems
and Gröbner Bases¹

Eugenio Roanes-Lozano Luis M. Laita
Eugenio Roanes-Macías
Dept. Algebra, Universidad Complutense de Madrid
Dept. I.A., Universidad Politécnica de Madrid

Abstract:

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.