کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657925 | 690117 | 2005 | 34 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finite graph automata for linear and boundary graph languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Finite graph automata for linear and boundary graph languages Finite graph automata for linear and boundary graph languages](/preview/png/9657925.png)
چکیده انگلیسی
Here we introduce graph automata as devices for the recognition of sets of undirected node labelled graphs. A graph automaton consists of a finite state control, a finite set of instructions, and a collection of heads or guards. It reads an input graph in a systematic way and performs a graph search directed by the instructions. As our main results we show that finite graph automata recognize exactly the set of graph languages generated by linear NCE graph grammars and that alternating finite graph automata recognize exactly the languages of boundary graph grammars. Finally, we generalize some automata theoretic properties from string to graph automata, integrate the connectivity of graphs into graph automata, and explain why graph automata cannot be generalized to deal with dynamic edge relabellings and eNCE graph languages.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 199-232
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 199-232
نویسندگان
F.J. Brandenburg, K. Skodinis,