Skip to Main content Skip to Navigation
Conference papers

State Complexity of Simple Splicing

Abstract : Splicing, as a binary word/language operation, was inspired by the DNA recombination under the action of restriction enzymes and ligases, and was first introduced by Tom Head in 1987. Splicing systems as generative mechanisms were defined as consisting of an initial starting set of words called an axiom set, and a set of splicing rules—each encoding a splicing operation—, as their computational engine to iteratively generate new strings starting from the axiom set. Since finite splicing systems (splicing systems with a finite axiom set and a finite set of splicing rules) generate a subclass of the family of regular languages, descriptional complexity questions about splicing systems can be answered in terms of the size of the minimal deterministic finite automata that recognize their languages. In this paper we focus on a particular type of splicing systems, called simple splicing systems, where the splicing rules are of a particular form. We prove a tight state complexity bound of $$2^n - 1$$ for (semi-)simple splicing systems with a regular initial language with state complexity $$n \ge 3$$. We also show that the state complexity of a (semi-)simple splicing system with a finite initial language is at most $$2^{n-2} + 1$$, and that whether this bound is reachable or not depends on the size of the alphabet and the number of splicing rules.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387296
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:35:59 PM
Last modification on : Friday, November 29, 2019 - 5:01:50 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Lila Kari, Timothy Ng. State Complexity of Simple Splicing. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.197-209, ⟨10.1007/978-3-030-23247-4_15⟩. ⟨hal-02387296⟩

Share

Metrics

Record views

48