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

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:

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.