Skip to content

Non-Empty set from Contravariant.Adjuction use cases #11

Description

@subttle

Writing this idea down before I forget:
Data.Functor.Contravariant.Adjunction has an instance for Predicate Predicate, for which the unit (and also counit) which can be thought of, IIRC, as giving all the possible non-empty "sets" with respect to some unit element. I wonder if there is a way to use that in this library, for example in the synchronizing function below, I have a need for non empty sets. Would it make sense to use the aformention instance here or even perhaps other places?

-- Theorem (Cerny, 1964): A DFA M is (directable) synchronizing iff ∀q ∈ Q, ∃p ∈ Q, ∃w ∈ Σ★: δ(q, w) = δ(p, w)
-- That is, there exists a word w, such that evaluation of w from from any state, q, always ends up in the same state, p.
-- "A DFA is synchronizing if there exists a word that sends all states of the automaton to the same state." - https://arxiv.org/abs/1507.06070
synchronizing ∷ (Finite q, Finite s) ⇒                  DFA q s → Bool
synchronizing = not . isZero . power
          where power ∷ (Finite q) ⇒ DFA q s → DFA (Set q) s -- FIXME supposed to be a non-empty set -- TODO alter this to check for shortest path to get shortest reset word?
                power m@(DFA δ _ _) = DFA { delta = \(states, σ) → map (\q → δ (q, σ)) states
                                          , q0    = qs m
                                          , fs    = map singleton (qs m)
                                          }

The other place I think it could potentially be useful is in the next variant of the co-inductive automata, PA/NA. Will have to look into it.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions