Welcome to MathOverflow

Question

2

1

A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of strings of $\Sigma^*$.

One can then define a regular predicate over $\Sigma^*$

as an n-ary relation on $\Sigma^*$ such that by suitably coding n-tuples of words as single words (see for example Blumensath and Gradel) one obtains a regular language (over a new alphabet). If $R(x,y)$ is a regular binary predicate, what can be the status of the unary predicate $\exists x.R(x,y)$? (again regular, decidable, r.e., or what else?)

flag	asked Jun 28 at 16:14 Alberto 65●3

3

The set '$\{ y : (\exists x)[R(x,y)] \}$' is also regular. This is a consequence of the more general fact that if $S$ is a regular set, then any set first-order definable from $S$ is regular. Indeed, all sets that are definable from $S$ in a first-order manner together with the quantifier "there exists infinitely many" and the quantifiers "there exist $k$-many mod $n$" is regular. – Asher M. Kach Jun 28 at 16:30

2

Asher, I would recommend you to post your comment as an answer, especially if you could sketch the proof (e.g. by mentioning how the pumping lemma allows you to cut the existential search down). – Joel David Hamkins Jun 28 at 19:04

Thank you for the answer. I don't know why I've never seen this kind of closure property being treated in a formal language/computability theory course, while it is always explained for the case of recursively enumerable predicates. @Joel: thanks for your point, I would like to see a sketch of the proof. Can it be found in some textbook? I think it would be nice to show this to students. – Alberto Jun 28 at 21:42

Can one not prove this from the equivalence of MSO with regular languages? – Benjamin Steinberg Jun 29 at 1:59

I looked up on google the issue of MSO definability of regular languages. The result which is reported everywhere (that of Buchi) is based on an interpretation of individual variables as natural numbers and of set-variables as sets of natural numbers (to be understood as positions in words). The semantics is then $ w,I,J \models \phi$ where $w$ is a word, $I$ is a valuation of individual variables, $J$ is a valuation of set-variables and $\phi$ is a formula. I was referring to a straightforward interpretation of individual variables as words. Are the answers still valid? – Alberto Jun 29 at 9:11

show 1 more comment

Alberto · Accepted Answer · 2012-06-29 15:56:26Z UTC

I think I found a reference for the answer. It should be in the following paper:

S. Eilemberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by n-tape automata, Journal of Algebra, vol. 13, (1969), pp. 447-464.

Unfortunately I cannot download it from the internet.

Existential quantification over regular predicates

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.