Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
Spot
Spot
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 117
    • Issues 117
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
  • Merge Requests 1
    • Merge Requests 1
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Spot
  • SpotSpot
  • Issues
  • #17

Closed
Open
Opened 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
None
Milestone
None
Assign milestone
Time tracking
None
Due date
None
Reference: spot/spot#17