About: Splicing systems are generative mechanisms introduced by Tom Head in 1987 to model the biological process of DNA recombination. The computational engine of a splicing system is the “splicing operation”, a cut-and-paste binary string operation defined by a set of “splicing rules”, quadruples [Formula: see text] where [Formula: see text] are words over an alphabet [Formula: see text]. For two strings [Formula: see text] and [Formula: see text], applying the splicing rule r produces the string [Formula: see text]. In this paper we focus on a particular type of splicing systems, called (i, j) semi-simple splicing systems, [Formula: see text] and [Formula: see text], wherein all splicing rules r have the property that the two strings in positions i and j in r are singleton letters, while the other two strings are empty. The language generated by such a system consists of the set of words that are obtained starting from an initial set called “axiom set”, by iteratively applying the splicing rules to strings in the axiom set as well as to intermediately produced strings. We consider semi-simple splicing systems where the axiom set is a regular language, and investigate the descriptional complexity of such systems in terms of the size of the minimal deterministic finite automata that recognize the languages they generate.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • Splicing systems are generative mechanisms introduced by Tom Head in 1987 to model the biological process of DNA recombination. The computational engine of a splicing system is the “splicing operation”, a cut-and-paste binary string operation defined by a set of “splicing rules”, quadruples [Formula: see text] where [Formula: see text] are words over an alphabet [Formula: see text]. For two strings [Formula: see text] and [Formula: see text], applying the splicing rule r produces the string [Formula: see text]. In this paper we focus on a particular type of splicing systems, called (i, j) semi-simple splicing systems, [Formula: see text] and [Formula: see text], wherein all splicing rules r have the property that the two strings in positions i and j in r are singleton letters, while the other two strings are empty. The language generated by such a system consists of the set of words that are obtained starting from an initial set called “axiom set”, by iteratively applying the splicing rules to strings in the axiom set as well as to intermediately produced strings. We consider semi-simple splicing systems where the axiom set is a regular language, and investigate the descriptional complexity of such systems in terms of the size of the minimal deterministic finite automata that recognize the languages they generate.
Subject
  • Musical groups from Dublin (city)
  • Formal languages
  • Kamen Rider television series
  • Sumerograms
  • Combinatorics on words
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software