On Languages Piecewise Testable in the Strict Sense
On Languages Piecewise Testable in the Strict Sense
复制标题
论严格意义上的分段可测语言
DOI：
10.1007/978-3-642-14322-9_19
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Sean Wibel
中科院分区：
文献类型：
--
作者：
J. Rogers;Jeffrey Heinz;G. Bailey;Matt Edlefsen;M. Visscher;David Wellcome;Sean Wibel
在本文中，我们探讨了严格分段语言的类别，最初引入的是将Heinz [7] [7]的长距离语音模式描述为优先语言。我们提供一系列等效的抽象表征，讨论它们的基本属性，相对于其他众所周知的次级类别找到它们，并提供算法以在此处定义的语法和有限状态自动机之间转换，以及确定常规语言是否是正规语言的算法严格分段。
In this paper we explore the class of Strictly Piecewise languages, originally introduced to characterize long-distance phonotactic patterns by Heinz [7] as the Precedence Languages. We provide a series of equivalent abstract characterizations, discuss their basic properties, locate them relative to other well-known subregular classes and provide algorithms for translating between the grammars defined here and finite state automata as well as an algorithm for deciding whether a regular language is Strictly Piecewise.