More functionality for DPDA

[Tagl]

My next focus was gonna be a little bit on DPDAs. I've started implementing enumeration and iteration.
Are there any specific operations that you're particularly interested in prioritizing?
Some of them may not have any known efficient algorithm (regularity of language) or may even be undecidable (although that's more common for the nondeterministic version).
@caleb531 @eliotwrobson

Some ideas:

• Enumeration
• Iteration
• Union with regular language
• Intersection with regular language
• Complement
• Equivalence
• Emptiness
• Regularity (exponential complexity)

[eliotwrobson]

@Tagl I'm not an expert on these operations (my domain of knowledge and usage on stuff in the package is mostly limited to regular languages), but these all seem reasonable. I guess the operations with regular languages are the most interesting to me (due to what I said previously).

[caleb531]

@Tagl Ideally, enumeration/iteration is something I'd personally love to see implemented for all automaton types. But I understand if we start running against the wall of feasibility.

Equivalence would also be great to have, but I understand if there are challenges with that. The order you listed other operations seems like a fine priority for me (e.g. care more about union than complement, and more about complement than emptiness).

[caleb531]

@Tagl (cc @eliotwrobson) I think I'd actually like to save any DPDA work for a post-v7 release. I am starting to get eager to release v7 soon, with all of its substantial improvements to the library.

[eliotwrobson]

@caleb531 I'm inclined to agree. We've merged in a ton of changes that significantly overhaul large parts of the library. I think it would be good to release and get feedback on the existing changes.

[Tagl]

I think I'd actually like to save any DPDA work for a post-v7 release. I am starting to get eager to release v7 soon, with all of its substantial improvements to the library.

No worries, this is gonna take a long time.

[eliotwrobson]

Since there was mention of having the __iter__ working for all automaton types in the discussion here, I'll say that I'm not sure about any of the PDAs beyond the DPDA, but this is definitely infeasible for TMs (in fact, I don't think there are any nontrivial algorithms for TMs).

[caleb531]

@eliotwrobson Just want to comment and say that's fine with me! If a feasible algorithm doesn't exist, then it is what it is.