Summoning Cthulhu by Parsing HTML with Regular Expressions (2021)

Re:Summoning Cthulhu by Parsing HTML with Regular Expression... by cravingsleep on Saturday April 16, 2022 @05:10AM (#31050892)

As another example, we can look at the set of all palindromes. One way to check whether a string is a palindrome is to reverse it, and check that it is equal to its own reverse. This process requires storing a reversed copy of the string in memory. Since the string can be arbitrarily large, we require an arbitrarily large amount of memory. Any algorithm that I can come up with for determining whether a string is a palindrome runs into this same issue. By our rule of thumb, the set of palindromes is a non-regular language; this is indeed a fact which can be formally proved.

I'm pretty sure you can check if a string is a palindrome with O(1) space complexity? Just create a left pointer to the start of the string and a right pointer to the end and walk them towards the middle checking the chars they point to is equal each time?

[ Parent | on HN ]

Re:Summoning Cthulhu by Parsing HTML with Regular Expression... by yeputons on Saturday April 16, 2022 @05:23AM (#31050939)

That's not O(1), that's O(log n) memory, where `n` is the size of your string. You need `log n` bits to store the pointer. Granted, it's very limited for practical purposes, but you have to account for it in theoretical applications.

UPD: you can also say that you're actually writing a code for a Turing machine with two heads, and that would be ok. So, yeah, this is why the "you cannot write a constant-memory algorithm" definition is very hand-waving, one has to be extra careful with the model they're working in.

[ Parent | on HN ]

Re:Summoning Cthulhu by Parsing HTML with Regular Expression... by tgv on Saturday April 16, 2022 @05:44AM (#31051039)

If you have a symbol that cannot be in the input (an EOT token), I think you can write it in O(1). You just change the input when you're done checking the outer symbols. Takes extra time, though.

[ Parent | on HN ]

Re:Summoning Cthulhu by Parsing HTML with Regular Expression... by pwdisswordfish9 on Saturday April 16, 2022 @05:41AM (#31051028)

That requires you to have the entire string in memory, so it’s still Ω(n). Regular languages can be recognized using O(1) space and a single reading pointer into the string, without even storing it whole; you can process it in a streaming manner.

[ Parent | on HN ]

Re:Summoning Cthulhu by Parsing HTML with Regular Expression... by _ZeD_ on Saturday April 16, 2022 @05:24AM (#31050949)

how do you get to have the pointer to the end? welcome to the "accidently quadratic" world :)

[ Parent | on HN ]