| Copyright | (c) 2021-2024 Dakotah Lambert |
|---|---|
| License | MIT |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
LTK.Decide.Definite
Contents
Description
This module implements an algorithm to decide whether a given FSA is Definite (Def) or Reverse Definite (RDef) based on the classic semigroup characterizations summarized by Brzozowski and Fich in their 1984 work "On Generalized Locally Testable Languages".
Since: 1.0
Synopsis
- isDef :: (Ord n, Ord e) => FSA n e -> Bool
- isDefM :: (Ord n, Ord e) => SynMon n e -> Bool
- isDefs :: FiniteSemigroupRep s => s -> Bool
- isRDef :: (Ord n, Ord e) => FSA n e -> Bool
- isRDefM :: (Ord n, Ord e) => SynMon n e -> Bool
- isRDefs :: FiniteSemigroupRep s => s -> Bool
- isTDef :: (Ord n, Ord e) => FSA n e -> Bool
- isTDefM :: (Ord n, Ord e) => SynMon n e -> Bool
- isTDefs :: FiniteSemigroupRep s => s -> Bool
- isTRDef :: (Ord n, Ord e) => FSA n e -> Bool
- isTRDefM :: (Ord n, Ord e) => SynMon n e -> Bool
- isTRDefs :: FiniteSemigroupRep s => s -> Bool
Plain
isDef :: (Ord n, Ord e) => FSA n e -> Bool #
True iff the automaton recognizes a definite stringset, characterized by a set of permitted suffixes.
isDefs :: FiniteSemigroupRep s => s -> Bool #
True iff \(Se=e\) for idempotents \(e\).
Since: 1.2
isRDef :: (Ord n, Ord e) => FSA n e -> Bool #
True iff the automaton recognizes a reverse definite stringset, characterized by a set of permitted prefixes.
isRDefs :: FiniteSemigroupRep s => s -> Bool #
True iff \(eS=e\) for idempotents \(e\).
Since: 1.2
Tier-Based
isTDefs :: FiniteSemigroupRep s => s -> Bool #
Definite on the projected subsemigroup.
Since: 1.2
isTRDefs :: FiniteSemigroupRep s => s -> Bool #
Reverse definite on the projected subsemigroup.
Since: 1.2