id: 06101747
dt: a
an: 06101747
au: Palioudakis, Alexandros; Salomaa, Kai; Akl, Selim G.
ti: State complexity and limited nondeterminism.
so: Kutrib, Martin (ed.) et al., Descriptional complexity of formal systems.
    14th international workshop, DCFS 2012, Braga, Portugal, July 23‒25,
    2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31622-7/pbk).
    Lecture Notes in Computer Science 7386, 252-265 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: finite automata; limited nondeterminism; state complexity; language
    operations
ci: 
li: doi:10.1007/978-3-642-31623-4_20
ab: Summary: We consider nondeterministic finite automata having finite tree
    width (ftw-NFA) where the computation on any input string has a
    constant number of branches. We give effective characterizations of
    ftw-NFAs and a tight worst-case state size bound for determinizing an
    ftw-NFA $A$ as a function of the tree width and the number of states of
    $A$. We introduce a lower bound technique for ftw-NFAs and consider the
    operational state complexity of this model.
rv: