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

better encoding for parity acceptance #42

Closed
adl opened this issue May 19, 2015 · 6 comments
Closed

better encoding for parity acceptance #42

adl opened this issue May 19, 2015 · 6 comments
Labels

Comments

@adl
Copy link
Owner

@adl adl commented May 19, 2015

I'm implementing some support for generating and recognizing parity acceptance conditions, and I don't like the encoding currently suggested in the specifications:

acc-name: parity min even 5
Acceptance: 5 Inf(0) | (Fin(0)&Fin(1)&Inf(2)) | (Fin(0)&Fin(1)&Fin(2)&Fin(3)&Inf(4))

I would prefer this to be

acc-name: parity min even 5
Acceptance: 5 Inf(0) | (Fin(1)&Inf(2)) | (Fin(1)&Fin(3)&Inf(4))

The two formulas are logically equivalent, but the second

  • is an irredundant sum of products,
  • does not use the same set number in both Fin and Inf primitves.

In particular, I have found the latter point to be important in several algorithms. I can think of at least three algorithms in Spot where either I have special cases to handle acceptance with sets that are both used as Inf and Fin, or the algorithm is simply requires disjoint Fin/Inf numbers as a prerequisite. (My typical simple "horror case" is Acceptance: 2 (Fin(0)&Inf(1)) | (Inf(0)&Fin(1)) which basically encodes Inf(0) xor Inf(1).)

What do you think? Can I change the parity examples to use the irredundant encoding?

@adl adl added the enhancement label May 19, 2015
@xblahoud
Copy link
Collaborator

@xblahoud xblahoud commented May 20, 2015

I like the suggestion. It makes the acceptance shorter and I can't see any disadvantages.

@strejcek
Copy link
Collaborator

@strejcek strejcek commented May 20, 2015

I agree, please change it.

@adl
Copy link
Owner Author

@adl adl commented May 20, 2015

I've made a patch on branch adl/42, but I would like Joachim's opinion before we merge it, as I think he is the only producer of Parity automata currently.

@JanKretinsky
Copy link
Collaborator

@JanKretinsky JanKretinsky commented May 20, 2015

I'm also fine with your suggestion

@kleinj
Copy link
Collaborator

@kleinj kleinj commented May 20, 2015

Fine by me. Currently, jhoafparser does not check for the canonical Acceptance expression for parity, I'll add that.

Should we add the canonical expressions for 'min odd' and 'max even' to the format document as well, just to be extra clear what's expected?

adl added a commit that referenced this issue May 20, 2015
@adl
Copy link
Owner Author

@adl adl commented May 20, 2015

I've added examples for parity min odd 6 and parity max even 5. Can you double check and merge if you are happy with it?

@adl adl closed this in 663a6d4 May 20, 2015
kleinj added a commit that referenced this issue May 20, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.