Automata and logics over finitely varying functions

Annals of Pure and Applied Logic 161 (3):324-336 (2010)
  Copy   BIBTEX

Abstract

We extend some of the classical connections between automata and logic due to Büchi [5] and McNaughton and Papert [12] to languages of finitely varying functions or “signals”. In particular, we introduce a natural class of automata for generating finitely varying functions called ’s, and show that it coincides in terms of language definability with a natural monadic second-order logic interpreted over finitely varying functions Rabinovich [15]. We also identify a “counter-free” subclass of ’s which characterise the first-order definable languages of finitely varying functions. Our proofs mainly factor through the classical results for word languages. These results have applications in automata characterisations for continuously interpreted real-time logics like Metric Temporal Logic Chevalier et al. [6] and [7].

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 103,748

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
Second-order logic on equivalence relations.Georgi Georgiev & Tinko Tinchev - 2008 - Journal of Applied Non-Classical Logics 18 (2-3):229-246.
Relating word and tree automata.Orna Kupferman, Shmuel Safra & Moshe Y. Vardi - 2006 - Annals of Pure and Applied Logic 138 (1):126-146.
On Relation Between Linear Temporal Logic and Quantum Finite Automata.Amandeep Singh Bhatia & Ajay Kumar - 2020 - Journal of Logic, Language and Information 29 (2):109-120.
Simple monadic theories and partition width.Achim Blumensath - 2011 - Mathematical Logic Quarterly 57 (4):409-431.
Topological completeness for higher-order logic.S. Awodey & C. Butz - 2000 - Journal of Symbolic Logic 65 (3):1168-1182.

Analytics

Added to PP
2017-02-19

Downloads
5 (#1,785,961)

6 months
1 (#1,598,919)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references