RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2013 Volume 49, Issue 2, Pages 58–72 (Mi ppi2108)

Automata Theory

Determinization of ordinal automata

An. A. Muchnik


Abstract: It is proved that for each nondeterministic ordinal automaton there exists a deterministic ordinal automaton which is equivalent to the original one for all countable ordinals. An upper bound for the number of states of the deterministic automaton is double exponential in the number of states of the nondeterministic automaton.

UDC: 621.391.1+519.7

Received: 05.09.2011
Revised: 05.02.2013


 English version:
Problems of Information Transmission, 2013, 49:2, 149–162

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024