State complexity of operations on two-way deterministic finite automata over a unary alphabet

Michal Kunc, Alexander Okhotin

Research outputpeer-review

3 Citations (Scopus)

Abstract

The paper determines the number of states in a two-way deterministic finite automaton (2DFA) over a one-letter alphabet sufficient and in the worst case necessary to represent the results of the following operations: (i) intersection of an m-state 2DFA and an n-state 2DFA requires between m∈+∈n and m∈+∈n∈+∈1 states; (ii) union of an m-state 2DFA and an n-state 2DFA, between m∈+∈n and 2m∈+∈n∈+∈4 states; (iii) Kleene star of an n-state 2DFA, (g(n)∈+∈O(n))2 states, where is the maximum value of lcm(p 1, ..., p k ) for , known as Landau's function; (iv) k-th power of an n-state 2DFA, between (k∈-∈1)g(n)∈-∈k and k(g(n)∈+∈n) states; (v) concatenation of an m-state and an n-state 2DFAs, states.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 13th International Workshop, DCFS 2011, Proceedings
Pages222-234
Number of pages13
DOIs
Publication statusPublished - 11 Aug 2011
Event13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011 - Giessen/Limburg
Duration: 25 Jul 201127 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6808 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Workshop of Descriptional Complexity of Formal Systems, DCFS 2011
CountryGermany
CityGiessen/Limburg
Period25/07/1127/07/11

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'State complexity of operations on two-way deterministic finite automata over a unary alphabet'. Together they form a unique fingerprint.

Cite this