language-toolkit-1.2.0.0: A set of tools for analyzing languages via logic and automata
Copyright(c) 2021-2024 Dakotah Lambert
LicenseMIT
Safe HaskellSafe-Inferred
LanguageHaskell2010

LTK.Decide.Definite

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

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.

isDefM :: (Ord n, Ord e) => SynMon n e -> Bool #

True iff \(Se=e\) for idempotents \(e\).

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.

isRDefM :: (Ord n, Ord e) => SynMon n e -> Bool #

True iff \(eS=e\) for idempotents \(e\).

isRDefs :: FiniteSemigroupRep s => s -> Bool #

True iff \(eS=e\) for idempotents \(e\).

Since: 1.2

Tier-Based

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

Definite on some tier.

isTDefM :: (Ord n, Ord e) => SynMon n e -> Bool #

Definite on the projected subsemigroup.

isTDefs :: FiniteSemigroupRep s => s -> Bool #

Definite on the projected subsemigroup.

Since: 1.2

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

Reverse definite on some tier.

isTRDefM :: (Ord n, Ord e) => SynMon n e -> Bool #

Reverse definite on the projected subsemigroup.

isTRDefs :: FiniteSemigroupRep s => s -> Bool #

Reverse definite on the projected subsemigroup.

Since: 1.2