Computation Theory
In the automata theory, a set of all palindromes in a given alphabet is a typical example of a language that is context-free, but not regular. This means that it is, in theory, impossible for a computer with a finite amount of memory to reliably test for palindromes. (For practical purposes with modern computers, this limitation would apply only to incredibly long letter-sequences.)
In addition, the set of palindromes may not be reliably tested by a deterministic pushdown automaton which also means that they are not LR(k)-parsable or LL(k)-parsable. When reading a palindrome from left-to-right, it is, in essence, impossible to locate the "middle" until the entire word has been read completely.
It is possible to find the longest palindromic substring of a given input string in linear time.
Read more about this topic: Palindrome
Famous quotes containing the words computation and/or theory:
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“No one thinks anything silly is suitable when they are an adolescent. Such an enormous share of their own behavior is silly that they lose all proper perspective on silliness, like a baker who is nauseated by the sight of his own eclairs. This provides another good argument for the emerging theory that the best use of cryogenics is to freeze all human beings when they are between the ages of twelve and nineteen.”
—Anna Quindlen (20th century)