Skip to content
GitLab
  • Menu
Projects Groups Snippets
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in
  • Spot Spot
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 132
    • Issues 132
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 2
    • Merge requests 2
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Spot
  • SpotSpot
  • Issues
  • #17
Closed
Open
Created Dec 19, 2014 by Alexandre Duret-Lutz@adlOwner

autfilt --are-equivalent

It would be nice to be able to run this from the command-line.

If the automata are minimal WDBA, this is easier, since they can be complemented in linear time. Löding (/Efficient minimization of deterministic weak ω-automata/, 2001) discusses such equivalence check in its last paragraph. Dealing with DBA that are not weak is also easy.

In the general case we would have to use some complementation algorithm (but I'd prefer that we reimplement Safra's construction — see #16 (closed)). Maybe we can also avoid the cost of Safra in case the automata are isomorphic.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking