language-toolkit-1.2.0.0: A set of tools for analyzing languages via logic and automata
Copyright(c) 2017-2023 Jim Rogers and Dakotah Lambert
LicenseMIT
Safe HaskellSafe-Inferred
LanguageHaskell2010
ExtensionsCpp

LTK.Traversals

Description

Find paths through an automaton.

Synopsis

Documentation

data Path n e #

A path through an FSA.

Constructors

Path 

Fields

Instances

Instances details
Ord n => Monoid (Path n e) # 
Instance details

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) # 
Instance details

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) # 
Instance details

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) # 
Instance details

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) # 
Instance details

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