• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the State Complexity of Operations on Two-Way Finite automata

Galina Jiraskova, Alexander Okhotin, On the State Complexity of Operations on Two-Way Finite automata. TUCS Technical Reports 912, Turku Centre for Computer Science, 2008.

Abstract:

The number of states in two-way deterministic finite automata (2DFAs) is considered.
It is shown that the state complexity of basic operations is:
at least <i>m</i>+<i>n</i>&#8722;o(<i>m</i>+<i>n</i>) and at most 4<i>m</i>+<i>n</i>+1 for union;
at least <i>m</i>+<i>n</i>&#8722;o(<i>m</i>+<i>n</i>) and at most <i>m</i>+<i>n</i>+1 for intersection;
at least <i>n</i> and at most 4<i>n</i> for complementation;
at least &Omega;(<i>m</i>/<i>n</i>) + 2^{&Omega;(<i>n</i>)}/log <i>m</i>
and at most 2<i>m</i>^<i>m</i>+1 2^nⁿ⁺¹ for concatenation;
at least (1/n) 2^{<i>n</i>/2 &#8722; 1}
and at most 2^{O(<i>n</i>^<i>n</i>+1)}
for both star and square;
between <i>n</i> and <i>n</i>+2 for reversal;
exactly 2<i>n</i> for inverse homomorphism.
In each case <i>m</i> and <i>n</i> denote
the number of states in 2DFAs for the arguments.

Files:

Abstract in PDF-format

BibTeX entry:

@TECHREPORT{tJiOk08a,
  title = {On the State Complexity of Operations on Two-Way Finite automata},
  author = {Jiraskova, Galina and Okhotin, Alexander},
  number = {912},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2008},
  keywords = {State complexity, descriptional complexity, two-way automata},
  ISBN = {978-952-12-2148-4},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication