Options
Descriptional complexity of alternating finite automata
Date Issued
01-01-2006
Author(s)
Kavitha, J.
Jeganathan, L.
Sethuraman, G.
Abstract
State complexity is a descriptive complexity measure for regular languages. We investigate the state complexity of some operations on regular languages. In particular, we consider the concatenation, complementation, and shuffle operations of languages represented by Alternating Finite Automata(AFA). Most of the shown bounds are tight in the exact number of states. That is, the number is sufficient in the worst case.