The decision problem for some logics for finite words on infinite alphabets |
| |
Authors: | Ch. Choffrut S. Grigorieff |
| |
Affiliation: | (1) LIAFA, Université Paris 7 & CNRS 2, Paris, France |
| |
Abstract: | This paper is a follow-up to a previous paper where the logical characterization of n-ary synchronous relations due to Eilenbeig, Elgot, and Shepherdson was investigated in the case where the alphabet has infinitely many letters. Here we show that modifying one of the predicates leads to a completely different picture for infinite alphabets, though it does not change the expressive power for finite alphabets. Indeed, roughly speaking, being able to express the fact that two words end with the same symbol leads to an undecidable theory, already for the Σ2 fragment. Finally, we show that the existential fragment is decidable. Bibliography: 19 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 100–119. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|