String assembling systems

dc.contributor.authorKutrib, Martin
dc.contributor.authorWendlandt, Matthias
dc.date.accessioned2023-06-02T13:37:45Z
dc.date.available2013-07-10T13:50:49Z
dc.date.available2023-06-02T13:37:45Z
dc.date.issued2012
dc.description.abstractWe introduce and investigate string assembling systems which form a computational model that generates strings from copies out of a finite set of assembly units. The underlying mechanism is based on piecewise assembly of a double-stranded sequence of symbols, where the upper and lower strand have to match. The generation is additionally controlled by the requirement that the first symbol of a unit has to be the same as the last symbol of the strand generated so far, as well as by the distinction of assembly units that may appear at the beginning, during, and at the end of the assembling process. We start to explore the generative capacity of string assembling systems. In particular, we prove that any such system can be simulated by some nondeterministic one-way two-head finite automaton, while the stateless version of the two-head finite automaton marks to some extent a lower bound for the generative capacity. Moreover, we obtain several incomparability and undecidability results as well as (non-)closure properties, and present questions for further investigations.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-98900
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/16404
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-15784
dc.language.isoende_DE
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleString assembling systemsen
dc.typearticlede_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.commentDieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG geförderten) Allianz- bzw. Nationallizenz frei zugänglich. This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively.
local.opus.fachgebietInformatikde_DE
local.opus.id9890
local.opus.instituteInstitut für Informatikde_DE
local.source.freetextRAIRO - Theoretical Informatics and Applications 46(04):593-613 doi: 10.1051/ita/2012020de_DE
local.source.urihttps://doi.org/10.1051/ita/2012020

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
10.1051_ita_2012020_Kutrib.pdf
Größe:
221.67 KB
Format:
Adobe Portable Document Format