کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950655 | 1364296 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Regular languages viewed from a graph-theoretic perspective
ترجمه فارسی عنوان
زبان های منظم از دیدگاه گراف-نظری مشاهده شده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider the graph G(L|w), resp. the directed graph Gâ(L|w), associated with an arbitrary language LâΣâ and an arbitrary string wâΣâ. The clique number of L is then defined as the supremum of the clique numbers of the graphs G(L|w) where w ranges over all strings in Σâ. The maximum in- or outdegree of L is defined analogously. We characterize regular languages with an infinite clique number and determine tight upper bounds in the finite case. We obtain analogous results for the maximum indegree and the maximum outdegree of a regular language. As an application, we consider the problem of determining the maximum activity level of a prefix-closed regular language - a parameter that is related to the computational complexity of parsing techniques utilizing unbounded regular lookahead. Finally, we determine the computational complexity of various problems arising from our graph-theoretic approach.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 253, Part 3, April 2017, Pages 484-496
Journal: Information and Computation - Volume 253, Part 3, April 2017, Pages 484-496
نویسندگان
Marius Konitzer, Hans Ulrich Simon,