TY - GEN
T1 - On languages Piecewise testable in the strict sense
AU - Rogers, James
AU - Heinz, Jeffrey
AU - Bailey, Gil
AU - Edlefsen, Matt
AU - Visscher, Molly
AU - Wellcome, David
AU - Wibel, Sean
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/78649765832
U2 - 10.1007/978-3-642-14322-9_19
DO - 10.1007/978-3-642-14322-9_19
M3 - Conference contribution
SN - 3642143210
SN - 9783642143212
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 255
EP - 265
BT - The Mathematics of Language - 11th Biennial Conference, MOL 11, Revised Selected Papers
T2 - 11th Biennial Conference on Mathematics of Language, MOL 11
Y2 - 20 August 2009 through 21 August 2009
ER -