Google Analytics

Saturday, March 01, 2003

Cardinality Theorem for Regular Languages?

Till Tantau told me an interesting open question at STACS. Kummer proved the following Cardinality Theorem for the recursive sets: Fix a constant k and set A. If there is a recursive function f such that for all x1,...,xk, f(x1,...,xk) is a number between 0 and k that is not |{x1,...,xk}∩A| then A is recursive. The same is not true for polynomial time but is open for regular languages. Details and some partial results in Tantau's paper.

No comments:

Post a Comment