کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950653 1364296 2017 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Weighted automata and logics for infinite nested words
ترجمه فارسی عنوان
اتوماتای ​​وزن و منطق برای کلمات نامحدود بی نهایت
کلمات کلیدی
کلمات مشتعل، اتوماتای ​​وزنی، منطق وزن، خودکار اتوماتیک، مونوئید ارزش گذاری،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Nested words introduced by Alur and Madhusudan are used to capture structures with both linear and hierarchical order, e.g. XML documents, without losing valuable closure properties. Furthermore, Alur and Madhusudan introduced automata and equivalent logics for both finite and infinite nested words, thus extending Büchi's theorem to nested words. Recently, average and discounted computations of weights in quantitative systems found much interest. Here, we will introduce and investigate weighted automata models and weighted MSO logics for infinite nested words. As weight structures we consider valuation monoids which incorporate average and discounted computations of weights as well as the classical semirings. We show that under suitable assumptions, two resp. three fragments of our weighted logics can be transformed into each other. Moreover, we show that the logic fragments have the same expressive power as weighted nested word automata.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 3, April 2017, Pages 448-466
نویسندگان
, ,