کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874026 | 686415 | 2015 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Normality and two-way automata
ترجمه فارسی عنوان
نرمال و اتوماتای دو طرفه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای دو طرفه، اعداد عادی، فشرده سازی،
ترجمه چکیده
ما ثابت می کنیم که مبدل های دو طرفه (هر دو قطعی و غیر قطعی) می توانند عدد های عادی را فشرده نکنند. برای رسیدن به این هدف، ابتدا نشان می دهیم که امکان پذیری فشردگی از مبدل های یک طرفه به مبدل های دو طرفه امکان پذیر است. این نتایج یک نتیجه شناخته شده را به وجود می آورند: واژه های بی نهای عادی دقیقا همان هایی هستند که نمی توانند با مبدل های حالت ناخوشایند فشرده شده و به طور کلی توسط مبدل های حالت محدود با محدودیت به یک غیر قطعی باشد. ما همچنین استدلال می کنیم که چنین تعمیم نمی تواند به مبدل های دو طرفه با حافظه نا محدود، حتی در فرم ساده یک شمارنده، گسترش یابد.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that two-way transducers (both deterministic and non-deterministic) cannot compress normal numbers. To achieve this, we first show that it is possible to generalize compressibility from one-way transducers to two-way transducers. These results extend a known result: normal infinite words are exactly those that cannot be compressed by lossless finite-state transducers, and, more generally, by bounded-to-one non-deterministic finite-state transducers. We also argue that such a generalization cannot be extended to two-way transducers with unbounded memory, even in the simple form of a single counter.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 241, April 2015, Pages 264-276
Journal: Information and Computation - Volume 241, April 2015, Pages 264-276
نویسندگان
Olivier Carton, Pablo Ariel Heiber,