Frank Stephan: On block pumpable languages

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, Wednesday 10 Aug 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: On block pumpable languages


Call a language L block pumpable iff there is a constant p>1 such
that for every splitting of a word in the language L into p+1 blocks,
one can find a subword consisting of an interval of the interior blocks
such that each modified word obtained by repeating or omitting this
subword is also in the language L. Such subwords are called pump.
Ehrenfeucht, Parikh and Rozenberg showed that a language is regular
iff the language and its complement are both block pumpable. The aim
of this paper is to provide some evidence that beyond this
characterisation, block pumpable languages are a notion which is
interesting in its own right. It will be shown that block pumpable
languages satisfy natural closure properties: The intersection of
two block pumpable languages is block pumpable, the union of two
block pumpable languages is block pumpable and the image of block
pumpable languages under a transduced mapping is block
pumpable. However, block pumpable languages are not closed under
complement and Kleene star. Furthermore, block pumpable languages
satisfy the condition that one can pump them several times, that
is, for each k and each sufficiently large number p(k) and
every splitting of a word into p(k) parts, one can find k disjoint
pumps in the word which can be pumped independently. The growth-rate
(number of words up to given length) of every non-regular pumpable
language is exponential. One can define block pumpable relations
and structures and show that the existential theory of such a
structure is decidable and that an alternation of quantifiers
destroys decidability.

The talk follows the paper “On block pumpable languages”
by Christopher Chak, Rusins Freivalds, Frank Stephan
and Henrietta Tan, which contains contains results from the FYP
of Christopher Chak and Henrietta Tan; the paper appeared in
Theoretical Computer Science 609:272-285, 2016. Furthermore, the talk
also presents results from the FYP of Jonathan Sung. The talk had
been presented at the conference “Computability, Randomness and
Applications” in Luminy, France.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.