Recent developments in the theory of finite splicing systems have revealed surprising connections between long-standing notions in the formal language theory and splicing operation. More precisely, the syntactic monoid and Schützenberger constant have strong interaction with the investigation of regular splicing languages. This paper surveys results of structural characterization of classes of regular splicing languages based on the above two notions and discusses basic questions that motivate further investigations in this field. In particular, we improve the result in [6] that provides a structural characterization of reflexive symmetric splicing languages by showing that it can be extended to the class of all reflexive splicing languages: this is the larger class for which a characterization is known. © 2005 Elsevier B.V. All rights reserved.
Bonizzoni, P., Mauri, G. (2005). Regular splicing languages and subclasses. THEORETICAL COMPUTER SCIENCE, 340(2), 349-363 [10.1016/j.tcs.2005.03.035].
Regular splicing languages and subclasses
BONIZZONI, PAOLA;MAURI, GIANCARLO
2005
Abstract
Recent developments in the theory of finite splicing systems have revealed surprising connections between long-standing notions in the formal language theory and splicing operation. More precisely, the syntactic monoid and Schützenberger constant have strong interaction with the investigation of regular splicing languages. This paper surveys results of structural characterization of classes of regular splicing languages based on the above two notions and discusses basic questions that motivate further investigations in this field. In particular, we improve the result in [6] that provides a structural characterization of reflexive symmetric splicing languages by showing that it can be extended to the class of all reflexive splicing languages: this is the larger class for which a characterization is known. © 2005 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.