State complexity of overlap assembly

DOI10.1007/978-3-319-94812-6_10MaRDI QIDQ1616964zbMATH OpenOpenAlexFDO

Authors Janusz Brzozowski, Bai Li, Marek Szykuła, Lila Kari

Publication date 7 November 2018

Full work available at URL https://arxiv.org/abs/1710.06000

zbMATH Keywords

regular language state complexity overlap assembly tight upper bound

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Protein sequences, DNA sequences (92D20)

Abstract: The emph{state complexity} of a regular language

L_{m}

is the number

m

of states in a minimal deterministic finite automaton (DFA) accepting

L_{m}

. The state complexity of a regularity-preserving binary operation on regular languages is defined as the maximal state complexity of the result of the operation where the two operands range over all languages of state complexities

l e m

and

l e n

, respectively. We find a tight upper bound on the state complexity of the binary operation emph{overlap assembly} on regular languages. This operation was introduced by Csuhaj-Varj'u, Petre, and Vaszil to model the process of self-assembly of two linear DNA strands into a longer DNA strand, provided that their ends "overlap". We prove that the state complexity of the overlap assembly of languages

L_{m}

and

L_{n}

, where

m g e 2

and

n g e 1

, is at most

2 (m - 1) 3^{n - 1} + 2^{n}

. Moreover, for

m g e 2

and

n g e 3

there exist languages

L_{m}

and

L_{n}

over an alphabet of size

n

whose overlap assembly meets the upper bound and this bound cannot be met with smaller alphabets. Finally, we prove that

m + n

is a tight upper bound on the overlap assembly of unary languages, and that there are binary languages whose overlap assembly has exponential state complexity at least

m (2^{n - 1} - 2) + 2

.

Recommendations

Cited in

(5)

This page was built for publication: State complexity of overlap assembly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1616964)