3 ms·

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

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?

yeputons 5y ago
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.
- tgv 5y ago
  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.
_ZeD_ 5y ago
how do you get to have the pointer to the end? welcome to the "accidently quadratic" world :)
pwdisswordfish9 5y ago
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.

yeputons 5y ago

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.

tgv 5y ago
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.

_ZeD_ 5y ago

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

pwdisswordfish9 5y ago

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.