Monadic logic and automata: Recent developments

被引：0

作者：

Thomas, W ^{[1
]}

机构：

[1] RWTH Aachen, Lehrstuhl Informat 7, D-52056 Aachen, Germany

来源：

THIRTEENTH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 1998年

关键词：

D O I：

10.1109/LICS.1998.705650

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This tutorial surveys selected recent results on the connection between monadic second-order logic and finite automata. As a unifying idea, the role of automata as normal forms of monadic formulas is pursued. In the first part we start from an automata-theoretic interpretation of existential monadic second-order formulas and in this framework explain the monadic quantifier alternation hierarchy over finite graphs. In the second part, infinite models, in particular omega-words, are considered. We analyze the logical significance of central constructions in omega-automata theory and sketch new proofs of decidability results in. monadic second-order logic.

引用

页码：136 / 138

页数：3