Existence of constants in regular splicing languages.

Area of Science:

• Formal Language Theory
• Theoretical Computer Science
• Automata Theory

Background:

• Finite splicing systems are crucial in formal language theory, yet their characterization remains an open problem.
• A key conjecture posits that regular splicing languages must possess a Schutzenberger constant.

Purpose of the Study:

• To rigorously prove the conjecture that regular languages must have a Schutzenberger constant to be splicing languages.
• To leverage this proof for a deeper understanding of splicing language characterization.

Main Methods:

• Analysis of properties of strongly connected components within the minimal deterministic finite state automaton (DFA) of regular splicing languages.
• Utilizing the concept of constants of corresponding languages.
• Investigating properties of transitive automata and path automata.

Main Results:

• The longstanding conjecture is proven true: a necessary condition for a regular language to be a splicing language is the existence of a Schutzenberger constant.
• The study establishes a link between the properties of minimal DFAs' strongly connected components and the language's splicing capabilities.

Conclusions:

• The characterization of regular splicing languages is advanced by confirming the necessity of Schutzenberger constants.
• The findings provide new insights into the structure of automata related to splicing languages, including transitive and path automata.