| Autor: |
Dzelme-Bērziņa, Ilze |
| Zdroj: |
Unconventional Computation: 9th International Conference, US 2010, Tokyo, Japan, June 21-25, 2010. Proceedings; 2010, p188-188, 1p |
| Abstrakt: |
The study of finite state automata working on infinite words was initiated by Büchi [1]. Büchi discovered connection between formulas of the monadic second order logic of infinite sequences (S1S) and ω-regular languages, the class of languages over infinite words accepted by finite state automata. Few years later, Muller proposed an alternative definition of finite automata on infinite words [4]. McNaughton proved that with Muller΄s definition, deterministic automata recognize all ω-regular languages [2]. Later, Rabin extended decidability result of Büchi for S1S to the monadic second order of the infinite binary tree (S2S) [5]. Rabin theorem can be used to settle a number of decision problems in logic. A theory of automata over infinite words has started from these studies. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
