Non-well-founded sets seem to be grammars from a CS point of view. As soon as you admit the Kleene-star '*' operator you have potential infinity. If you allow c

Non-well-founded sets seem to be grammars from a CS point of view. As soon as you admit the Kleene-star '*' operator you have potential infinity. If you allow circular grammar definitions, then you are specifying non-well-founded-sets. When parsing finite structures, it just so happens that the parsing terminates, but it's easy to extend to open-ended (potentially infinite) streams. There are even type system constructs and language expressions for them, but only executable in lazy languages, or systems open to external input. CS has also made theoretical progress, perhaps the most surprising is differentiating regular expressions and other regular datatypes: http://en.wikipedia.org/wiki/Brzozowski_derivative http://en.wikipedia.org/wiki/Brzozowski_derivative http://blog.sigfpe.com/2005/05/derivatives-of-regular-expressions.html http://blog.sigfpe.com/2005/05/derivatives-of-regular-expres... http://strictlypositive.org/diff.pdf http://strictlypositive.org/diff.pdf I also recommend 'The Liar' by Barwise & Etchemendy.