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.
Articolo in rivista - Articolo scientifico
splicing language
English
2005
340
2
349
363
none
Bonizzoni, P., Mauri, G. (2005). Regular splicing languages and subclasses. THEORETICAL COMPUTER SCIENCE, 340(2), 349-363 [10.1016/j.tcs.2005.03.035].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/1895
Citazioni
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 13
Social impact