کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439117 690448 2009 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Nondeterministic state complexity of nested word automata
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Nondeterministic state complexity of nested word automata
چکیده انگلیسی

We study the nondeterministic state complexity of Boolean operations on regular languages of nested words. For union and intersection we obtain matching upper and lower bounds. For complementation of a nondeterministic nested word automaton with n states we establish a lower bound that is significantly worse than the exponential lower bound for ordinary nondeterministic finite automata (NFA). We develop techniques to prove lower bounds for the size of nondeterministic nested word automata that extend the known techniques used for NFAs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 30–32, 20 August 2009, Pages 2961-2971