An algebraic approach to regular sets

Horst Reichel

pp. 449-458

in: Kokichi Futatsugi, Jean-Pierre Jouannaud, José Meseguer (eds), Algebra, meaning, and computation, Berlin, Springer, 2006

Abstract

In recent years an increasing interest in regular sets for different kinds of elements could be observed. The introduction of XML has led to investigations of regular sets of both ranked and unranked trees and also of attributed unranked trees.The aim of this short note is to introduce a uniform notion of regularity. If instantiated for strings, ranked trees and unranked trees it will coincide with the existing concepts and it can easily be extended to arbitrary data types. This leads to a natural notion of regularity for different kinds of attributed unranked trees and also to regular sets of structured elements which have not yet been investigated. The approach takes advantage from freeness constraints and parametric abstract data types as offered by the algebraic specification language Casl