کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10225766 | 1701212 | 2018 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Weighted register automata and weighted logic on data words
ترجمه فارسی عنوان
اتوماتیک ثبت شده وزن و منطق وزن بر روی کلمات داده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ترجمه چکیده
کلمات داده ها عبارتند از توالی جفت که در آن عنصر اول از الفبای محدود گرفته شده است و عنصر دوم از یک دامنه نامحدود گرفته شده است. اتوماتای ثبت نام یک مدل به طور گسترده مورد مطالعه برای استدلال بر روی کلمات داده است. در این مقاله، مدلهای اتوماتا برای جنبه های کمی سیستم ها با دامنه های نامحدود نامحدود، مانند هزینه های ذخیره داده ها در یک سرور از راه دور یا مصرف منابع (مثلا حافظه، انرژی، زمان) در طی تجزیه و تحلیل داده ها مورد بررسی قرار می گیریم. ما ماژول های اتوماتیک ثبت شده بر روی کلمات داده ها را بر روی نیمی از داده های متناوب مجهز به مجموعه ای از توابع داده های باینری معرفی می کنیم و خواص بسته شدن آنها را بررسی می کنیم. بر خلاف مدل های دیگر که در ادبیات مطرح شده است، ما امکان مقایسه داده ها با استفاده از مجموعه دلخواه روابط داده باینری را فراهم می کنیم. این امر ما را قادر می سازد که اتوماتای زمان بندی شده و اتوماتیک زمان بندی شده با وزن را به چارچوب ما متصل کنیم. در نتیجه اصلی ما، ما یک ویژگی منطقی از ماشین حساب ثبت وزن را با استفاده از منطق دوم مرتبه وجود دارد مسیحی؛ برای اثبات ما یک کلاس جدیدی از ماشین حساب قابل ثبت قابل تعریف قابل استفاده است.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Data words are sequences of pairs where the first element is taken from a finite alphabet and the second element is taken from an infinite data domain. Register automata provide a widely studied model for reasoning on data words. In this paper, we investigate automata models for quantitative aspects of systems with infinite data domains, e.g., the costs of storing data on a remote server or the consumption of resources (e.g., memory, energy, time) during a data analysis. We introduce weighted register automata on data words over commutative data semirings equipped with a collection of binary data functions, and we investigate their closure properties. Unlike the other models considered in the literature, we allow data comparison by means of an arbitrary collection of binary data relations. This enables us to incorporate timed automata and weighted timed automata into our framework. In our main result, we give a logical characterization of weighted register automata by means of weighted existential monadic second-order logic; for the proof we employ a new class of determinizable visibly register automata.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 744, 5 October 2018, Pages 3-21
Journal: Theoretical Computer Science - Volume 744, 5 October 2018, Pages 3-21
نویسندگان
Parvaneh Babari, Manfred Droste, Vitaly Perevoshchikov,