Bound-decreasing duplication system

We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates string...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-11, Vol.793, p.152-168
Main Authors: Cho, Da-Jung, Han, Yo-Sub, Kim, Hwee
Format: Article
Language:English
Subjects:
Automata theory
Bio-inspired operations
Computer Science
Formal languages
String duplication systems
Tandem duplication
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce the bound-decreasing duplication operation, a new variant of tandem duplication operation, that has restrictions on the position and the maximum size of the duplication segment in a target string. Then, we examine the bound-decreasing duplication system that iteratively generates strings from an initial string using the bound-decreasing duplication operation. We show that there exists a nondeterministic finite-state automaton (NFA) accepting all strings generated by the bound-decreasing duplication system when an initial input is a single string; in other words, the bound-decreasing duplication system produces a regular language. This helps us to calculate the system capacity based on the corresponding NFA. Furthermore, we revisit a deduplication operation—a reverse process of duplication—on an NFA that transforms a given NFA to a smaller NFA while generating the same language by the string duplication system.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.06.018