Name
Abstract | ||
|---|---|---|
We extend some of the classical connections between automata and logic due to Büchi (1960) [5] and McNaughton and Papert (1971) [12] 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 Rabinovich (2002) [15]. We also identify a “counter-free” subclass of ST-NFA’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 (MTL) Chevalier et al. (2006, 2007) [6], [7]. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.apal.2009.07.007 | Annals of Pure and Applied Logic |
Keywords | Field | DocType |
03B44,03B10,03D05 | Discrete mathematics,Automaton,Natural class,Mathematical proof,First-order logic,Temporal logic,Mathematics,Intermediate logic,MathML,Monad (functional programming) | Journal |
Volume | Issue | ISSN |
161 | 3 | 0168-0072 |
Citations | PageRank | References |
0 | 0.34 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabrice Chevalier | 1 | 126 | 7.32 |
| Deepak D’Souza | 2 | 55 | 3.25 |
| M. Raj Mohan | 3 | 4 | 1.49 |
| Pavithra Prabhakar | 4 | 219 | 25.69 |