Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Extend map memoization of ffo/flo to nenoform formulae as well #27

Open
bestchai opened this issue May 26, 2020 · 0 comments
Open

Extend map memoization of ffo/flo to nenoform formulae as well #27

bestchai opened this issue May 26, 2020 · 0 comments
Labels
enhancement New feature or request

Comments

@bestchai
Copy link
Member

bestchai commented May 26, 2020

Right now, map checker memoizes ffo/flo for formulae which are strict subtrees of the original formula, but the checker often does ffo/flo on the negated nenoform of the formulae, so adding these to the memo table would be of great use.

Steps to implementation

  1. Need tree equality b/w LTL formulae
  • is top level equal?
  • are kids equal (order matter for most binop except xor, <->,)
  • are sets of formulae equal
  • are constants equal
  • are APs equal (by name)
  • Test with some parsing tests
  1. Collecting relevant APS
  • add neno, nneno form to map when collecting for each individual formula
  • create form -> nneno map
    • form -> nneno
    • nneno -> neno
    • neno -> nneno
  • Test by accessing elements in form -> nneno map and making sure they are equal
  1. getting all objects the same
  • create top lvl neno, nneno version.
  • for each:
    • traverse tree; at each node check both contents of
      • form -> APS: replace key if equal
      • form -> nneno: replace key, vals if equal
  • test by using the new neno formulae function and making sure those elements are in the nenoform -> APs map
  1. After all of the above, remove the use_memo diasblers around nnenoform calls

[Issue created by carolemieux: 2015-06-04]

@bestchai bestchai added the enhancement New feature or request label May 26, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant