کلمات کلیدی مربوط به کتاب و غیره. تکنیک ها و کاربردهای Tree Automata: مهندسی انفورماتیک و کامپیوتر، تئوری خودکار
در صورت تبدیل فایل کتاب etc. Tree Automata Techniques and Applications به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب و غیره. تکنیک ها و کاربردهای Tree Automata نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
Université de Lille, 2008, -262 pp.
During the past few years, several of
us have been asked many times about references on finite tree
automata. On one hand, this is the witness of the liveness of
this field. On the other hand, it was difficult to answer.
Besides several excellent survey chapters on more specific
topics, there is only one monograph devoted to tree automata by
Gecseg and Steinby. Unfortunately, it is now impossible to find
a copy of it and a lot of work has been done on tree automata
since the publication of this book. Actually using tree
automata has proved to be a powerful approach to simplify and
extend previously known results, and also to find new results.
For instance recent works use tree automata for application in
abstract interpretation using set constraints, rewriting,
automated theorem proving and program verification, databases
and XML schema languages.
Tree automata have been designed a long time ago in the context
of circuit verification. Many famous researchers contributed to
this school which was headed by A. Church in the late 50’s and
the early 60’s: B. Trakhtenbrot, J.R. Buchi, M.O. Rabin, Doner,
Thatcher, etc. Many new ideas came out of this program. For
instance the connections between automata and logic. Tree
automata also appeared first in this framework, following the
work of Doner, Thatcher and Wright. In the 70’s many new
results were established concerning tree automata, which lose a
bit their connections with the applications and were studied
for their own. In particular, a problem was the very high
complexity of decision procedures for the monadic second order
logic. Applications of tree automata to program verification
revived in the 80’s, after the relative failure of automated
deduction in this field. It is possible to verify temporal
logic formulas (which are particular Monadic Second Order
Formulas) on simpler (small) programs. Automata, and in
particular tree automata, also appeared as an approximation of
programs on which fully automated tools can be used. New
results were obtained connecting properties of programs or type
systems or rewrite systems with automata.
Our goal is to fill in the existing gap and to provide a
textbook which presents the basics of tree automata and several
variants of tree automata which have been devised for
applications in the aforementioned domains. We shall discuss
only finite tree automata, and the reader interested in
infinite trees should consult any recent survey on automata on
infinite objects and their applications (See the bibliography).
The second main restriction that we have is to focus on the
operational aspects of tree automata. This book should appeal
the reader who wants to have a simple presentation of the
basics of tree automata, and to see how some variations on the
idea of tree automata have provided a nice tool for solving
difficult problems. Therefore, specialists of the domain
probably know almost all the material embedded. However, we
think that this book can be helpful for many researchers who
need some knowledge on tree automata. This is typically the
case of a PhD student who may find new ideas and guess
connections with his (her) own work.
Again, we recall that there is no presentation nor discussion
of tree automata for infinite trees. This domain is also in
full development mainly due to applications in program
verification and several surveys on this topic do exist. We
have tried to present a tool and the algorithms devised for
this tool. Therefore, most of the proofs that we give are
constructive and we have tried to give as many complexity
results as possible. We don’t claim to present an exhaustive
description of all possible finite tree automata already
presented in the literature and we did some choices in the
existing menagerie of tree automata. Although some works are
not described thoroughly (but they are usually described in
exercises), we think that the content of this book gives a good
flavor of what can be done with the simple ideas supporting
tree automata.
This book is an open work and we want it to be as interactive
as possible. Readers and specialists are invited to provide
suggestions and improvements. Submissions of contributions to
new chapters and improvements of existing ones are
welcome.
Among some of our choices, let us mention that we have not
defined any precise language for describing algorithms which
are given in some pseudo algorithmic language. Also, there is
no citation in the text, but each chapter ends with a section
devoted to bibliographical notes where credits are made to the
relevant authors. Exercises are also presented at the end of
each chapter. Tree Automata Techniques and Applications is
composed of eight main chapters (numbered 1–8). The first one
presents tree automata and defines recognizable tree languages.
The reader will find the classical algorithms and the classical
closure properties of the class of recognizable tree languages.
Complexity results are given when they are available. The
second chapter gives an alternative presentation of
recognizable tree languages which may be more relevant in some
situations. This includes regular tree grammars, regular tree
expressions and regular equations. The description of
properties relating regular tree languages and context-free
word languages form the last part of this chapter. In Chapter
3, we show the deep connections between logic and automata. In
particular, we prove in full details the correspondence between
finite tree automata and the weak monadic second order logic
with k successors. We also sketch several applications in
various domains.
Chapter 4 presents a basic variation of automata, more
precisely automata with equality constraints. An equality
constraint restricts the application of rules to trees where
some subtrees are equal (with respect to some equality
relation). Therefore we can discriminate more easily between
trees that we want to accept and trees that we must reject.
Several kinds of constraints are described, both originating
from the problem of non-linearity in trees (the same variable
may occur at different positions).
In Chapter 5 we consider automata which recognize sets of sets
of terms. Such automata appeared in the context of set
constraints which themselves are used in program analysis. The
idea is to consider, for each variable or each predicate symbol
occurring in a program, the set of its possible values. The
program gives constraints that these sets must satisfy. Solving
the constraints gives an upper approximation of the values that
a given variable can take. Such an approximation can be used to
detect errors at compile time: it acts exactly as a typing
system which would be inferred from the program. Tree set
automata (as we call them) recognize the sets of solutions of
such constraints (hence sets of sets of trees). In this chapter
we study the properties of tree set automata and their
relationship with program analysis.
Originally, automata were invented as an intermediate between
function description and their implementation by a circuit. The
main related problem in the sixties was the synthesis problem:
which arithmetic recursive functions can be achieved by a
circuit? So far, we only considered tree automata which accepts
sets of trees or sets of tuples of trees (Chapter 3) or sets of
sets of trees (Chapter 5). However, tree automata can also be
used as a computational device. This is the subject of Chapter
6 where we study tree transducers. In Chapter 7 we present
basic properties of alternating automata. As an application we
consider set constraints that have already been introduced in
Chapter 5.
In Chapter 8 we drop the restriction for ranked trees that the
label of a node determines the number of successors of this
node, so we consider the model of unranked ordered trees. This
model is used for representing the structure of XML documents.
We discuss the basic model of hedge automaton, study its
algorithmic and closure properties, and then present some
formalisms used in practice to define classes of XML documents.
Recognizable Tree Languages and
Finite Tree Automata
Regular Grammars and Regular Expressions
Logic, Automata and Relations
Automata with Constraints
Tree Set Automata
Tree Transducers
Alternating Tree Automata
Automata for Unranked Trees