Hi,
DFS algorithms can nevertheless gain some completness
power on rational trees when paired with loop checking.
Like @kuniaki.mukai was using in compare_with_stack/3.
They might be not as good as HK though.
You find a DFA subset and equality relation here,
implemented via DFS algorithms using a visitor set:
def find_equiv_counterexample(dfa_a, dfa_b):
# Symmetric difference: strings accepted by exactly one DFA
return find_word(dfa_a ^ dfa_b)
def find_subset_counterexample(smaller, bigger):
# Intersection of "smaller" with the complement of "bigger"
return find_word(~bigger & smaller)
https://pypi.org/project/dfa/
The later results in ordering DFAs by a partial order
and not by a total order. The project has also a DFA
minimization algorithm. But I didn’t get my head around
yet implementing it,
and I don’t know whether @kuniaki.mukai implemented
the DFA minimization algorithm that has supposedly
O(N log(N)) complexity.
Bye
Mild Shock schrieb:
Hi,
This is a nice confusion of the highest order.
observations on the decidability
Well in summary the existence of a pretest (==)/2
makes Mercio's decidable. Equality on rational trees
is decidable, even if it comes in disguise as Mercio’s
mathematical definition, which gives a total order
which is unfortunately not a natural order:
A=B :⟺ A' =lex B'
A<B :⟺ A' <lex B'
Natural order of rational trees?
https://math.stackexchange.com/a/210730
Why is Mercio’s mathematical definition of equality
decidable? Because it is semantically equivalent to
bisimulation as implemented in (==)/2 , and decidable
is a semantic notion:
Decidability (logic)
In logic, a true/false decision problem is decidableif there
exists an effective method for deriving the correct answer.
Decidability (logic) - Wikipedia
So if you talk about semi-decidable, decidable etc..
its always about the existence of an algorithm in
the large space of effective method according to
the Church hypothesis.
If you want to talk about a particular algorithm
you would use the terminology “incomplete”. Like for
example DFS algorithms are “incomplete” compared to
BFS algorithms on certain problems.
Bye
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)