search

zhilin02 / slreplace

1 stars 3 forks source link

Write up reduction from k-reversal-bounded to one-way with reverse #17

Closed matthewhague closed 6 years ago

matthewhague commented 6 years ago

Implementing the solution proposed in #13.

matthewhague commented 6 years ago

Begun in 11fc65df8c01c66fd7daf92063f6a47a033adf15, ccc255343c538fa68c438319e3c54bce08cb9eaf, 347592b5a61630390e7fd5f69acb0b4b615d356f.

matthewhague commented 6 years ago

@zhilin02 wrote up an informal description. Will try to find time to write it formally. Let me know what you think.

matthewhague commented 6 years ago

@zhilin02 btw, i noticed the appendix section began by promising a proof that one-way+reverse is in EXPSPACE. I'm not sure what you had in mind for this (in additional to what's already in the main body). Does anything need to be added?

zhilin02 commented 6 years ago

On 27/1/2018 12:07 AM, matthewhague wrote:

@zhilin02 https://github.com/zhilin02 btw, i noticed the appendix section began by promising a proof that one-way+reverse is in EXPSPACE. I'm not sure what you had in mind for this (in additional to what's already in the main body). Does anything need to be added?

No, the appendix was written before the current version of the main text.

If the main text already shows this, then we do not need prove it again in appendix.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/zhilin02/slreplace/issues/17#issuecomment-360826868, or mute the thread https://github.com/notifications/unsubscribe-auth/AKfH1us-dBLPTlFVPzKz0SJnX11nfNtvks5tOfgsgaJpZM4RudYZ.

zhilin02 commented 6 years ago

Briefly browsed, seems nice, you use states instead of tags 1, 2, ... to mark the starting points of passes.

I think it is simpler, just go ahead, please.

On 26/1/2018 11:40 PM, matthewhague wrote:

@zhilin02 https://github.com/zhilin02 wrote up an informal description. Will try to find time to write it formally. Let me know what you think.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/zhilin02/slreplace/issues/17#issuecomment-360818885, or mute the thread https://github.com/notifications/unsubscribe-auth/AKfH1kRFgpvOjULtSIytIJVPW9W30JNmks5tOfHkgaJpZM4RudYZ.

matthewhague commented 6 years ago

Thanks. Your tagging approach was a lot nicer than the truncating i had thought of previously.

I will hold off on a formal definition of the automata: i'm not sure it's necessary since (i think) it's clear how the automata work and that they can be defined in a compact way.

I guess at least a proposition should be added to say the reduction keeps things the same. I will concentrate on the intro example first.

matthewhague commented 6 years ago

Todo: