Copyright	(c) 2021-2024 Dakotah Lambert
License	MIT
Safe Haskell	Safe-Inferred
Language	Haskell2010

LTK.Decide.DotDepth

Description

This module implement algorithms to decide whether a given FSA has a given dot depth. Currently, only dot depth one is testable, using the equations presented by Knast's 1983 "A semigroup characterization of dot-depth one languages" https://doi.org/10.1051/ita/1983170403211

Since: 1.2

Synopsis

isDot1 :: (Ord n, Ord e) => FSA n e -> Bool
isDot1M :: (Ord n, Ord e) => SynMon n e -> Bool
isDot1s :: FiniteSemigroupRep s => s -> Bool

Documentation

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

True iff the automaton recognizes a dot-depth one stringset.

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

True iff the monoid recognizes a dot-depth one stringset.

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

True iff the semigroup recognizes a dot-depth one stringset. That is, for idempotents \(e\) and \(f\) and elements \(a\), \(b\), \(c\) and \(d\), it holds that ((eafb)^{omega}eafde(cfde)^{omega} = (eafb)^{omega}e(cfde)^{omega}).