6533b828fe1ef96bd1288d66

RESEARCH PRODUCT

Quantum Finite State Automata over Infinite Words

Ilze Dzelme-bērziņa

subject

Discrete mathematicsCombinatoricsFinite-state machineDeterministic finite automatonComputer Science::Logic in Computer ScienceContinuous spatial automatonQuantum finite automataAutomata theoryNondeterministic finite automatonω-automatonComputer Science::Formal Languages and Automata TheoryDecidabilityMathematics

description

The study of finite state automata working on infinite words was initiated by Buchi [1]. Buchi 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 Buchi 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.

yearjournalcountryeditionlanguage
2010-01-01
https://doi.org/10.1007/978-3-642-13523-1_21