In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. It has been conjectured that a necessary condition for a regular language L to be a splicing language is that L must have a constant in the Schützenberger sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. Using constants of the corresponding languages, we also provide properties of transitive automata and path-automata.

Bonizzoni, P., Jonoska, N. (2015). Existence of constants in regular splicing languages. INFORMATION AND COMPUTATION, 242, 340-353 [10.1016/j.ic.2015.04.001].

Existence of constants in regular splicing languages

BONIZZONI, PAOLA
;
2015

Abstract

In spite of wide investigations of finite splicing systems in formal language theory, basic questions, such as their characterization, remain unsolved. It has been conjectured that a necessary condition for a regular language L to be a splicing language is that L must have a constant in the Schützenberger sense. We prove this longstanding conjecture to be true. The result is based on properties of strongly connected components of the minimal deterministic finite state automaton for a regular splicing language. Using constants of the corresponding languages, we also provide properties of transitive automata and path-automata.
Articolo in rivista - Articolo scientifico
Information Systems; Computational Theory and Mathematics; Theoretical Computer Science; Computer Science Applications1707 Computer Vision and Pattern Recognition
English
2015
242
340
353
reserved
Bonizzoni, P., Jonoska, N. (2015). Existence of constants in regular splicing languages. INFORMATION AND COMPUTATION, 242, 340-353 [10.1016/j.ic.2015.04.001].
File in questo prodotto:
File Dimensione Formato  
information-compu.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 536.86 kB
Formato Adobe PDF
536.86 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/97882
Citazioni
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
Social impact