文章基本信息

标题：Logics with rigidly guarded data tests
本地全文：下载
作者：Gabriele Puppis ; Thomas Colcombet ; Clemens Ley 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2015
卷号：11
期号：3
页码：1
DOI：10.2168/LMCS-11(3:10)2015
出版社：Technical University of Braunschweig
摘要：The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. Following Buchi's approach, we introduce a variant of monadic second-order logic with data equality tests that captures precisely the data languages recognizable by orbit finite data monoids. We also establish, following this time the approach of Schutzenberger, McNaughton and Papert, that the first-order fragment of this logic defines exactly the data languages recognizable by aperiodic orbit finite data monoids. Finally, we consider another variant of the logic that can be interpreted over generic structures with data. The data languages defined in this variant are also recognized by unambiguous finite memory automata.
其他关键词：Data Languages, Orbit-finite Data Monoids, Rigidly Guarded MSO, FOdefinability, Finite Memory Automata.