First-order Cost Logics and Automatic Structures

We provide new characterizations of the class of regular cost functions (Colcombet 2009) in terms of different quantitative first-order logics. This result extends a classical result connecting the regular languages with the languages definable by a first-order formula over the infinite (binary) tree of finite words with equal length predicate. Furthermore, we use these results to identify a structure that is complete for the class of resource automatic structures and investigate approaches how resource (tree) automatic structures can be used to obtain decidability results for costWMSO and WMSO+U as well. Parts of this are joint work with Simon Leßenich, Christof Löding and Amaldev Manuel and will appear in MFCS 2014 as Definability and Transformations for Cost Logics and Automatic Structures

Authors

• Martin Lang

Keywords

No keywords are indexed for this paper.