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 a suitable model of computation. To process trees, which are recursive structures, arbology uses pushdown automata, which read linearised notations of trees, as its suitable model of computation. This conforms with the fact that

We think that arbology is unique in the sense it tries to represent 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).

From the historical point of view, Arbology as a new discipline was oficially introduced at London Stringology Days 2009 for the first time. An overview of basic arbology principles was then presented by Borivoj Melichar as an invited speaker at the 4th International Conference on Language and Automata Theory and Applications 2010.

Our recent considerations aim to processing also directed acyclic graphs (DAGs) analogously. In this case, a linear-bounded automaton seems to be a suitable model of computation for processing DAGs.

You can contact us here.

Created by: Jan Janousek Last updated:3/3/2015