LTK.Traversals

Find paths through an automaton.

Documentation

data Path n e

A path through an FSA.

Constructors

Path

Fields

• labels :: [Symbol e]

  Edge labels are gathered in reverse order, so labels is a reversed string.

• endstate :: Maybe (State n)

  Current State, if any.

• stateMultiset :: Multiset (State n)

  States seen so far, with multiplicity.

• depth :: Integer

  The number of edges taken so far.

Instances

Ord n => Monoid (Path n e)

Defined in LTK.Traversals

Methods

mempty :: Path n e

mappend :: Path n e -> Path n e -> Path n e

mconcat :: [Path n e] -> Path n e

Ord n => Semigroup (Path n e)

Defined in LTK.Traversals

Methods

(<>) :: Path n e -> Path n e -> Path n e

sconcat :: NonEmpty (Path n e) -> Path n e

stimes :: Integral b => b -> Path n e -> Path n e

(Show e, Show n) => Show (Path n e)

Defined in LTK.Traversals

Methods

showsPrec :: Int -> Path n e -> ShowS

show :: Path n e -> String

showList :: [Path n e] -> ShowS

(Eq e, Eq n) => Eq (Path n e)

Defined in LTK.Traversals

Methods

(==) :: Path n e -> Path n e -> Bool

(/=) :: Path n e -> Path n e -> Bool

(Ord e, Ord n) => Ord (Path n e)

Defined in LTK.Traversals

Methods

compare :: Path n e -> Path n e -> Ordering

(<) :: Path n e -> Path n e -> Bool

(<=) :: Path n e -> Path n e -> Bool

(>) :: Path n e -> Path n e -> Bool

(>=) :: Path n e -> Path n e -> Bool

max :: Path n e -> Path n e -> Path n e

min :: Path n e -> Path n e -> Path n e

word :: Path n e -> [Symbol e]

The reversal of the labels of the Path.

isAcyclic :: (Ord n, Ord e) => FSA n e -> Bool

True iff the given FSA contains no reachable cycles.

Since: 1.0

initialsPaths :: (Ord e, Ord n) => FSA n e -> Set (Path n e)

Initial open list for traversal from initial states.

initialsNDPath :: (Ord e, Ord n) => FSA n e -> Path (Set n) e

Initial open list for non-deterministic traversal from initial states.

rejectingPaths :: (Ord e, Ord n) => FSA n e -> Integer -> Set (Path n e)

All paths of length less than or equal to a given bound that do not end in an accepting state.

acyclicPaths :: (Ord e, Ord n) => FSA n e -> Set (Path n e)

All paths from initialsPaths that do not contain cycles.

extensions :: (Ord e, Ord n) => FSA n e -> Path n e -> Set (Path n e)

Paths extending a given path by a single edge.

boundedCycleExtensions :: (Ord e, Ord n) => FSA n e -> Integer -> Path n e -> Set (Path n e)

Extensions other than back-edges to a state that has been visited more than a given number of times.

nondeterministicAcyclicExtensions :: (Ord e, Ord n) => FSA n e -> Path (Set n) e -> Set (Path (Set n) e)

The extensions of a non-deterministic path other than back-edges