Successor and predecessor functions

[Tagl]

@caleb531 Here's a draft of the algorithm, a lot of optimizations to be made regarding precomputation.

[coveralls]

Coverage remained the same at 100.0% when pulling b3af8799d72f992562dc8607bf2752d570d6a1c5 on Tagl:succ-and-pred into 4bc41aae1f3c786a36e78513beb411b8363a3438 on caleb531:develop.

[Tagl]

@eliotwrobson I just realized that a matching predecessor may potentially need to return an infinite string so can't do that one. For example DFA.universal_language({'0', '1'}).predecessor('1') would have to return 01111...

[eliotwrobson]

@Tagl Yes, there's some subtlety to this, especially dealing with infinite languages. You might just want to say that this is only for DFAs over finite languages. There's some discussion of this issue in that original blog post, apparently you can always make it return a prefix of the lexicographically next thing? I think sticking with finite languages may be the least confusing way to go.

[Tagl]

Successor works fine for infinite languages since it yields in preorder. Predecessor would follow a similar DFS process but yields postorder and therefore may never yield. If we really want to include a predecessor function along with the successor function then there are a number ways we could do it:

1. Implement it like the successor and allow library users to shoot themselves in the foot with infinite iteration
2. 1. but raise exception if language is infinite, very restrictive but still useful in some cases.
3. 1. but raise exception if a cycle is required to produce the predecessor.
4. We implement a Word type which can be infinite in length and is made up of finite and/or infinite parts. We can then use this as input and output of these functions. However, this is a lot more work so perhaps not worth the effort.

[eliotwrobson]

I'm kindof leaning toward option 2, since this seems the least confusing for an end user.

[Tagl]

I'm kindof leaning toward option 2, since this seems the least confusing for an end user.

I think 2 is a good start and easier to implement. Can be updated to 3 later on if deemed necessary.

[caleb531]

We already have potentially-infinite iteration in DFA.__iter__, don't we? So I'm not sure if Option 1 is as bad as it sounds.

I suppose a fifth option might be to add a keyword arg that controls the behavior—whether an exception is raised, or whether yielding is infinite.

[Tagl]

We already have potentially-infinite iteration in DFA.__iter__, don't we? So I'm not sure if Option 1 is as bad as it sounds.

I suppose a fifth option might be to add a keyword arg that controls the behavior—whether an exception is raised, or whether yielding is infinite.

I should clarify, this would be infinite iteration without any results because the search algorithm would keep adding a token. The while loop would iterate forever without yielding once because for each potential predecessor that it does find, there is gonna be one that is longer and therefore is lexicographically larger. Therefore in this case it will never be a useful function, even though it is trying to do exactly what is asked of it, that's why I believe we should raise an exception, but it would be more practical if that only happens when absolutely necessary.

The infinite iteration in __iter__ is quite different will eventually find a result and yield it. So it can generate an infinite amount of data but it will always yield the next result within a finite amount of time.

[caleb531]

@Tagl I see. Then yeah, if we can identify the never-yielding case ahead of time, then I'd say throw an exception (probably a specialized one).

[caleb531]

@Tagl (cc @eliotwrobson) What is the status of this PR? Does Option 2 still need to be implemented?

If possible, I would kindly ask if we could convert to drafts any PRs that are not yet ready for my review. That helps me out a lot.

[Tagl]

My mistake, I thought I had made it a draft originally

I will change it back once I've implemented predecessor with option 2

[Tagl]

@caleb531 @eliotwrobson Ready for review

[caleb531]

@Tagl Just an update: this PR is looking pretty good currently, I've just been mulling over the effort required to make ignore_rejection a standard parameter for read_input_stepwise on all automaton types. Most of that centers around when None should be yielded, or if that is even necessary (e.g. in the case of nondeterminism).

But after reviewing the other automaton classes just now, that should be doable (or doesn't even seem to be an issue thanks to the nondeterminism in some of those types). So I plan to be merging this PR shortly.

[Tagl]

Might be a bit out of scope though, maybe better to just adapt this PR to the current implementation and then we can discuss the change to the API better later

On Tue, Nov 8, 2022, 00:12 Caleb Evans @.***> wrote:

@Tagl https://github.com/Tagl Just an update: this PR is looking pretty good currently, I've just been mulling over the effort required to make ignore_rejection a standard parameter for read_input_stepwise on all automaton types. Most of that centers around when None should be yielded, or if that is even necessary (e.g. in the case of nondeterminism).

But after reviewing the other automaton classes just now, that should be doable (or doesn't even seem to be an issue thanks to the nondeterminism in some of those types). So I plan to be merging this PR shortly.

— Reply to this email directly, view it on GitHub https://github.com/caleb531/automata/pull/92#issuecomment-1306401451, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB2ZBKXC46FKCVQHXEUTXXDWHGLHHANCNFSM6AAAAAARSCH6RM . You are receiving this because you were mentioned.Message ID: @.***>

[caleb531]

@Tagl Well, to clarify—I would not be standardizing ignore_rejection in this PR, as I agree that it is out of scope. I would be implementing that after this PR is merged.