Automata and Logics over Signals

Fabrice Chevalier, Deepak D'Souza, Raj Mohan Matteplackel and Pavithra Prabhakar

We extend some of the classical connections between automata and logic due to Buchi and McNaughton and Papert, to languages of finitely varying functions or "signals". In particular we introduce a natural class of automata for generating finitely varying functions called ST-NFA's, and show that it coincides in terms of language-definability with a natural monadic second-order logic interpreted over finitely varying functions. We also identify a "counter-free" subclass of ST-NFA's which characterize 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 (MTL).

Modern Applications of Automata Theory, 2012
Download: BIB PS PDF