TY - GEN
T1 - An algebraic characterization of strictly piecewise languages
AU - Fu, Jie
AU - Heinz, Jeffrey
AU - Tanner, Herbert G.
PY - 2011
Y1 - 2011
N2 - This paper provides an algebraic characterization of the Strictly Piecewise class of languages studied by Rogers et al. 2010. These language are a natural subclass of the Piecewise Testable languages (Simon 1975) and are relevant to natural language. The algebraic characterization highlights a similarity between the Strictly Piecewise and Strictly Local languages, and also leads to a procedure which can decide whether a regular language L is Strictly Piecewise in polynomial time in the size of the syntactic monoid for L.
AB - This paper provides an algebraic characterization of the Strictly Piecewise class of languages studied by Rogers et al. 2010. These language are a natural subclass of the Piecewise Testable languages (Simon 1975) and are relevant to natural language. The algebraic characterization highlights a similarity between the Strictly Piecewise and Strictly Local languages, and also leads to a procedure which can decide whether a regular language L is Strictly Piecewise in polynomial time in the size of the syntactic monoid for L.
UR - https://www.scopus.com/pages/publications/79955763963
U2 - 10.1007/978-3-642-20877-5_26
DO - 10.1007/978-3-642-20877-5_26
M3 - Conference contribution
AN - SCOPUS:79955763963
SN - 9783642208768
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 252
EP - 263
BT - Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings
T2 - 8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
Y2 - 23 May 2011 through 25 May 2011
ER -