2014/05/22 by Stefano Crespi Reghizzi, Pierluigi San Pietro
Computer Science · #cs.FL
paper · pdf · doi:10.4204/eptcs.151.15
published as EPTCS 151, 2014, pp. 216-230 · In Proceedings AFL 2014, arXiv:1405.5272
arxiv created 2014/05/22 · arxiv updated 2014/05/23
Commutative languages with the semilinear property (SLIP) can be naturally recognized by real-time NLOG-SPACE multi-counter machines. We show that unions and concatenations of such languages can be similarly recognized, relying on -- and further developing, our recent results on the family of consensually regular (CREG) languages. A CREG language is defined by a regular language on the alphabet that includes the terminal alphabet and its marked copy. New conditions, for ensuring that the union or concatenation of CREG languages is closed, are presented and applied to the commutative SLIP languages. The paper contributes to the knowledge of the CREG family, and introduces novel techniques for language composition, based on arithmetic congruences that act as language signatures. Open problems are listed.