Star free expressions over the reals

Authors
Rabinovich, A
Citation
A. Rabinovich, Star free expressions over the reals, THEOR COMP, 233(1-2), 2000, pp. 233-245
Citations number
12
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
233
Issue
1-2
Year of publication
2000
Pages
233 - 245
Database
ISI
SICI code
0304-3975(20000228)233:1-2<233:SFEOTR>2.0.ZU;2-M
Abstract
An interpretation of star free expressions over the reals is provided. The expressive power of star free expressions is compared to the expressive pow er of monadic first-order logic of order over the reals. It is proved that these formalisms have the same expressive power. This result provides a gen eralization of the classical McNaughton-Papert theorem (1971) from the fini te orders to the order of the reals. (C) 2000 Elsevier Science B.V. All rig hts reserved.