In this paper, we define the notion of a well-formed bag automation, which is used to model the inherent problems associated with the retrieval of elements from nondeterministic storage, such as a bag. The transition applied by such a machine depends on the symbol retrieved by a bag as well as the current input symbol. We will consider the computational power and other properties of nondeterministic and deterministic, well-formed bag automata. Of particular interest is a strict, infinite hierarchy of deterministic well-formed bag languages which we demonstrate between the deterministic counter languages and the deterministic context-free languages.
['Mark Daley', 'Mark G. Eramian', 'Ian McQuillan']
The bag automaton: a model of nondeterministic storage