Monadic second-order logic on infinite words and trees
We present one of the fundamental results on the automata theory, namely the correspondence between finite automata recognizability and monadic second--order logic definability. The types of languages concerned are mainly those of infinite words and trees. As a corollary, we show the monadic second-...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2007.
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/139914/prif_b/ |
| Shrnutí: | We present one of the fundamental results on the automata theory, namely the correspondence between finite automata recognizability and monadic second--order logic definability. The types of languages concerned are mainly those of infinite words and trees. As a corollary, we show the monadic second--order logics with one and two successors to be decidable. These results are due to Büchi (1962) and Rabin (1969). We also illustrate the theory by our original examples. |
|---|---|
| Popis jednotky: | Vedoucí práce: Michal Kunc. |
| Fyzický popis: | v, 46 l. |