Data.Comp.Automata

This module defines tree automata based on compositional data types.

Documentation

type DUTATrans f q = Alg f q

This type represents transition functions of deterministic bottom-up tree acceptors (DUTAs).

data DUTA f q

This data type represents deterministic bottom-up tree acceptors (DUTAs).

Constructors

DUTA

Fields

dutaTrans :: DUTATrans f q

dutaAccept :: q -> Bool

runDUTATrans :: Functor f => DUTATrans f q -> Term f -> q

This function runs the transition function of a DUTA on the given term.

duta :: Functor f => DUTA f q -> Term f -> Bool

This function checks whether a given DUTA accepts a term.

type NUTATrans f q = AlgM [] f q

This type represents transition functions of non-deterministic bottom-up tree acceptors (NUTAs).

data NUTA f q

This type represents non-deterministic bottom-up tree acceptors.

Constructors

NUTA

Fields

nutaTrans :: AlgM [] f q

nutaAccept :: q -> Bool

runNUTATrans :: Traversable f => NUTATrans f q -> Term f -> [q]

This function runs the given transition function of a NUTA on the given term

nuta :: Traversable f => NUTA f q -> Term f -> Bool

This function checks whether a given NUTA accepts a term.

determNUTA :: Traversable f => NUTA f q -> DUTA f [q]

This function determinises the given NUTA.

type DUTTTrans f g q = forall a. f (q, a) -> (q, Cxt Hole g a)

This function represents transition functions of deterministic bottom-up tree transducers (DUTTs).

duttTransAlg :: (Functor f, Functor g) => DUTTTrans f g q -> Alg f (q, Term g)

This function transforms a DUTT transition function into an algebra.

runDUTTTrans :: (Functor f, Functor g) => DUTTTrans f g q -> Term f -> (q, Term g)

This function runs the given DUTT transition function on the given term.

data DUTT f g q

This data type represents deterministic bottom-up tree transducers.

Constructors

DUTT

Fields

duttTrans :: DUTTTrans f g q

duttAccept :: q -> Bool

dutt :: (Functor f, Functor g) => DUTT f g q -> Term f -> Maybe (Term g)

This function transforms the given term according to the given DUTT and returns the resulting term provided it is accepted by the DUTT.

type NUTTTrans f g q = forall a. f (q, a) -> [(q, Cxt Hole g a)]

This type represents transition functions of non-deterministic bottom-up tree transducers (NUTTs).

nuttTransAlg :: (Functor f, Functor g) => NUTTTrans f g q -> AlgM [] f (q, Term g)

This function transforms a NUTT transition function into a monadic algebra.

runNUTTTrans :: (Traversable f, Functor g) => NUTTTrans f g q -> Term f -> [(q, Term g)]

This function runs the given NUTT transition function on the given term.

data NUTT f g q

This data type represents non-deterministic bottom-up tree transducers (NUTTs).

Constructors

NUTT

Fields

nuttTrans :: NUTTTrans f g q

nuttAccept :: q -> Bool

nutt :: (Traversable f, Functor g) => NUTT f g q -> Term f -> [Term g]

This function transforms the given term according to the given NUTT and returns a list containing all accepted results.