Fix the allow_partial behavior, or deprecate it

[EduardoGoulart1]

Creating this issue to look into the semantics of the allow_partial flag.

See: https://github.com/caleb531/automata/pull/125 for the motivation

[caleb531]

@EduardoGoulart1 Thanks for this—I was intending to create a separate issue for this as a follow-up, but forgot. 😅

I'd like to repost your rationale for the sake of the discussion:

I don't think that the library should be guided by my specific needs, but allow_partial is actually useful for my use case. For instance, think about a "linear" DFA with a large alphabet. Not only is it more memory efficient, but it can also be more computationally efficient e.g. for minimization.

Please understand that I do see the practicality of keeping allow_partial from a memory and authoring perspective, however it introduces a lot of undefined behavior that needs to be resolved in order to implement it fully.

For example, when reading input, what should we do when there is no transition defined for the next input symbol that's read? You might probably say "throw a RejectionException like anything else!" and I would agree.

But how does that work in the context of a DFA method like _cross_product()? That method has nothing to do with reading input, and so it would not be appropriate to raise a RejectionException when transitions[some_state] results in a KeyError. These operations still need to produce valid DFAs that only accept/reject when input is actually read, but how do you represent (in the output DFA) the fact that we encountered a missing transition along the way? I don't know if there's any theoretical algorithm to cover that.

So ultimately, I don't think we can work around the memory limitations, because in order to preserve the integrity of existing DFA operations, every DFA must be complete (i.e. have a transition defined for every input symbol on every state). But having thought about it some more, I would still be open to the possibility of replacing allow_partial with a throwaway_state input parameter, but be aware that this would still be producing a not-so-memory-efficient complete DFA.

Thoughts?

cc @eliotwrobson

[EduardoGoulart1]

@EduardoGoulart1 Thanks for this—I was intending to create a separate issue for this as a follow-up, but forgot. sweat_smile

I'd like to repost your rationale for the sake of the discussion:

I don't think that the library should be guided by my specific needs, but allow_partial is actually useful for my use case. For instance, think about a "linear" DFA with a large alphabet. Not only is it more memory efficient, but it can also be more computationally efficient e.g. for minimization.

Please understand that I do see the practicality of keeping allow_partial from a memory and authoring perspective, however it introduces a lot of undefined behavior that needs to be resolved in order to implement it fully.

For example, when reading input, what should we do when there is no transition defined for the next input symbol that's read? You might probably say "throw a RejectionException like anything else!" and I would agree.

But how does that work in the context of a DFA method like _cross_product()? That method has nothing to do with reading input, and so it would not be appropriate to raise a RejectionException when transitions[some_state] results in a KeyError. These operations still need to produce valid DFAs that only accept/reject when input is actually read, but how do you represent (in the output DFA) the fact that we encountered a missing transition along the way? I don't know if there's any theoretical algorithm to cover that.

So ultimately, I don't think we can work around the memory limitations, because in order to preserve the integrity of existing DFA operations, every DFA must be complete (i.e. have a transition defined for every input symbol on every state). But having thought about it some more, I would still be open to the possibility of replacing allow_partial with a throwaway_state input parameter, but be aware that this would still be producing a not-so-memory-efficient complete DFA.

Thoughts?

cc @eliotwrobson

I'd like to start with a justification of why I think that allow_partial is worth the trouble. Just imagine the intersection between two almost linear DFAs with a large alphabet (say, 100 labels). You would gain a factor of 100 in memory and (more importantly) CPU cycles. I find myself doing a lot of DFA operations with relatively small (<10 states) DFAs, but with large alphabets (50-100). So even with small DFAs, the code is still relatively slow because of the large alphabet

In general, for me, the semantics of allow_partial is well defined. If you think about DFAs as sets of words, then a non-existing label has the same behavior as if that transition would exist and lead to a trap state. So operations such as complement, intersection, etc are well defined. The only caveat is that this target trap state is not represented explicitly, so you can't return this trap state when calling read_input_stepwise. But that's alright, we can just throw an error instead.

The _cross_product() operator specifically, is more of a helper function. For me, the semantics there should be: if a partial DFA is passed as a parameter, then the result is also a partial DFA. That could be implemented as a simple check at the beginning that switches between both implementations.

For testing the allow_partial behavior, we can use the existing tests, but add a method to_partial, that turns the DFA into a partial DFA by removing the trap state. That way we could easily use the existing tests cases.

As I said, I would need to give it a try on the code to see how difficult the implementation is. But my feeling is that it shouldn't be that bad once we properly define the semantics

[caleb531]

@EduardoGoulart1 That makes sense. I guess personally, I have been struggling with how to implement this in a way that produces semantically-correct results, so if you have an idea, then I would be grateful if you could take a stab at it.

For example, the current DFA.union method produces a DFA where each state is a permutation of each DFA's set of states (e.g. ('q0', 'p2')). So in the case of a partial DFA, each permutation state (a tuple) could contain None (e.g. ('q0', None) or (None, 'p2')). Now is this cross product algo for partial DFAs as simple as excluding any states/transitions where None is one or more of the tuple values? Or is it more complicated than that? I personally don't know.

cc @eliotwrobson

[EduardoGoulart1]

@EduardoGoulart1 That makes sense. I guess personally, I have been struggling with how to implement this in a way that produces semantically-correct results, so if you have an idea, then I would be grateful if you could take a stab at it.

For example, the current DFA.union method produces a DFA where each state is a permutation of each DFA's set of states (e.g. ('q0', 'p2')). So in the case of a partial DFA, each permutation state (a tuple) could contain None (e.g. ('q0', None) or (None, 'p2')). Now is this cross product algo for partial DFAs as simple as excluding any states/transitions where None is one or more of the tuple values? Or is it more complicated than that? I personally don't know.

cc @eliotwrobson

Just FYI: I can't find the time to work on this feature right now (I am very busy these next 2 weeks). But I didn't forget this issue. This is definitely on my TODO list because it's a feature that I need

[eliotwrobson]

@EduardoGoulart1 did you have a chance to take a further look at the issues outlined here? I think things are starting to move towards a v8 release, and it would be great to have a resolution to this issue included there.

[EduardoGoulart1]

Yes! My paper deadline passed last Thursday so I am officially a free man. I will work on it over the following days but first implement just a few operators...

[eliotwrobson]

Just a note @EduardoGoulart1 the from_finite_language should be able to take advantage of the allow_partial behavior. You just have to have the function take this in as a parameter and at the end and omit the creation of the trap state.

[eliotwrobson]

@EduardoGoulart1 as I understand it, https://github.com/caleb531/automata/pull/139 was merged in preparation for some of the topics discussed in this issue. Do you think you'll have time to do some follow-up work soon? I think we're moving toward a v8 release before too long and it would be great to have these changes included.

[EduardoGoulart1]

@EduardoGoulart1 as I understand it, #139 was merged in preparation for some of the topics discussed in this issue. Do you think you'll have time to do some follow-up work soon? I think we're moving toward a v8 release before too long and it would be great to have these changes included.

When is V8 due?

[caleb531]

@EduardoGoulart1 I have no specific due date in mind — I typically publish new major releases when they feel ready. But I am in agreement with @eliotwrobson that it would be great to have this as part of v8.

If a specific timeline would be helpful, I might say it would be great to have this particular task implemented/merged within the next couple weeks, perhaps.

[EduardoGoulart1]

@EduardoGoulart1 I have no specific due date in mind — I typically publish new major releases when they feel ready. But I am in agreement with @eliotwrobson that it would be great to have this as part of v8.

If a specific timeline would be helpful, I might say it would be great to have this particular task implemented/merged within the next couple weeks, perhaps.

I was halfway done with the implementation but had to stop. It is realistic to say that I can finalize it for next week (07th May). Would that work?

[eliotwrobson]

@EduardoGoulart1 that would be awesome! Feel free to put up a work in progress PR even if you have work that's incomplete, it makes the review process go a bit faster if we can start looking at it earlier..

[eliotwrobson]

Linking this paper here so I don't lose it: https://arxiv.org/abs/0802.2826

This paper is a more abstract description of Valmari's algorithm for minimizing partial DFAs. It should be easier to read and implement than the paper with the C++ code. Once we get a first iteration of partial DFA support, it would be awesome if we could add this algorithm as the default for minimizing partial DFAs (should be much faster over large alphabets).

[EduardoGoulart1]

Linking this paper here so I don't lose it: https://arxiv.org/abs/0802.2826

This paper is a more abstract description of Valmari's algorithm for minimizing partial DFAs. It should be easier to read and implement than the paper with the C++ code. Once we get a first iteration of partial DFA support, it would be awesome if we could add this algorithm as the default for minimizing partial DFAs (should be much faster over large alphabets).

Oh great I was looking for a better explanation to his original algorithm... Yes definitely makes sense to implement that algorithm instead

[eliotwrobson]

Closing now that #147 was merged to develop, and will be a part of the v8 release!