State-Size Hierarchy for Finite-State Complexity.

Cristian S. Calude Kai Salomaa Tania Roblot

Published in: Int. J. Found. Comput. Sci. (2012)

Keyphrases

finite state
markov chain
space complexity
markov decision processes
computational complexity
model checking
transition systems
state space
optimal policy
transition probabilities
information retrieval
sufficient conditions
memory requirements
average cost