In 2008, some members of Prague Stringology Club started dealing with algorithms on trees and have founded an algorithmic discipline, which was given the name Arbology from the Spanish word 'Arbol', meaning 'Tree'.

The main motivation for founding arbology was to apply the well-known principles of algorithms from stringology to trees so that effective analogous tree algorithms would be created.

In stringology, finite automata can be used as the model of computation. To process trees, which are recursive structures, arbology uses pushdown automata, which read linearised notations of trees, as its basic model of computation. We think that arbology is unique in the sense it represents a systematic approach to creating tree algorithms by means of pushdown automata (although some particular tree algorithms based on pushdown automata, for example Graham-Glanville technique used for code selection, are known).

Arbology as a new discipline was oficially first introduced at London Stringology Days 2009. Overview of basic arbology principles and results was presented by Borivoj Melichar as an invited speaker at the 4th International Conference on Language and Automata Theory and Applications 2010 .

Our latest considerations aim to analogous automata algorithms for the processing of directed acyclic graphs.

You can contact us here.

Created by: Jan Janousek Last updated:18/7/2011