FC is a first-order logic that reasons over all factors of a finite word using concatenation, and can define non-regular languages like that of all squares (ww). In this paper, we establish that there are regular languages that are not FC-definable. Moreover, we give a decidable characterization of the FC-definable regular languages in terms of algebra, automata, and regular expressions. The latter of which is natural and concise: Star-free generalized regular expressions extended with the Kleene star of terminal words.
翻译：FC是一种一阶逻辑，它通过连接运算对有限词的所有因子进行推理，并能定义非正则语言（如所有平方词ww构成的集合）。本文证明存在不是FC-可定义的正则语言。此外，我们基于代数理论、自动机理论和正则表达式，给出了FC-可定义正则语言的可判定刻画。其中基于正则表达式的刻画尤为自然简洁：即允许对终结词进行克林星运算的星号自由广义正则表达式。
相关内容
FC：Financial Cryptography and Data Security。
Explanation：金融密码与数据安全。
Publisher：Springer。
SIT： http://dblp.uni-trier.de/db/conf/fc/
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员