The hierarchical structure of graph searches (Q1098301): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Stefan Waner / rank | |||
Property / author | |||
Property / author: Stefan Waner / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0890-5401(87)90064-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1988549774 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3885184 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5639839 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5550390 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3856120 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:53, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The hierarchical structure of graph searches |
scientific article |
Statements
The hierarchical structure of graph searches (English)
0 references
1987
0 references
Given a graph \({\mathcal B}\), we show the existence of a universal automaton \({\mathcal U}\) which ``searches'' \({\mathcal B}\). U is universal in the sense that any automaton which searches \({\mathcal B}\) behaves as a subautomaton of \({\mathcal U}\). Further, \({\mathcal U}\) is naturally filtered in a manner suggestive of hierarchical search depth: level 1 corresponds to simple rules for moving on \({\mathcal B}\), level 2 to ``meta-rules'', and so on. We show that if \({\mathcal M}\) is any finite state automaton which searches \({\mathcal B}\), then \({\mathcal M}\) can in fact be embedded in some finite level \({\mathcal U}_ n\) of \({\mathcal U}\). This leads naturally to a definition of ``depth'' of an arbitrary automaton which searches \({\mathcal B}\), and we give several examples of such automata with varying depth. This notion of depth is independent of the state space structure of \({\mathcal M}\). We further describe a resulting strategy for the construction of evolutionary learning systems which learn structural control hierarchies, based on our model of the universal automaton.
0 references
universal automaton
0 references
hierarchical search
0 references
finite state automaton
0 references
evolutionary learning systems
0 references