✦ LIBER ✦

Star free expressions over the reals

✍ Scribed by Alexander Rabinovich

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 116 KB
Volume: 233
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)00050-4

No coin nor oath required. For personal study only.

✦ Synopsis

An interpretation of star free expressions over the reals is provided. The expressive power of star free expressions is compared to the expressive power of monadic ÿrst-order logic of order over the reals. It is proved that these formalisms have the same expressive power. This result provides a generalization of the classical McNaughton-Papert theorem (1971) from the ÿnite orders to the order of the reals.

📜 SIMILAR VOLUMES

Counting problems over the reals

✍ Klaus Meer 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 152 KB

In this paper we introduce a notion of counting problems over the real numbers. We follow the approaches of Blum et al. (1998) for computability over R and of Gr adel and Meer (1996) for descriptive complexity theory in this setting and give a complete characterization of such problems by logical me

Machines Over the Reals and Non-Uniformi

Machines Over the Reals and Non-Uniformity

✍ Felipe Cucker 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 908 KB

## Abstract We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet ‐ say {0,1} ‐ which can be decided by real machines working under sev

Computing over the reals with addition a

Computing over the reals with addition and order

✍ P. Koiran 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 881 KB

Pixley-Roy spaces over subsets of the re

Pixley-Roy spaces over subsets of the reals

✍ Peg Daniels 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 958 KB

Analog computers and recursive functions

Analog computers and recursive functions over the reals

✍ Daniel Silva Graça; José Félix Costa 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 235 KB

In this paper we show that Shannon's general purpose analog computer (GPAC) is equivalent to a particular class of recursive functions over the reals with the flavour of Kleene's classical recursive function theory. We first consider the GPAC and several of its extensions to show that all these mod

On sparseness and Turing reducibility ov

On sparseness and Turing reducibility over the reals

✍ Felipe Cucker 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 517 KB

We prove some results about existence of NP-complete and NP-hard (for Turing reductions) sparse sets on different settings over the real numbers.