Depth-first search, left to right: the lexicographic order on paths, which considers a node before the nodes it dominates and the nodes of a left daughter before those of its sister.
- depthFirst q = ↑q
Used in BrananErlewine2026, Storment2026
Docs / Syntax / Minimalist / Probe / Search
Search orders
import Linglib.Syntax.Minimalist.Probe.Search · namespace Minimalist.Probe
A probe's search can be stated procedurally, as the order in which it considers the positions of
its domain, stopping at the first one that satisfies it; such an order is a key for
LinearizedSyntacticObject.goalsBy. Depth-first search, left to right, orders positions
lexicographically by their paths, the preorder of RoseTree.vertices; breadth-first search orders
them by depth and then left to right; and breadth-first search over unordered sisters orders them
by depth alone.
Main definitions
Minimalist.Probe.depthFirst,Minimalist.Probe.breadthFirst,Minimalist.Probe.depth: the three search orders.
References
- Branan & Erlewine 2026, Locality and (minimal) search formalized
Declarations
Breadth-first search, left to right: by depth, then left to right.
- breadthFirst q = toLex ((↑q).length, ↑q)
Used by breadthFirst_lt_of_depth_lt
Used in BrananErlewine2026
Breadth-first search over unordered sisters: by depth alone.
- depth q = (↑q).length
Used by breadthFirst_lt_of_depth_lt, depth_complement
Used in BrananErlewine2026, Storment2026
Built from ,
Built from