Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2008 | Journal of Automata, Languages and Combinatorics | current input symbol,deterministic counter language,well-formed bag automation,well-formed bag automaton,inherent problem,infinite hierarchy,computational power,deterministic context-free language,nondeterministic storage,deterministic well-formed bag language,automata |
Field | DocType | Volume |
Deterministic automaton,Nondeterministic finite automaton,Nondeterministic algorithm,Nested word,Deterministic finite automaton,Computer science,Automaton,Algorithm,Automation,Theoretical computer science,Hierarchy | Journal | 13 |
Issue | Citations | PageRank |
3 | 1 | 0.39 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Daley | 1 | 166 | 22.18 |
| Mark Eramian | 2 | 12 | 1.69 |
| Ian McQuillan | 3 | 97 | 24.72 |