Christian Sievers

colno in 1:17 ?

That seems fine

How is the matrix computed? How is the automaton computed?

How do you compute M*v? Do you use sparse matrices?

I'm not sure I need it, what is the problem?

Okay

@Anush Hi!

Good luck!

oh, I think that should be [[2,2],[0,2]]

what are you trying? This should be correct

yes. And the sparse representation doesn't directly allow 2 as entry, so has repetitions

both is possible, one just has to adapt the rest of the computation

(or from j to i, I never remember)

i-j-entry: how many ways to get from state i to j

This seems to be the transition table

How does memory usage compare to the GAP code?

I think they prefer to stay GAP-only. They have used code in other languages before, but this seems far outside its usual realm. They still might like to know about it, it's always good to have options.

How much memory did it take?

Yeah, it is amazing!

Yes. And taking v[initstate] is a short way to premultiply init, i.e. the 0-1 vector which identifies the initial state

The List/Sum thing is sparse matrix / vector multiplication

And List(l,x->f(x) returns a list of all the values of f(x)

@Anush Sum(l,x->f(x)) sums all the values of f(x) with x in l

@Anush i've seen your answer here

@Anush I see. Up to what length?

@Bubbler I guess you what to see this

@Anush What do you mean by "full answer"?

they'd have to transform the input

("this"=your suggestion)

This looks more like vectorisation than threads

Ah yes, that's right. I was thinking about 4 long running threads that would need to communicate about the reachable states they have found.

I don't think such a parallelisation could work in any reasonable way.

How long did it take?

@Anush Wow! Now what are you gonna do with it?

I know Sevi. Haven't thought about her for a long time.

Using gap format of course automatically gives consecutive state numbers.

@Anush You keep mentioning this Seviers person. I'd really like to get to know them.

I don't think it helps testing. It avoids just encoding the subset as number-as-bitset, but maybe that isn't a bad thing. I guess doing that helps less than I first thought.

@Anush What I would call "the subset construction" always has 2^n states, and is fast to compute wrt the size of the output. I guess you want the reachable part of it, or maybe any DFA that accepts the same language? In the first case, you can check correctness as suggested by @Bubbler. Also worth considering: are the states required to be numbers? Consecutive ones?

In other word: the automaton has read more of the left string than the first machine or the pseudocode algorithm would have read from it, so what was read too early is memorized in the state

(unless I also mixed it up in other places. I do get confused which I called L and which I called R)

less

About L_{c,w}, c is the current edit distance of the right word read so far, and the left word without the letters of w. It corresponds to a situation when the left reading head is behind the right one. It's exactly the same c as in the pseudocode

At the end, the reading head has passed the word and is behind it

I'm not sure what your question is. But note that head has two meanings here: head of a list: first element. And the reading head of a machine that operates with tapes.

@Anush tail(l)=bcd, behind the word: after d (if we agree to start at a), it's when we have worked through all the input

@Anush Checking that automata accept the same language is possible. I wonder if there would be any interesting answers that don't just call a library, especially if you make it a fastest-code challenge

@Anush Sure

@Anush Fixed.

@Anush I don't know what more to say than I did in my math.SE answer (except there is a bug in the pseudocode). NFA to DFA conversion is not needed for understanding the NFA.