Paper deep dive
Exploration Space Theory: Formal Foundations for Prerequisite-Aware Location-Based Recommendation
Madjid Sadallah
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/20/2026, 8:57:13 PM
Summary
The paper introduces Exploration Space Theory (EST), a formal framework for location-based recommendation that models prerequisite dependencies among Points of Interest (POIs) using Knowledge Space Theory. It proves that valid user exploration states form a finite distributive lattice, enabling algorithmic guarantees such as linear-time fringe computation and sub-path optimal path generation. The authors propose the Exploration Space Recommender System (ESRS), which integrates a Bayesian state estimator, dynamic programming, and structural cold-start strategies to provide formally valid recommendations.
Entities (10)
Relation Signals (7)
Valid User Exploration States → form → Finite Distributive Lattice
confidence 96% · We prove that the valid user exploration states -- the order ideals of a surmise partial order on points of interest -- form a finite distributive lattice
Exploration Space Theory → transposes → Knowledge Space Theory
confidence 95% · We introduce Exploration Space Theory (EST), a formal framework that transposes Knowledge Space Theory into location-based recommendation.
Surmise Relation → defines → Prerequisite Dependency
confidence 94% · q ⪯ q' means that engaging meaningfully with q' presupposes prior meaningful engagement with q.
Exploration Space Theory → yields → Linear-Time Fringe Computation
confidence 92% · These structural results yield four direct consequences: linear-time fringe computation...
Exploration Space Recommender System → implements → Bayesian State Estimator
confidence 90% · The ESRS integrates... a Bayesian state estimator with beam approximation and EM parameter learning
Structural Cold-Start → provides → Formal Validity Guarantee
confidence 89% · the structural one being the only approach in the literature to provide a formal validity guarantee conditional on the correctness of the inferred surmise relation.
Birkhoff's Representation Theorem → connects → Formal Concept Analysis
confidence 88% · Birkhoff’s representation theorem... connects the exploration space canonically to Formal Concept Analysis.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Location-based recommender systems have achieved considerable sophistication, yet none provides a formal, lattice-theoretic representation of prerequisite dependencies among points of interest -- the semantic reality that meaningfully experiencing certain locations presupposes contextual knowledge gained from others -- nor the structural guarantees that such a representation entails. We introduce Exploration Space Theory (EST), a formal framework that transposes Knowledge Space Theory into location-based recommendation. We prove that the valid user exploration states -- the order ideals of a surmise partial order on points of interest -- form a finite distributive lattice and a well-graded learning space; Birkhoff's representation theorem, combined with the structural isomorphism between lattices of order ideals and concept lattices, connects the exploration space canonically to Formal Concept Analysis. These structural results yield four direct consequences: linear-time fringe computation, a validity certificate guaranteeing that every fringe-guided recommendation is a structurally sound next step, sub-path optimality for dynamic-programming path generation, and provably existing structural explanations for every recommendation. Building on these foundations, we specify the Exploration Space Recommender System (ESRS) -- a memoized dynamic program over the exploration lattice, a Bayesian state estimator with beam approximation and EM parameter learning, an online feedback loop enforcing the downward-closure invariant, an incremental surmise-relation inference pipeline, and three cold-start strategies, the structural one being the only approach in the literature to provide a formal validity guarantee conditional on the correctness of the inferred surmise relation. All results are established through proof and illustrated on a fully traced five-POI numerical example.
Tags
Links
- Source: https://arxiv.org/abs/2603.06624v1
- Canonical: https://arxiv.org/abs/2603.06624v1
Trouble viewing inline? Open PDF directly →
Full Text
122,129 characters extracted from source content.
Expand or collapse full text
Exploration Space Theory Formal Foundations for Prerequisite-Aware Location-Based Recommendation Madjid Sadallah LIRIS, Université Claude Bernard Lyon 1, CNRS, 43 boulevard du 11 novembre 1918, 69622 Villeurbanne, France madjid.sadallah@liris.cnrs.fr Abstract Location-based recommender systems have achieved considerable sophistication, yet none provides a formal, lattice-theoretic representation of prerequisite dependencies among points of interest—the semantic reality that meaningfully experiencing certain locations presupposes contextual knowledge gained from others—nor the structural guarantees that such a representation entails. We introduce Exploration Space Theory (EST), a formal framework that transposes Knowledge Space Theory into location-based recommendation. We prove that the valid user exploration states—the order ideals of a surmise partial order on points of interest—form a finite distributive lattice and a well-graded learning space; Birkhoff’s representation theorem, combined with the structural isomorphism between lattices of order ideals and concept lattices, connects the exploration space canonically to Formal Concept Analysis. These structural results yield four direct consequences: linear-time fringe computation, a validity certificate guaranteeing that every fringe-guided recommendation is a structurally sound next step, sub-path optimality for dynamic-programming path generation, and provably existing structural explanations for every recommendation. Building on these foundations, we specify the Exploration Space Recommender System (ESRS)—a memoized dynamic program over the exploration lattice, a Bayesian state estimator with beam approximation and EM parameter learning, an online feedback loop enforcing the downward-closure invariant, an incremental surmise-relation inference pipeline, and three cold-start strategies, the structural one being the only approach in the literature to provide a formal validity guarantee conditional on the correctness of the inferred surmise relation. All results are established through proof and illustrated on a fully traced five-POI numerical example. Keywords: Knowledge Space Theory — Formal Concept Analysis — Distributive Lattice Theory — Location-Based Recommender Systems — Sequential Recommendation — Exploration Paths — Urban Computing — Dynamic Programming Introduction Urban exploration is fundamentally a process of structured discovery. A visitor arriving in an unfamiliar city does not face a featureless scatter of locations but a partially ordered space of experiences in which certain visits naturally build upon others. Understanding the architectural evolution of a historic quarter provides the contextual grounding necessary to appreciate a specialist gallery housed within it; experiencing a city’s central food market gives experiential meaning to a subsequent tour of its artisanal producers. This ordering is not a temporal sequence imposed by geography or logistics, but a partial order of cognitive and experiential prerequisites: a semantic structure that should be explicitly represented in any recommendation system that aspires to support genuine discovery rather than mere retrieval. Current Location-Based Recommender Systems (LBRS) have made substantial advances in personalization, context-awareness, and sequential modeling (Ricci et al., 2011; Adomavicius and Tuzhilin, 2005; Yuan et al., 2013). Collaborative filtering identifies users with similar behavioral patterns; deep sequential models—ranging from Markov chains to Recurrent Neural Networks and Transformer-based architectures (Rendle et al., 2010; Hidasi et al., 2016; Kang and McAuley, 2018; Yang et al., 2022)—capture transition regularities from historical trajectories with impressive empirical performance. Yet across all these paradigms, a critical dimension remains absent: an explicit, formally grounded, and interpretable model of why certain sequences of locations are more meaningful than others. These systems learn correlational shadows of an underlying semantic structure they cannot represent. They cannot distinguish a visit sequence driven by geographic proximity from one driven by a genuine prerequisite dependency. Consequently, users in unfamiliar environments frequently receive fragmented lists of popular venues rather than coherent, structured journeys (Gavalas et al., 2014). To address this structural gap, we turn to Knowledge Space Theory (KST; Doignon and Falmagne, 1985, 1999; Falmagne and Doignon, 2011). Originally designed to formalize knowledge acquisition in educational domains, KST defines a knowledge space as a family of states closed under union, structured by surmise relations in which mastering one item implies having mastered its prerequisites. Over four decades, this theory has proven effective in driving adaptive assessment and intelligent tutoring systems (Corbett and Anderson, 1994; Desmarais and Baker, 2012). The central thesis of the present work is that the mathematical apparatus of KST translates naturally, rigorously, and productively to the domain of urban exploration. By transposing KST to LBRS, the representational paradigm shifts fundamentally. Rather than modeling a user solely through latent preference embeddings, we propose to represent the user’s cumulative exploration state: a structured object encoding what the user has meaningfully visited and thereby determining what they are now ready to discover. We prove that any surmise relation over a finite set of points of interest generates a collection of valid exploration states forming a finite distributive lattice. This algebraic structure provides immediate algorithmic guarantees: linear-time computation of the exploration fringe, guaranteed valid fringe-guided transitions, and sub-path optimal dynamic-programming-based path recommendation. These guarantees are not heuristic claims but consequences of proven mathematical propositions. Translating these results into a functional architecture, we propose the Exploration Space Recommender System (ESRS). The ESRS integrates a unified interest score that synthesizes user preferences, location properties, collaborative signals, and structural state-relative constraints. It employs a BLIM-inspired probabilistic model to handle uncertainty in user state estimation, and offers three KST-grounded cold-start strategies, one of which—purely structural cold-start—provides a formal validity guarantee unavailable in any existing approach (see §4.4 and Limitation L5). The present work is a conceptual and theoretical contribution. We provide a comprehensive architectural specification, a complete algorithmic pipeline, and a fully traced numerical example. Empirical evaluation against state-of-the-art baselines is explicitly identified as the primary direction for future work; the objective here is to establish the mathematical foundations of EST, prove their correctness, and demonstrate how the framework addresses structural limitations of current approaches that are not resolvable by purely statistical means. Background and Related Work Location-Based Recommendation Systems Location-Based Recommender Systems sit at the intersection of geographic information science, personalization, and machine learning. Their core task is to produce, for a given user and spatiotemporal context, a ranked list of Points of Interest (POIs) likely to be relevant and engaging. Collaborative filtering and geographic influence. The seminal observation of Ye et al. (2011) is that the probability of visiting a POI decreases as a power-law function of distance from a user’s home or current position. This spatial structure has become a standard component of LBRS architecture (Schafer et al., 2007). Context integration. Yuan et al. (2013) demonstrated that visited POI types vary significantly by time of day and day of week. More broadly, Adomavicius and Tuzhilin (2011) established the principle of context-aware recommendation: interactions should be modeled as triples (u,i,c)(u,i,c) rather than pairs (u,i)(u,i). Content-based filtering leverages POI attribute structure (Pazzani and Billsus, 2007; Lops et al., 2011); hybrid architectures address individual weaknesses of each paradigm (Burke, 2002). Deep learning and graph-based approaches. He et al. (2017) introduced Neural Collaborative Filtering, replacing the inner product of matrix factorization with a multi-layer perceptron. Graph Neural Networks extended these capabilities by explicitly modeling relational structure (Fan et al., 2019; Wu et al., 2021), propagating information along user-POI interaction graphs, social graphs, and category hierarchies. Persistent structural gap. Despite this sophistication, all the above systems fundamentally model individual POI relevance or pairwise transition patterns. They have no mechanism to ask whether the user is semantically ready for a given POI—whether the cognitive and experiential prerequisites for meaningfully engaging with it have been met. EST addresses this gap by modeling the user’s cumulative exploration state as a first-class object and encoding semantic readiness through the surmise relation. Sequence-Aware and Session-Based Recommendation Markov-chain approaches. Rendle et al. (2010) introduced FPMC, combining personalized user factors with first-order Markov transition patterns for next-POI prediction. The first-order Markov assumption limits ability to capture long-range dependencies. RNN-based approaches. Hidasi et al. (2016) introduced GRU4Rec, using Gated Recurrent Units to model session-level recommendation. Feng et al. (2017) proposed DeepMove, using an attention-based recurrent architecture separately modeling long-term and short-term mobility patterns. Transformer-based approaches. Self-attention (Kang and McAuley, 2018; Sun et al., 2019) has superseded RNNs as the dominant architecture for sequential recommendation. SASRec achieves state-of-the-art performance on multiple benchmarks. GETNext (Yang et al., 2022) integrates a graph-based global POI transition model with a local Transformer encoder. STAN (Luo et al., 2021) applies spatio-temporal self-attention weighting past check-ins by spatial proximity and temporal recency. The fundamental representational boundary. All sequential models learn to predict the next item by identifying statistical regularities in observed sequences. High co-occurrence does not imply a prerequisite relationship, and a prerequisite relationship may not manifest as high co-occurrence if most users satisfy it via indirect paths, if the prerequisite is universally satisfied (no variance), or if training data is sparse. Sequential models therefore cannot reliably infer, represent, or reason about prerequisite dependencies even if such dependencies structure the data. EST introduces an orthogonal modeling dimension—the formal prerequisite structure—that sequential models cannot represent by design. The Tourist Trip Design Problem The Tourist Trip Design Problem (TTDP) (Vansteenwegen et al., 2011; Gavalas et al., 2014) asks for a subset of POIs and an ordering maximizing total score without violating a time budget. It is a generalization of the NP-hard Orienteering Problem. Lim et al. (2018) introduced a personalized variant in which scores are functions of user interest profiles, but retains the core assumption that POIs are independent: there are no inter-POI dependencies making the desirability of one contingent on having visited another. ESRS and the TTDP differ in three structural dimensions. First, ESRS interest scores depend on the user’s current exploration state, which changes after each visit. Second, ESRS models prerequisite dependencies as the primary structural element. Third, the TTDP does not model cumulative exploration knowledge. Despite these differences, the two frameworks are complementary: the ESRS path optimization component can incorporate TTDP-style time budget and time-window constraints as side constraints on the DP state space, as we formalize in the algorithmic section (Remark 5.7 in §5.3). Knowledge Space Theory Knowledge Space Theory (KST) was developed by Doignon and Falmagne (1985) to model the structure of human knowledge and the process of knowledge acquisition. A knowledge structure (Q,)(Q,K) consists of a finite domain Q of items and a family ⊆2QK 2^Q of knowledge states, satisfying ∅∈ and Q∈Q . A knowledge structure is a knowledge space if K is closed under arbitrary unions; it is a learning space if additionally closed under non-empty intersections and satisfying the well-graded property (Falmagne and Doignon, 2011). The surmise relation ⪯ on Q is defined by q⪯q′q q if mastering q′q implies having mastered q. The family of all downward-closed subsets of (Q,⪯)(Q, ) is a knowledge space (Doignon and Falmagne, 1999) and in fact a learning space (Falmagne and Doignon, 2011). The fringe of a knowledge state K is the set of items q∉Kq∉ K such that K∪qK∪\q\ is a valid state. In adaptive assessment, the fringe identifies items that are one step ahead of the current state and have maximal diagnostic value. This operational role is inherited directly by the exploration fringe in ESRS. The BLIM (Falmagne and Doignon, 1988) provides probabilistic inference machinery connecting observed responses to knowledge state estimates via Bayes’ rule with item-specific false-positive (βi _i) and false-negative (ηi _i) error parameters. KST has been deployed in the ALEKS adaptive learning platform (Falmagne and Doignon, 2011) and applied to structured path recommendation in technology-enhanced learning (Sadallah and Smits, 2023). Formal Concept Analysis and Distributive Lattice Theory Formal Concept Analysis (FCA) (Wille, 1982; Ganter and Wille, 1999) derives formal concepts from a binary object-attribute relation and organizes them into a concept lattice—a complete lattice capturing the hierarchical structure of the conceptual space. The relevance of FCA to EST is through Birkhoff’s representation theorem (Birkhoff, 1937; Davey and Priestley, 2002): every finite distributive lattice is isomorphic to the lattice of order ideals of a unique finite partial order. Since the exploration space ((Q,⪯),⊆)(K(Q, ), ) is a finite distributive lattice (Proposition 3.6), it is canonically identified with the ideal lattice of (Q,⪯)(Q, ), connecting the framework to FCA and enabling direct use of concept lattice visualization tools and incremental construction algorithms. Constraint-Based Recommender Systems Constraint-based recommender systems (Felfernig et al., 2006, 2011) (CBRS) encode a formalized domain model—a set of logical constraints over item attributes—and use constraint reasoning to identify items consistent with user requirements and domain rules. EST shares with constraint-based recommendation the commitment to an explicit domain model and associated interpretability and correctness guarantees. However, the frameworks differ fundamentally. Constraint-based systems model compatibility constraints at a single decision point—a one-shot filtering problem with a static user requirement set. EST models temporal prerequisite dependencies across multiple time steps: accessibility depends on the user’s cumulative exploration trajectory, a dynamic object changing with each confirmed visit. Moreover, constraint-based systems use attribute-based constraints (“the item must have property P”), while EST uses order-based prerequisites that generate the lattice structure underlying all algorithmic guarantees. Cold-Start in Recommender Systems Cold-start arises when interaction data is absent for a user or item (Schein et al., 2002). Standard mitigation strategies include content-based bootstrapping, demographic filtering, active learning, and stereotype-based initialization. In the LBRS context, a new user in an unfamiliar city faces cold-start in two senses simultaneously: no city-specific interaction history and no established position in the exploration state space. The KST framework offers a qualitatively different cold-start mechanism: Fringe(∅)=q∈Q:∄p∈Q with p≺qFringe( )=\q∈ Q: \,p∈ Q with p q\ comprises POIs with no prerequisites, unconditionally accessible to any user. These are the natural entry points into the Exploration Space, identified directly from the surmise relation without any interaction data. This structural strategy is not an approximation but an exact consequence of the mathematical definition. It provides a formal validity guarantee conditional on the correctness of the surmise relation ⪯ , a type of structural guarantee that purely statistical cold-start strategies do not provide. Summary and Positioning To the best of our knowledge, no existing LBRS paradigm simultaneously models (i) explicit prerequisite dependencies between POIs, (i) a formal user exploration state evolving through the exploration space as visits occur, (i) multi-step path recommendation grounded in both preferences and structural accessibility, and (iv) a principled cold-start strategy derived from the mathematical structure of the domain model. The combination of these four properties is the defining contribution of EST. Table 1 summarizes this positioning. Table 1: Structural positioning of ESRS relative to surveyed LBRS paradigms. ✓ = supported by design; ∘ = partially or approximately supported; × = not supported. All entries reflect design properties, not performance claims. Structural dimension CF/ Content Markov/ RNN/Transf. TTDP CBRS ESRS (ours) Explicit prerequisite dependencies × × × ∘ ✓ Dynamic structured exploration state × × × × ✓ Formal mathematical foundation ∘ ∘ ✓ ✓ ✓ Multi-step path respecting dependencies × ∘ ✓ × ✓ Structural cold-start from domain model × × × ∘ ✓ Formal Foundations of Exploration Space Theory Core Definitions and Conceptual Translation 3.1.1 The Conceptual Parallel In KST, a knowledge state is a set of items a learner has mastered. The collection of all realizable states is not the full power set but a structured family reflecting prerequisite dependencies. EST transposes this to the urban exploration context: (i) an exploration item is a Point of Interest; (i) an exploration state is a set of POIs a user has meaningfully visited; (i) some POIs presuppose others in the sense that the experiential value of a visit is substantially reduced without prior engagement with their prerequisites. 3.1.2 Primary Definitions Definition 3.1 (Exploration Structure and Exploration Space). An exploration structure is a pair (Q,)(Q,K) where Q is a finite non-empty set of exploration items (Points of Interest) and ⊆2QK 2^Q is a family of exploration states, satisfying ∅∈ and Q∈Q . An exploration structure (Q,)(Q,K) is an exploration space if K is closed under arbitrary unions: ∀Kλ∈Λ⊆:⋃λ∈ΛKλ∈.∀\,\K_λ\_λ∈ : _λ∈ K_λ . It is an exploration learning space if K is additionally closed under arbitrary non-empty intersections (we adopt the strong formulation of learning spaces as in Falmagne and Doignon (2011, Ch. 3)): ∀∅≠Kλ∈Λ⊆:⋂λ∈ΛKλ∈.∀\, ≠\K_λ\_λ∈ : _λ∈ K_λ . Definition 3.2 (Surmise Relation on Exploration Items). A surmise relation ⪯ on Q is a partial order: reflexive, transitive, and antisymmetric. The semantic interpretation is: q⪯q′q q means that engaging meaningfully with q′q presupposes prior meaningful engagement with q. We write q≺q′q q for the strict part and q⋖q′q q for the covering relation. The directed graph of covering relations is the Hasse diagram H=(Q,EH)H=(Q,E_H). Reflexivity encodes that a POI always presupposes itself. Transitivity encodes the chaining of prerequisites: if engaging with the Art Gallery requires the City Museum, and the Rooftop Bar requires the Art Gallery, then the Rooftop Bar also requires the City Museum. Antisymmetry rules out circular prerequisites. In the presence of cycles, items would collapse into equivalence classes under mutual dependence, and the intended prerequisite semantics would be ill-defined. Definition 3.3 (Valid Exploration State, Order Ideal, and Principal Ideal). A subset K⊆QK Q is a valid exploration state with respect to (Q,⪯)(Q, ) if it is downward closed (an order ideal): ∀q,q′∈Q:q⪯q′andq′∈K⟹q∈K.∀\,q,q ∈ Q: q q \;and\;q ∈ K\; \;q∈ K. The principal ideal generated by q∈Qq∈ Q is: ↓q=p∈Q:p⪯q. q=\p∈ Q:p q\. We denote by (Q,⪯)K(Q, ) the family of all valid exploration states. 3.1.3 Types of Prerequisite Dependency The surmise relation may encode four qualitatively different types of dependency in the urban context: (i) geographical containment (a specialist archive nested within an old town presupposes an embodied sense of place); (i) thematic progression (an artisanal cooperative is most meaningful to a visitor who has developed, at the city’s main market, a sense of the broader food culture); (i) institutional or logistical sequencing (a visitor center provides orientation scaffolding for subsequent exploration); (iv) data-driven inference (sequential regularities in historical trajectory data serve as an empirical signal, subject to expert validation). 3.1.4 Structural Properties Two properties of the surmise relation are important. Sparsity: most pairs of POIs have no prerequisite relationship. Sparsity directly controls the computational tractability of the exploration space and the degree to which recommendations are structurally constrained. Semantic vs. Euclidean topology: the surmise relation is entirely independent of geographic distance. Two adjacent POIs may be semantically unrelated under ⪯ , while two distant POIs may be strongly prerequisite-linked. The surmise relation encodes a topology of meaning orthogonal to the physical city. The Exploration Space as a Well-Graded Learning Space Proposition 3.4 (Exploration Space is a Well-Graded Learning Space). Let Q be a finite non-empty set and ⪯ a surmise relation on Q. The pair (Q,(Q,⪯))(Q,K(Q, )) is an exploration learning space satisfying: (i) ∅∈ and Q∈Q ; (i) K is closed under arbitrary unions; (i) K is closed under arbitrary non-empty intersections; (iv) K is well-graded: for any K∈K with K≠∅K≠ , there exists a sequence ∅=K0⊂K1⊂⋯⊂Km=K =K_0⊂ K_1⊂·s⊂ K_m=K with m=|K|m=|K|, where Kj+1∖Kj=pjK_j+1 K_j=\p_j\ and pj∈Fringe(Kj)p_j (K_j) for all j. Proof. (i). ∅ satisfies downward closure vacuously. Q contains every element of the domain by definition. (i). Let K=⋃λKλK= _λK_λ. If q⪯q′q q and q′∈Kq ∈ K, then q′∈Kλ0q ∈ K_ _0 for some λ0 _0. Since Kλ0K_ _0 is an order ideal, q∈Kλ0⊆Kq∈ K_ _0 K. (i). Let K=⋂λKλK= _λK_λ (non-empty family). If q⪯q′q q and q′∈Kq ∈ K, then q′∈Kλq ∈ K_λ for every λ, so q∈Kλq∈ K_λ for every λ, giving q∈Kq∈ K. (iv). We use the following claim: for any non-empty order ideal K and any maximal element m of K under ⪯ , the element m belongs to Fringe(K∖m)Fringe(K \m\). Indeed, for any p≺mp m strictly, downward closure of K gives p∈Kp∈ K, and p≠mp≠ m gives p∈K∖mp∈ K \m\. Moreover K∖mK \m\ is itself an order ideal: for any q⪯q′q q with q′∈K∖mq ∈ K \m\, downward closure of K gives q∈Kq∈ K, and q=mq=m would require m⪯q′m q , i.e. m≺q′m q (since q′≠mq ≠ m), with q′∈Kq ∈ K—contradicting the maximality of m in K. Hence q≠mq≠ m and q∈K∖mq∈ K \m\. Starting from K, iteratively remove maximal elements to produce a decreasing chain terminating at ∅ in exactly |K||K| steps; reversing gives the required increasing sequence. ■ Remark 3.5 (What the Learning Space Property Enables). Part (i) establishes that (Q,⪯)K(Q, ) is an exploration space, ensuring the structure is non-trivial. Part (i), closure under intersection, makes (,⊆)(K, ) a complete lattice (Proposition 3.6), enabling the memoization strategy in the DP algorithm: states are lattice elements identifiable via their set representation without ambiguity. Part (iv) is the guarantee most directly relevant to recommendation experience: for any valid state K, the system can always reach K by single-step fringe additions, and the recommendation pipeline can never reach a valid state from which no single-step progress is possible (unless the user is at Q). An additional consequence is that (,⊆)(K, ) is graded: all maximal chains between two comparable states K⊆K′K K have the same length |K′|−|K||K |-|K|. This follows from Proposition 3.4(iv): applying the well-graded property to K gives a chain of length |K||K| from ∅ to K, and applied to K′K gives a chain of length |K′||K | from ∅ to K′K ; every maximal chain from K to K′K therefore has length |K′|−|K||K |-|K|, independent of the path taken. The “distance” between exploration states is thus well-defined and path-independent. Distributive Lattice Structure and Connection to Formal Concept Analysis Proposition 3.6 (Distributive Lattice). The exploration space ((Q,⪯),⊆)(K(Q, ), ) is a finite distributive lattice with meet K∧K′=K∩K′K K =K∩ K , join K∨K′=K∪K′K K =K∪ K , bottom 0^=∅ 0= , and top 1^=Q 1=Q. Proof. Proposition 3.4(i,i) establishes that K∪K′K∪ K and K∩K′∈K∩ K for any K,K′∈K,K . K∪K′K∪ K is the least upper bound: it contains both K and K′K , and any K′∈K satisfying K⊆K′K K and K′⊆K′K K satisfies K∪K′⊆K′K∪ K K . Symmetrically, K∩K′K∩ K is the greatest lower bound. Distributivity follows from the set-theoretic identity K∪(K′∩K′)=(K∪K′)∩(K∪K′)K∪(K ∩ K )=(K∪ K )∩(K∪ K ) applied to the set-theoretic realizations of the lattice operations. ■ Remark 3.7 (Birkhoff’s Representation Theorem and Join-Irreducibles). Birkhoff’s theorem (Birkhoff, 1937; Davey and Priestley, 2002) states that every finite distributive lattice is isomorphic to the lattice of order ideals of its poset of join-irreducible elements. Identification of join-irreducibles. We claim the join-irreducible elements of ((Q,⪯),⊆)(K(Q, ), ) are precisely the principal ideals ↓q q for q∈Qq∈ Q. ↓q q is an order ideal: if p⪯p′p p and p′∈↓qp ∈ q, then p′⪯qp q and by transitivity p⪯qp q, so p∈↓qp∈ q. ↓q q is join-irreducible: suppose ↓q=I1∪I2 q=I_1∪ I_2 with I1,I2∈I_1,I_2 and I1,I2⊊↓qI_1,I_2 q (non-trivial decomposition). Since q∈I1∪I2q∈ I_1∪ I_2, say q∈I1q∈ I_1. Then I1I_1 contains q and is an order ideal, so ↓q⊆I1 q I_1, giving I1=↓qI_1= q, contradicting the hypothesis I1⊊↓qI_1 q. Every join-irreducible is a principal ideal: in a lattice of order ideals ordered by inclusion, a join-irreducible element K must have a unique maximal element m. Indeed, if K had two distinct maximal elements m1,m2m_1,m_2, then K=↓m1∪↓m2K= m_1∪ m_2 would be a non-trivial join decomposition, contradicting join-irreducibility. Hence K=↓mK= m. The map φ:q↦↓q :q q is an order isomorphism from (Q,⪯)(Q, ) to the join-irreducible poset of (,⊆)(K, ): injectivity follows from antisymmetry, and order preservation from transitivity. Applying Birkhoff’s theorem, ((Q,⪯),⊆)(K(Q, ), ) is the unique finite distributive lattice (up to isomorphism) whose join-irreducible poset is (Q,⪯)(Q, ). Practical consequences. (i) Compactness: the entire lattice is encoded by the n-element partial order (Q,⪯)(Q, ), enabling fringe computation without state enumeration. (i) Connection to FCA: the lattice (,⊆)(K, ) is formally identical in structure to a concept lattice, making the full toolkit of FCA—visualization software, incremental construction algorithms—directly applicable. (i) Hasse diagram as computational substrate: covering relations in (Q,⪯)(Q, ) suffice for all ESRS computations, as shown in Proposition 3.10. The Exploration Fringe Definition 3.8 (Exploration Fringe). Given a valid exploration state K∈(Q,⪯)K (Q, ), the exploration fringe is: Fringe(K)=q∈Q∖K|↓q∖q⊆K.Fringe(K)\;=\; \q∈ Q K\; |\; q \q\ K \. Equivalently, Fringe(K)Fringe(K) is the set of minimal elements of (Q∖K,⪯↾Q∖K)(Q K, \! _Q K). Operational interpretation. q∈Fringe(K)q (K) if and only if K∪q∈K∪\q\ (proved in Lemma 3.9). The fringe precisely identifies the set of POIs the system can recommend as next steps without creating an invalid exploration state. Lemma 3.9 (Fringe Transitions Preserve Validity). For any K∈(Q,⪯)K (Q, ) and q∈Fringe(K)q (K), we have K∪q∈(Q,⪯)K∪\q\ (Q, ). Proof. Let K′=K∪qK =K∪\q\. Let p⪯q′p q with q′∈K′q ∈ K . If q′∈Kq ∈ K, then p∈K⊆K′p∈ K K by downward closure of K. If q′=q =q: if p=qp=q then p∈K′p∈ K ; if p≠qp≠ q then p≺qp q strictly, so p∈↓q∖q⊆K⊆K′p∈ q \q\ K K by the fringe condition. ■ Proposition 3.10 (Efficient Fringe Computation). Let H=(Q,EH)H=(Q,E_H) be the Hasse diagram of ⪯ and assume O(1)O(1) membership testing for K. Given any valid state K, the fringe Fringe(K)Fringe(K) can be computed in O(n+|EH|)O(n+|E_H|) time. When K is updated by adding a single item q∗q^*, the fringe can be updated incrementally in O(degH+(q∗))O(deg_H^+(q^*)) time. Proof. Batch computation. The fringe condition q∈Fringe(K)q (K) requires all lower covers of q in H to be in K (checking lower covers suffices because in a finite poset every predecessor of q lies below some lower cover of q, and downward closure then propagates membership through transitivity). Algorithm: (1) initialize counter array cnt[q]←0cnt[q]← 0 for all q∈Q∖Kq∈ Q K (O(n)O(n)); (2) for each (p,q)∈EH(p,q)∈ E_H with p,q∉Kp,q∉ K, increment cnt[q]cnt[q] (O(|EH|)O(|E_H|)); (3) return q∈Q∖K:cnt[q]=0\q∈ Q K:cnt[q]=0\ (O(n)O(n)). Incremental update. Assuming the counter array cntcnt is maintained across state updates, when q∗q^* is added to K: for each successor s with q∗⋖sq^* s, decrement cnt[s]cnt[s]; if cnt[s]cnt[s] reaches 0 and s∉K∪q∗s∉ K∪\q^*\, add s to the fringe. Remove q∗q^* from the fringe. Cost: O(degH+(q∗))O(deg_H^+(q^*)). ■ q1q_1: City Museumq2q_2: Latin Quarterq4q_4: Art Galleryq3q_3: Med. Libraryq5q_5: Rooftop Bar≺ ≺ ≺ (a) Hasse diagram of (Q,⪯)(Q, )∅ q1\q_1\q2\q_2\q1,q4\q_1,q_4\q1,q2\q_1,q_2\q2,q3\q_2,q_3\… (12 states total)Q=q1,q2,q3,q4,q5Q=\q_1,q_2,q_3,q_4,q_5\(b) Lattice (,⊆),||=12(K, ),|K|=12 Figure 1: (a) Hasse diagram of the surmise relation on Q=q1,…,q5Q=\q_1,…,q_5\ with covering relations q1⋖q4⋖q5q_1 q_4 q_5 and q2⋖q3q_2 q_3. Items q1q_1 and q2q_2 have no predecessors and form Fringe(∅)Fringe( ). (b) The resulting distributive lattice of valid exploration states. By Remark 3.7, the join-irreducible elements are the five principal ideals ↓q1=q1 q_1=\q_1\, ↓q2=q2 q_2=\q_2\, ↓q3=q2,q3 q_3=\q_2,q_3\, ↓q4=q1,q4 q_4=\q_1,q_4\, ↓q5=q1,q4,q5 q_5=\q_1,q_4,q_5\. The 12 valid states result from multiplicativity of ideal counts: since the poset is the disjoint union of two independent chains, its ideal lattice is the direct product of their ideal lattices. The chain q1≺q4≺q5q_1 q_4 q_5 generates 4 ideals and q2≺q3q_2 q_3 generates 3, giving 4×3=124× 3=12. State Transitions and Path Validity Corollary 3.11 (Path Validity). Let K0∈(Q,⪯)K_0 (Q, ) and let π=(q1,…,qk)π=(q_1,…,q_k) satisfy, for each j: qj∈Fringe(Kj−1)q_j (K_j-1) and Kj=Kj−1∪qjK_j=K_j-1∪\q_j\. Then Kj∈(Q,⪯)K_j (Q, ) for all j, and the items q1,…,qkq_1,…,q_k are pairwise distinct. Proof. Validity: by induction, Lemma 3.9 gives Kj∈K_j from Kj−1∈K_j-1 and qj∈Fringe(Kj−1)q_j (K_j-1). Distinctness: qj∈Q∖Kj−1q_j∈ Q K_j-1 implies qj∉q1,…,qj−1⊆Kj−1q_j∉\q_1,…,q_j-1\ K_j-1. ■ Corollary 3.11 is the safety certificate of the ESRS recommendation algorithm. Any path generated by sequential fringe selection (i) respects the prerequisite structure by construction, without any explicit constraint-checking step, and (i) never recommends the same POI twice. A further structural consequence—sub-path optimality of the dynamic program over (,⊆)(K, )—is established in Proposition 5.4 once the Bellman formulation is introduced (§5.3). System Architecture The Exploration Space Recommender System (ESRS) comprises three interconnected components (Figure 2): the Location Database, the User Modeling Component, and the Recommendation Engine. These interact through the Exploration Space (Q,,⪯)(Q,K, ). Exploration Space (Q,,⪯)(Q,K, ) Fringe, lattice, transitions Recommendation Engine Assessment → Fringe → DP / Rank User Interface & Feedback Paths, rankings, check-ins Location Database POIs, attributes, surmise ⪯ User Modeling Eu(t)E_u(t), Pu(K)P_u(K), u(t)p_u(t) POI datauser statestructurerecommendationsattributesfeedback loop Figure 2: High-level architecture of ESRS. The Exploration Space (Q,,⪯)(Q,K, ) serves as the shared structural backbone, populated from the Location Database and navigated by the Recommendation Engine in light of the User Modeling Component. Location Database The surmise relation ⪯ is treated as a first-class citizen of the data model, stored explicitly as directed edges alongside standard POI attributes. Each POI Li∈QL_i∈ Q is characterized by: unique identifier and coordinates (xi,yi)(x_i,y_i); hierarchical category CatiCat_i; normalized popularity Popi∈[0,1]Pop_i∈[0,1] and review score Revi∈[0,1]Rev_i∈[0,1]; static context (opening hours, admission policy); dynamic context (event feeds); and surmise links (Li≺Lj)(L_i L_j) derived from Algorithm 5 subject to expert validation. For new POIs, we define a soft neighborhood function: Nf(Li)=Lj∈Q:simcat(Li,Lj)>θ1ordist(Li,Lj)<θ2,N_f(L_i)=\L_j∈ Q:sim_cat(L_i,L_j)> _1\;or\;dist(L_i,L_j)< _2\, where simcatsim_cat measures category overlap (e.g., Jaccard on category hierarchy) and distdist is geographic distance. This neighborhood is used for initial placement and for identifying candidate POIs for potential surmise relations. A graph database backend (e.g., Neo4j) is appropriate for efficient DAG traversal, integrated with a geospatial layer (e.g., PostGIS) for spatial queries. User Modeling Component The User Modeling Component maintains three inter-related objects. Confirmed exploration state Eu(t)E_u(t) The set of POIs user u has been confirmed to have meaningfully visited by time t, operationalized via high-confidence engagement signals (deliberate check-in, dwell time above threshold θd+ _d^+, explicit rating). A strict invariant is maintained: Eu(t)E_u(t) is updated exclusively upon reception of a high-confidence signal and never overwritten by a probabilistic estimate. This preserves the structural integrity of the exploration space; since only fringe items are ever recommended (Algorithm 1) and Corollary 3.11 ensures fringe-guided transitions remain within K, the confirmed state can never violate the surmise relation. Probabilistic state distribution PuP_u and working state E^u E_u Because users visit POIs without registering check-ins, ESRS maintains a probability distribution Pu:→[0,1]P_u:K→[0,1] inspired by BLIM (Falmagne and Doignon, 1988). Upon observing an interaction pattern r, the distribution is updated by Bayes’ rule: Pu(K∣)∝P(∣K)⋅Pu(K),P_u(K )\; \;P(r K)· P_u(K), where the BLIM likelihood factorizes as: P(∣K)=∏i:ri=1[(1−βi)[i∈K]βi[i∉K]]⋅∏i:ri=0[ηi[i∈K](1−ηi)[i∉K]],P(r K)= _i:\,r_i=1 [(1- _i)^1[i∈ K]\, _i^1[i∉ K] ]· _i:\,r_i=0 [ _i^1[i∈ K]\,(1- _i)^1[i∉ K] ], with false-positive rate βi _i (the probability of a positive signal without a meaningful visit) and false-negative rate ηi _i (the probability of no digital signal despite a meaningful visit). The MAP estimate E^u=argmaxK∈Pu(K∣) E_u= *arg\,max_K P_u(K ) is the working state: used for fringe computation and path optimization, discarded at end of each cycle. When |||K| is too large for exact enumeration, beam-search estimation retains only the B most probable states and renormalizes. For c independent components with chain heights h1,…,hch_1,…,h_c, we have ||=∏i=1c(hi+1)|K|= _i=1^c(h_i+1); for example, with c=5c=5 components each of height hi=3h_i=3, ||≤45=1024|K|≤ 4^5=1024, which is fully tractable. Setting B∈100,500B∈\100,500\ achieves near-optimal MAP estimation in practice (Desmarais and Baker, 2012). Preference vector u(t)p_u(t) Individual affinities for POIs, updated via exponential moving average: pu,i(t+1)=pu,i(t)+ℓr⋅(Iobs−pu,i(t)),ℓr∈(0,1],p_u,i(t+1)=p_u,i(t)+ _r· (I_obs-p_u,i(t) ), 18.49988pt _r∈(0,1], where Iobs∈[0,1]I_obs∈[0,1] encodes normalized dwell time or rating. For POIs not yet encountered, a latent factor model trained on the interaction matrix R≈U⋅VTR≈ U· V^T provides the prior. The Unified Interest Score ℐ(u,Li,E^u)=wα⋅Prefu,i+wβ⋅Propi+wγ⋅Collabu,i+wδ⋅Rel(Li,E^u),I(u,L_i, E_u)\;=\;w_α·Pref_u,i+w_β·Prop_i+w_γ·Collab_u,i+w_δ·Rel(L_i, E_u), (1) with wα+wβ+wγ+wδ=1w_α+w_β+w_γ+w_δ=1, all coefficients non-negative, and all component scores in [0,1][0,1]. User preference Prefu,iPref_u,i A weighted combination of explicit feedback (ratings, bookmarks) and implicit behavioral proxies (dwell time, click-through, check-in frequency), with matrix factorization estimate R^ui R_ui as prior for unvisited POIs. Location properties Propi=wcCi+wrPopi+wsReviProp_i=w_cC_i+w_rPop_i+w_sRev_i where wc+wr+ws=1w_c+w_r+w_s=1 with all coefficients non-negative, ensuring Propi∈[0,1]Prop_i∈[0,1]. Category relevance Ci∈[0,1]C_i∈[0,1] measures the overlap between CatiCat_i and the user’s inferred category preferences (e.g., Jaccard similarity between CatiCat_i and Catj:Lj∈E^u\Cat_j:L_j∈ E_u\, with a content-based prior for new users). Normalized popularity PopiPop_i and review score ReviRev_i are defined in §4.1. This component is particularly important in cold-start regimes where no preference data is available. Collaborative signal Collabu,iCollab_u,i User similarity measured via regularized Jaccard: Simu,v=|Eu∩Ev|+ε|Eu∪Ev|+ε,Sim_u,v= |E_u∩ E_v|+ |E_u∪ E_v|+ , where ε>0 >0 (typically ε=1 =1) ensures stability; for Eu=Ev=∅E_u=E_v= , Simu,v=1Sim_u,v=1. For new users, a hybrid similarity combines this with preference-vector cosine: Simu,vhybrid=λsSimu,v+(1−λs)u⋅v‖u‖‖v‖,Sim^hybrid_u,v= _sSim_u,v+(1- _s) p_u·p_v\|p_u\|\|p_v\|, where λs:ℕ→[0,1] _s:N→[0,1] satisfies λs(0)=0 _s(0)=0 and λs(t)→1 _s(t)→ 1 as |Eu(t)||E_u(t)| grows (e.g., λs(t)=1−e−|Eu(t)|/κ _s(t)=1-e^-|E_u(t)|/κ for κ>0κ>0), ensuring Simu,vhybridSim^hybrid_u,v reduces to cosine similarity at system bootstrap. The collaborative signal is then: Collabu,i=∑v∈uSimu,vhybrid⋅Prefv,i∑v∈uSimu,vhybrid.Collab_u,i= _v _uSim^hybrid_u,v·Pref_v,i _v _uSim^hybrid_u,v. Proposition 4.1 (Cold-Start Robustness of the Collaborative Signal). For any user u with Eu(t0)=∅E_u(t_0)= and u(t0)≠p_u(t_0) 0, the collaborative signal Collabu,iCollab_u,i is well-defined. It is strictly positive for any POI LiL_i with at least one neighbor v∗∈uv^* _u satisfying Prefv∗,i>0Pref_v^*,i>0 and v∗≠p_v^* 0. Proof. With Eu(t0)=∅E_u(t_0)= , we have |Eu(t0)|=0|E_u(t_0)|=0, so by definition λs(0)=0 _s(0)=0 and Simu,vhybrid=u⋅v‖u‖‖v‖Sim^hybrid_u,v= p_u·p_v\|p_u\|\,\|p_v\|, the cosine similarity. Since preference scores lie in [0,1][0,1], the cosine is non-negative; it is strictly positive whenever u≠p_u 0 and v≠p_v 0. The denominator ∑v∈uSimu,vhybrid _v _uSim^hybrid_u,v is strictly positive whenever |u|≥1|U_u|≥ 1 and u≠p_u 0, so Collabu,iCollab_u,i is well-defined. Non-zero: by hypothesis there exists v∗∈uv^* _u with Prefv∗,i>0Pref_v^*,i>0. If v∗≠p_v^* 0 and u≠p_u 0, then Simu,v∗hybrid>0Sim^hybrid_u,v^*>0, and the numerator ∑vSimu,vhybrid⋅Prefv,i≥Simu,v∗hybrid⋅Prefv∗,i>0 _vSim^hybrid_u,v·Pref_v,i ^hybrid_u,v^*·Pref_v^*,i>0. ■ State-relative structural accessibility Rel(Li,E^u)Rel(L_i, E_u) Rel(Li,E^u)=|↓Li∩E^u||↓Li|.Rel(L_i, E_u)\;=\; | L_i∩ E_u|| L_i|. (2) This equals 1 if and only if Li∈E^uL_i∈ E_u: since E^u E_u is an order ideal, Li∈E^uL_i∈ E_u implies ↓Li⊆E^u L_i E_u, giving |↓Li∩E^u|=|↓Li|| L_i∩ E_u|=| L_i|; conversely, since Li∈↓LiL_i∈ L_i by reflexivity of ⪯ , Li∉E^uL_i∉ E_u implies Li∉↓Li∩E^uL_i∉ L_i∩ E_u, so |↓Li∩E^u|≤|↓Li|−1<|↓Li|| L_i∩ E_u|≤| L_i|-1<| L_i|. For a fringe item Li∈Fringe(E^u)L_i ( E_u), we have ↓Li∖Li⊆E^u L_i \L_i\ E_u and Li∉E^uL_i∉ E_u, so Rel(Li,E^u)=(|↓Li|−1)/|↓Li|Rel(L_i, E_u)=(| L_i|-1)/| L_i|: the score is strictly less than 1 but approaches 1 as the depth of LiL_i grows. For prerequisite-free fringe items (|↓Li|=1| L_i|=1, i.e., ↓Li=Li L_i=\L_i\), the score is 0 regardless of E^u E_u—they are structurally accessible but have no visited prerequisites to reference. The score provides a graded measure of proximity to accessibility for non-fringe items; for fringe items it encodes prerequisite depth, with deeper items receiving a higher score. The Recommendation Engine (Algorithm 1) restricts ranking and path optimization to F=Fringe(E^u)F=Fringe( E_u). Within the fringe, RelRel contributes to ℐI via the wδw_δ term: it assigns higher scores to items whose prerequisite chains are deeper, providing a gradient of structural proximity even among accessible items. For prerequisite-free fringe items (|↓Li|=1| L_i|=1), this term is uniformly zero; the other three components of ℐI carry the full discriminative weight. Cold-Start Strategies 4.4.1 New Users Strategy 1—Structural onboarding. Fringe(∅)=q∈Q:∄p∈Q with p≺qFringe( )=\q∈ Q: \,p∈ Q with p q\ comprises POIs with no prerequisites, unconditionally accessible to any user. Proposition 4.2 (Structural Cold-Start Guarantee). For any surmise relation (Q,⪯)(Q, ) and any user u with Eu(t0)=∅E_u(t_0)= , the set Fringe(∅)Fringe( ) is non-empty, and q∈(Q,⪯)\q\ (Q, ) for all q∈Fringe(∅)q ( ). Proof. Since Q is finite and non-empty, any partial order on Q has at least one minimal element under ≺ (the finiteness of Q guarantees well-foundedness, which precludes infinite descending chains and hence ensures minimal elements exist), so Fringe(∅)Fringe( ) is non-empty. For q∈Fringe(∅)q ( ): ↓q∖q=∅⊆∅ q \q\= , so q\q\ is valid by Lemma 3.9. ■ A lightweight questionnaire maps stated interests to categories in Fringe(∅)Fringe( ), initializing recommendations using the wβw_β component of the interest score. This constitutes knowledge-based recommendation (Burke, 2002): principled recommendations before any user data is collected, with a formal validity guarantee conditional on the correctness of the inferred surmise relation ⪯ (see Limitation L5). Strategy 2—Popularity bootstrapping. When the user declines the questionnaire, set wα=wγ=wδ=0w_α=w_γ=w_δ=0, wβ=1w_β=1, ranking Fringe(∅)Fringe( ) by inherent attractiveness. Weights are progressively rebalanced toward preference- and collaborative-based components as interactions accumulate, via wα(t)=wα∞(1−e−t/τ)w_α(t)=w_α^∞(1-e^-t/τ). Strategy 3—Stereotype initialization. Map new users to exploration archetypes (Cultural Discoverer, Culinary Explorer, Historical Researcher) based on available contextual signals, initializing u(t0)p_u(t_0) from the corresponding cluster centroid (Schein et al., 2002). 4.4.2 New POIs New POI LnewL_new is initially placed in Fringe(∅)Fringe( ) with no surmise links (conservative placement guaranteeing no artificial structural constraints). It is included in the soft neighborhood Nf(Lj)N_f(L_j) for its most similar existing POIs via the neighborhood function defined in §4.1. As trajectory data accumulates, Algorithm 5 is re-executed with LnewL_new included, and candidate surmise relations are integrated via the incremental update of Proposition 3.10 after expert validation. Recommendation Algorithm Notational discipline. Eu(t)∈E_u(t) denotes the confirmed exploration state, updated exclusively upon high-confidence signals. E^u∈ E_u denotes the working state (MAP estimate, computed at the start of each cycle and discarded at its end). Pu:→[0,1]P_u:K→[0,1] denotes the state distribution. The confirmed state is never directly overwritten by any probabilistic estimate. We use ηi∈(0,1) _i∈(0,1) exclusively for the BLIM false-negative rate of item LiL_i, and ℓr∈(0,1] _r∈(0,1] for the preference learning rate. The Full ESRS Pipeline Algorithm 1 ESRS Recommendation Pipeline 1:User u; confirmed state Eu(t)∈E_u(t) ; distribution PuP_u; preference vector u(t)p_u(t); exploration space (Q,,⪯)(Q,K, ); Location Database D; mode ∈Path,Rank∈\ Path, Rank\; max steps kmaxk_ ; beam width B; diversity weights (wN,wD)(w_N,w_D) 2:Recommended path π∗π^* or diversified ranked list ℛR 3:// Phase 1: State Assessment 4:(Pu,E^u)←BLIMAssess(Pu,recent,B)(P_u,\, E_u)← BLIMAssess(P_u,r_recent,B) ⊳ PuP_u updated in-place; E^u E_u is the MAP estimate 5:E^u←E^u∪Eu(t) E_u← E_u∪ E_u(t) ⊳ Confirmed visits always present in working state 6:Compute ℐ(u,Li,E^u)I(u,L_i, E_u) via Eq. (1) for all Li∈QL_i∈ Q ⊳ Used directly in Rank mode; Path mode recomputes ℐ(u,q,K)I(u,q,K) at each DP node with the evolving state K (Algorithm 3) 7:// Phase 2: Fringe Construction 8:F←Fringe(E^u)F ( E_u) ⊳ O(n+|EH|)O(n+|E_H|); by Definition 3.8, Fringe(E^u)⊆Q∖E^uFringe( E_u) Q E_u; Proposition 3.10 9:if F=∅F= then 10: emit “Exploration complete; propose new semantic cluster or city area” 11: return ∅ 12:end if 13:// Phase 3a: Optimal Path 14:if mode =Path= Path then 15: return DPPath(E^u,kmax,B) DPPath( E_u,k_ ,B) ⊳ Algorithm 3; fringe computed internally 16:end if 17:// Phase 3b: Diversified Ranking 18:if mode =Rank= Rank then 19: return DiverseRank(u,F,E^u,kmax,wN,wD) DiverseRank(u,F, E_u,k_ ,w_N,w_D) ⊳ Algorithm 4 20:end if Remark 5.1 (Confirmed state invariant). Line 3 merges E^u E_u with Eu(t)E_u(t), ensuring Eu(t)⊆E^uE_u(t) E_u. Since Eu(t)∈E_u(t) and E^u∈ E_u , and K is closed under arbitrary unions (Proposition 3.4(i)), the union E^u∪Eu(t)∈ E_u∪ E_u(t) . The working state is discarded at the end of the pipeline and never written back to Eu(t)E_u(t); only Algorithm 7 may update the confirmed state, exclusively on high-confidence signals. Probabilistic State Estimation Definition 5.2 (Engagement signal and response vector). Let A⊆QA Q be a set of assessed items. For each Li∈AL_i∈ A, the engagement signal ri∈0,1r_i∈\0,1\ indicates positive engagement (ri=1r_i=1: dwell time above θd _d, explicit check-in, or user-initiated rating). A signal ri=1r_i=1 is high-confidence if it additionally satisfies dwell time above θd+>θd _d^+> _d or an explicit rating. The BLIM likelihood under local independence is: ℓ(∣K)=∏i:ri=1[(1−βi)[Li∈K]⋅βi[Li∉K]]⋅∏i:ri=0[ηi[Li∈K]⋅(1−ηi)[Li∉K]]. (r K)= _i:\,r_i=1 [(1- _i)^1[L_i∈ K]· _i^1[L_i∉ K] ]· _i:\,r_i=0 [ _i^1[L_i∈ K]·(1- _i)^1[L_i∉ K] ]. (3) The Bayesian posterior is Pu(K∣)∝ℓ(∣K)⋅Pu(K)P_u(K ) (r K)· P_u(K). Algorithm 2 BLIM State Estimation (Exact and Beam Approximation) 1:Distribution PuP_u; response vector r over A; BLIM parameters βi,ηi\ _i, _i\; beam width B 2:Updated distribution Pu′P_u ; MAP estimate E^u E_u 3:ℬ←top-B states by Pu(⋅)B -B states by P_u(·) 4:for all K∈ℬK do 5: P~(K)←Pu(K) P(K)← P_u(K) 6: P~(K)←P~(K)⋅∏i∈A:ri=1[(1−βi)[Li∈K]βi[Li∉K]] P(K)← P(K)· _i∈ A:\,r_i=1 [(1- _i)^1[L_i∈ K] _i^1[L_i∉ K] ] 7: P~(K)←P~(K)⋅∏i∈A:ri=0[ηi[Li∈K](1−ηi)[Li∉K]] P(K)← P(K)· _i∈ A:\,r_i=0 [ _i^1[L_i∈ K](1- _i)^1[L_i∉ K] ] 8:end for 9:Z←∑K∈ℬP~(K)Z← _K P(K); Pu′(K)←P~(K)/ZP_u (K)← P(K)/Z for K∈ℬK , 0 otherwise 10:return Pu′P_u , E^u←argmaxK∈ℬPu′(K) E_u← *arg\,max_K P_u (K) Remark 5.3 (Validity of the beam approximation). With B<||B<|K|, the approximation error is controlled by the prior mass outside the beam, εB=1−∑K∈ℬPu(K) _B=1- _K P_u(K). If the true MAP state K∗K^* is in ℬB—which holds whenever the prior is sufficiently concentrated—the MAP estimate is exact. The MAP estimate E^u E_u is always a member of K (the argmax is taken within ℬ⊆B ). When the EM algorithm is used for parameter estimation, the beam approximation discards the probability mass of states outside ℬB. Provided B is chosen large enough to capture the vast majority of the posterior mass (e.g., B≥100B≥ 100), the impact on the M-step estimates is negligible; this is the common practice in BLIM applications (Desmarais and Baker, 2012). 5.2.1 EM Parameter Estimation When ground-truth labels are unavailable, EM alternates between: • E-step: compute Pu(K∣(s))P_u(K ^(s)) for each training sequence using current parameters. • M-step: update by closed-form maximization: β^i=∑s∑K∌LiPu(K∣(s))⋅[ri(s)=1]∑s∑K∌LiPu(K∣(s)), β_i= _s _K L_iP_u(K ^(s))·1[r_i^(s)=1] _s _K L_iP_u(K ^(s)), with a symmetric expression for η^i η_i, and Pu(K)∝∑sPu(K∣(s))P_u(K) _sP_u(K ^(s)). Convergence to a local maximum is guaranteed by the standard EM monotonicity argument under exact inference (Falmagne and Doignon, 1988); when the beam approximation is used in the E-step, the discarded posterior mass breaks the monotonicity guarantee, and convergence is not formally assured (see Remark 5.3). Dynamic Programming for Path Recommendation 5.3.1 Bellman Formulation and Value Function The value function V:×0,…,kmax→ℝV:K×\0,…,k_ \ satisfies the following Bellman recursion (Bellman, 1957): V(K,j)=0if j=0 or Fringe(K)=∅,maxq∈Fringe(K)[ℐ(u,q,K)+V(K∪q,j−1)]otherwise.V(K,j)= cases0&if j=0 or Fringe(K)= ,\\ _q (K) [I(u,q,K)+V(K∪\q\,j-1) ]&otherwise. cases (4) The policy is π∗(K,j)=argmaxq∈Fringe(K)[ℐ(u,q,K)+V(K∪q,j−1)]π^*(K,j)= *arg\,max_q (K) [I(u,q,K)+V(K∪\q\,j-1) ]. Proposition 5.4 (Sub-Path Optimality). Let π∗=(q1,…,qk)π^*=(q_1,…,q_k) be a path achieving V(E^u,k)V( E_u,k) under Bellman recursion (4), with K0=E^uK_0= E_u and Kj=Kj−1∪qjK_j=K_j-1∪\q_j\. For any 0≤j<k0≤ j<k, the sub-path (qj+1,…,qk)(q_j+1,…,q_k) achieves V(Kj,k−j)V(K_j,k-j), i.e., it is optimal for the sub-problem starting from state KjK_j with remaining horizon k−jk-j. Proof. Suppose for contradiction that for some j there exists a path (qj+1′,…,qk′)(q _j+1,…,q _k) from KjK_j with ∑ℓ=j+1kℐ(u,qℓ′,Kℓ−1′)>∑ℓ=j+1kℐ(u,qℓ,Kℓ−1) _ =j+1^kI(u,q _ ,K _ -1)> _ =j+1^kI(u,q_ ,K_ -1), where Kℓ′=Kj∪qj+1′,…,qℓ′K _ =K_j∪\q _j+1,…,q _ \. Then the path (q1,…,qj,qj+1′,…,qk′)(q_1,…,q_j,q _j+1,…,q _k) from E^u E_u achieves value strictly greater than V(E^u,k)V( E_u,k). By Corollary 3.11 all intermediate states Kℓ′K _ are valid, so this path is feasible—contradicting the optimality of π∗π^*. ■ 5.3.2 Memoization over the Lattice The value V(K,j)V(K,j) depends on K only through the identity of the set K, not on the path used to reach K. Consequently, if two traversal sequences reach the same state K with the same remaining horizon j, V(K,j)V(K,j) is computed only once. States are identified as sorted tuples of POI identifiers (canonical representation admitting O(n)O(n) hashing). A top-down recursive call on DPVal(K,j) DPVal(K,j) triggers DPVal(K∪q,j−1) DPVal(K∪\q\,j-1) before returning, guaranteeing that every sub-problem with a strictly larger state set (or smaller remaining horizon) is resolved before its parent. Each pair (K,j)(K,j) is evaluated at most once via the memo table. Algorithm 3 ESRS Path Recommendation via Memoized DP 1:Working state E^u E_u; horizon kmaxk_ ; beam width B 2:Optimal path π∗π^*; optimal value V∗V^* 3:Initialize ← memo←\\, ← pred←\\ 4:function DPVal(K,jK,j) 5: if (K,j)∈(K,j)∈ memo then return [(K,j)] memo[(K,j)] 6: end if 7: if j=0j=0 or Fringe(K)=∅Fringe(K)= then 8: return 0 9: end if 10: C←TopBFringe(K,B)C← TopBFringe(K,B) 11: q∗←argmaxq∈C[ℐ(u,q,K)+DPVal(K∪q,j−1)]q^*← *arg\,max_q∈ C [I(u,q,K)+ DPVal(K∪\q\,j-1) ] 12: [(K,j)]←q∗ pred[(K,j)]← q^* 13: [(K,j)]←ℐ(u,q∗,K)+[(K∪q∗,j−1)] memo[(K,j)] (u,q^*,K)+ memo[(K∪\q^*\,j-1)] 14: return [(K,j)] memo[(K,j)] 15:end function 16:V∗←DPVal(E^u,kmax)V^*← DPVal( E_u,k_ ) 17:π∗←[]π^*←[\,]; Kc←E^uK_c← E_u; jc←kmaxj_c← k_ 18:while jc>0j_c>0 and (Kc,jc)∈(K_c,j_c)∈ pred do 19: q∗←[(Kc,jc)]q^*← pred[(K_c,j_c)]; π∗.(q∗)π^* .append(q^*); Kc←Kc∪q∗K_c← K_c∪\q^*\; jc←jc−1j_c← j_c-1 20:end while 21:return π∗π^*, V∗V^* 22:procedure TopBFringe(K,BK,B) 23: FK←Fringe(K)F_K (K) 24: if B=∞B=∞ or |FK|≤B|F_K|≤ B then return FKF_K 25: else return top-B items in FKF_K by ℐ(u,⋅,K)I(u,·,K) 26: end if 27:end procedure Proposition 5.5 (Correctness of Memoized DP). Algorithm 3 with B=∞B=∞ computes V(E^u,kmax)V( E_u,k_ ) correctly and returns a path achieving this value. Each state-horizon pair (K,j)(K,j) is evaluated at most once. Proof. Correctness: by structural induction on j. Base case j=0j=0: DPVal(K,0)(K,0) returns 0, matching Eq. (4). Base case Fringe(K)=∅Fringe(K)= , j>0j>0: DPVal(K,j)(K,j) returns 0, matching the second clause of the base case in Eq. (4). Inductive step: assuming Fringe(K)≠∅Fringe(K)≠ and DPVal(K′,j−1)(K ,j-1) returns V(K′,j−1)V(K ,j-1) correctly for all K′K , the expression v∗=maxq∈C[ℐ(u,q,K)+DPVal(K∪q,j−1)]v^*= _q∈ C [I(u,q,K)+ DPVal(K∪\q\,j-1) ] evaluates the Bellman recursion (4) correctly (with C=Fringe(K)C=Fringe(K) when B=∞B=∞). Each pair evaluated at most once: the memo table check at the top of DPVal returns immediately on any revisit, so each (K,j)(K,j) pair triggers the recursive computation at most once. Termination follows because every recursive call increases |K||K| or decreases j, and both quantities are bounded (|K|≤|Q||K|≤|Q|, j≥0j≥ 0). Backtracking: the predecessor map pred stores, for each (K,j)(K,j), the argmax *arg\,max item; following it from (E^u,kmax)( E_u,k_ ) recovers a path realizing V(E^u,kmax)V( E_u,k_ ). Corollary 3.11 ensures all intermediate states K∪q∗K∪\q^*\ are valid. ■ Remark 5.6 (Effect of Beam Width on Complexity and Optimality). With B=∞B=∞: Texact=O(kmax⋅|reach(kmax)|⋅(n+|EH|))T_exact=O (k_ ·|K_reach(k_ )|·(n+|E_H|) ). With B<∞B<∞: Tbeam=O(kmax⋅B⋅(n+|EH|))T_beam=O (k_ · B·(n+|E_H|) ). The beam search is guaranteed optimal when the optimal first step is among the top-B fringe items by interest score, which is empirically robust when wδ>0w_δ>0. Proposition 5.4 continues to hold under exact search; under beam search, sub-path optimality holds conditionally on the beam containing the optimal intermediate states. Remark 5.7 (TTDP Integration via Augmented State Space). As noted in Section 2.3, TTDP-style temporal constraints (time budget TmaxT_ , time windows [oi,ci][o_i,c_i]) can be incorporated by augmenting the DP state from K to (K,telapsed)(K,t_elapsed): V(K,t,j)=maxq∈Fringe(K)t+dur(q)+travel(K,q)≤Tmax[ℐ(u,q,K)+V(K∪q,t+dur(q)+travel(K,q),j−1)].V(K,t,j)= _ subarraycq (K)\\ t+dur(q)+travel(K,q)≤ T_ subarray\!\!\! [I(u,q,K)+V(K∪\q\,\,t+dur(q)+travel(K,q),\,j-1) ]. The structural guarantees of Lemma 3.9 and Corollary 3.11 are unaffected; the temporal constraint simply reduces the feasible fringe at each step. Diversified Top-k Ranking Definition 5.8 (Intra-list Diversity). For ℛ⊆FR F already selected and Li∈F∖ℛL_i∈ F : D(Li,ℛ)=1−1|ℛ|∑Lj∈ℛsimcat(Li,Lj)⋅exp(−λ⋅dist(Li,Lj)),D(L_i,R)=1- 1|R| _L_j sim_cat(L_i,L_j)· (-λ·dist(L_i,L_j)), where λ>0λ>0 is a scale parameter controlling the decay of geographic proximity relative to categorical similarity (larger λ penalizes geographically distant pairs more strongly; λ is set by cross-validation or domain expertise). Set D(Li,∅)=1D(L_i, )=1. simcat(Li,Lj)sim_cat(L_i,L_j) and dist(Li,Lj)dist(L_i,L_j) for Li,Lj∈FL_i,L_j∈ F are precomputed in O(|F|2)O(|F|^2) before Algorithm 4 is called, so each evaluation of D costs O(|ℛ|)O(|R|). The diversified score is: S(u,Li,E^u,ℛ)=wℐ⋅ℐ(u,Li,E^u)+wN⋅(1−Popi)+wD⋅D(Li,ℛ),wℐ+wN+wD=1.S(u,L_i, E_u,R)=w_I·I(u,L_i, E_u)+w_N·(1-Pop_i)+w_D· D(L_i,R), w_I+w_N+w_D=1. (5) Algorithm 4 Diversified Top-k Ranking (MMR-style) 1:User u; fringe F; working state E^u E_u; kmaxk_ ; weights wℐ,wN,wDw_I,w_N,w_D 2:Ranked list ℛR of size min(kmax,|F|) (k_ ,|F|) 3:ℛ←[]R←[\,]; ℱr←FF_r← F 4:while |ℛ|<kmax|R|<k_ and ℱr≠∅F_r≠ do 5: L∗←argmaxLi∈ℱrS(u,Li,E^u,ℛ)L^*← *arg\,max_L_i _rS(u,L_i, E_u,R) 6: ℛ.(L∗)R .append(L^*); ℱr←ℱr∖L∗F_r _r \L^*\ 7:end while 8:return ℛR Definition 5.9 (Structural Serendipity). Let u=Cati:Li∈E^uC_u=\Cat_i:L_i∈ E_u\. A POI Li∈Fringe(E^u)L_i ( E_u) is structurally serendipitous if Cati∉uCat_i _u and |↓Li|≥2| L_i|≥ 2. Remark 5.10 (Sufficient condition for structural serendipity). A sufficient condition for Fringe(E^u)Fringe( E_u) to contain at least one structurally serendipitous item is that there exists a covering relation Lj⋖LiL_j L_i in (Q,⪯)(Q, ) such that Catj∈uCat_j _u, Cati∉uCat_i _u, and ↓Li∖Li⊆E^u L_i \L_i\ E_u. Under these conditions, Li∈Fringe(E^u)L_i ( E_u) by Definition 3.8, |↓Li|≥2| L_i|≥ 2 (since Lj≺LiL_j L_i is a strict predecessor), and Cati∉uCat_i _u, so LiL_i is structurally serendipitous. This configuration arises naturally as E^u E_u grows: each fringe-guided transition into a new category exposes cross-category covering relations as candidates. Surmise Relation Inference Algorithm 5 Surmise Relation Inference via Sequential Pattern Mining 1:Trajectory database S=τ(1),…,τ(m)S=\τ^(1),…,τ^(m)\; minimum support σ; confidence threshold τc _c; significance level αstat _stat 2:Partial order ⪯ on Q 3:P2←(a,b):support(⟨a,b⟩,S)≥σP_2←\(a,b):support( a,b ,S)≥σ\ ⊳ Via PrefixSpan (Pei et al., 2001) 4:for all (a,b)∈P2(a,b)∈ P_2 do 5: na←|τ∈S:a∈τ|n_a←|\τ∈ S:a∈τ\| ⊳ trajectories containing a 6: nab←|τ∈S:a precedes b in τ|n_ab←|\τ∈ S:a precedes b in τ\| ⊳ trajectories containing a before b 7:end for 8:Cand←∅Cand← 9:for all (a,b)∈P2(a,b)∈ P_2 do 10: c^ab←nab/na c_ab← n_ab/n_a; pval←BinomTest(nab,na,τc)p_val← BinomTest(n_ab,n_a, _c) 11: if c^ab≥τc c_ab≥ _c and pval≤αstatp_val≤ _stat then 12: Cand←Cand∪(a,b)Cand ∪\(a,b)\ 13: end if 14:end for 15:// Cycle resolution BEFORE transitive closure 16:for all (a,b)∈Cand(a,b) with (b,a)∈Cand(b,a) do 17: if c^ab>c^ba c_ab> c_ba then 18: Remove (b,a)(b,a) from CandCand 19: else if c^ba>c^ab c_ba> c_ab then 20: Remove (a,b)(a,b) from CandCand 21: else ⊳ Exact tie: remove both to avoid arbitrary choice 22: Remove (a,b)(a,b) and (b,a)(b,a) from CandCand 23: end if 24:end for 25:SCCs←TarjanSCC(Cand)SCCs← TarjanSCC(Cand) 26:for all C∈SCCsC with |C|>1|C|>1 do 27: Retain only the highest-confidence edge within C; remove all others 28:end for⊳ CandCand is now a DAG 29:⪯←FloydWarshall(Cand) ← FloydWarshall(Cand) ⊳ O(n3)O(n^3); DAG ensures partial order 30:Flag pairs with c^ab<τchigh c_ab< _c^high for human review; remove unvalidated pairs 31:return ⪯ The one-sided binomial test in Step 2 guards against spurious high-confidence estimates from rare items: it tests whether nabn_ab is significantly above cab=τc_ab= _c, combining an empirical threshold with a statistical significance requirement to avoid false positives from POI pairs with few co-occurrences. 5.5.1 Incremental Surmise Update Algorithm 6 Incremental Surmise Relation Update 1:Current ⪯ ; Hasse diagram H; new trajectories ΔS S; thresholds; fringe counter array cnt 2:Updated ⪯′ , H′H , ′ cnt 3:ΔP2← P_2← new high-confidence pairs from ΔS S (Algorithm 5, Steps 1–5) 4:for all (a,b)∈ΔP2(a,b)∈ P_2 not yet in ⪯ do 5: if (b,a)∈⪯(b,a)∈ then Resolve conflict; skip if a≺ba b via transitivity 6: else 7: Add covering edge (a⋖b)(a b) to EHE_H if appropriate; update ⪯ transitively (O(n2)O(n^2) worst case: all predecessors of a must be related to all successors of b in the updated closure) 8: Update fringe counters via Proposition 3.10 incremental procedure (O(deg+(b))O(deg^+(b)) per active user) 9: end if 10:end for 11:Validate acyclicity; return ⪯′ , H′H , ′ cnt Online Feedback Processing and State Update Algorithm 7 Online Feedback Processing and User Model Update 1:Confirmed state Eu(t)E_u(t); distribution PuP_u; preference u(t)p_u(t); event (Li,ri,i)(L_i,r_i, hc_i); BLIM parameters; ℓr _r; H; cnt 2:Updated Eu(t′)E_u(t ), Pu′P_u , u(t′)p_u(t ) 3:Iobs←riI_obs← r_i ⊳ Or normalized dwell/rating if available 4:pu,i(t′)←pu,i(t)+ℓr⋅(Iobs−pu,i(t))p_u,i(t )← p_u,i(t)+ _r·(I_obs-p_u,i(t)) ⊳ Step 1: update preference 5:(Pu′,E^u)←BLIMAssess(Pu,(ri)Li,B)(P_u , E_u)← BLIMAssess(P_u,(r_i)_L_i,B) ⊳ Step 2: update distribution 6:if ri=1r_i=1 and i= hc_i= true then 7: if Li∈Fringe(Eu(t))L_i (E_u(t)) or Li∈Eu(t)L_i∈ E_u(t) then 8: Eu(t′)←Eu(t)∪LiE_u(t )← E_u(t)∪\L_i\ ⊳ Valid by Lemma 3.9 9: for all s: Li⋖sL_i s in H do [s]←[s]−1 cnt[s]← cnt[s]-1 10: end for 11: else 12: log warning; Eu(t′)←Eu(t)E_u(t )← E_u(t) ⊳ Structural invariant preserved 13: end if 14:else Eu(t′)←Eu(t)E_u(t )← E_u(t) 15:end if 16:return Eu(t′)E_u(t ), Pu′P_u , u(t′)p_u(t ) The guard at Step 3 is the operational enforcement of the downward-closure invariant. When a user engages with a non-fringe POI independently of the system, admitting it to the confirmed state could violate downward closure if prerequisites are absent. The guard rejects the update to Eu(t)E_u(t); the distribution PuP_u is still updated, which may surface missing prerequisites as candidates in the next cycle. The incremental fringe update costs O(degH+(Li))O(deg_H^+(L_i)). Consolidated Complexity Analysis Table 2: Time complexity of ESRS algorithmic components. n=|Q|n=|Q|; |EH||E_H| = edges in Hasse diagram; |reach||K_reach| = states reachable within kmaxk_ steps; B = beam width; |A||A| = assessed items; m = training trajectories; d¯ d = average trajectory length. Component Algorithm Time complexity Notes Batch fringe Prop. 3.10 O(n+|EH|)O(n+|E_H|) Per state Incremental fringe Prop. 3.10 O(degH+(q∗))O(deg_H^+(q^*)) Per transition BLIM exact Alg. 2 (B=||B=|K|) O(||⋅|A|)O(|K|·|A|) Exponential worst case BLIM beam Alg. 2 (B<||B<|K|) O(B⋅|A|)O(B·|A|) Approximate MAP DP exact Alg. 3 (B=∞B=∞) O(kmax⋅|reach|⋅(n+|EH|))O(k_ ·|K_reach|·(n+|E_H|)) Optimal path DP beam Alg. 3 (B<∞B<∞) O(kmax⋅B⋅(n+|EH|))O(k_ · B·(n+|E_H|)) Approx. optimal MMR ranking Alg. 4 O(kmax2⋅|F|)O(k_ ^2·|F|) |F|=|Fringe(E^u)||F|=|Fringe( E_u)|; pairwise simcatsim_cat and distdist precomputed in O(|F|2)O(|F|^2) Surmise (batch) Alg. 5 O(md¯+n3)O(m d+n^3) PrefixSpan + Floyd-Warshall Surmise (incr.) Alg. 6 O(n2)O(n^2) Per new pair (transitive closure update) Feedback Alg. 7 O(B⋅|A|+degH+(Li))O(B·|A|+deg_H^+(L_i)) Per event Matrix factorization §4.2 O(|obs|⋅k)O(|D_obs|· k) per epoch Offline init. Remark 5.11 (Decomposability of |||K|). If (Q,⪯)(Q, ) decomposes into c connected components (Q1,⪯1),…,(Qc,⪯c)(Q_1, _1),…,(Q_c, _c) (all elements of distinct components being incomparable under ⪯ ), then |(Q,⪯)|=∏i=1c|(Qi,⪯i)||K(Q, )|= _i=1^c|K(Q_i, _i)|. Proof: any order ideal I of the disjoint union decomposes uniquely as (I∩Q1,…,I∩Qc)(I∩ Q_1,…,I∩ Q_c), each I∩QkI∩ Q_k being an order ideal of (Qk,⪯k)(Q_k, _k); the correspondence is a bijection, giving the product formula. For a chain of height hih_i (hi+1h_i+1 elements), |(Qi)|=hi+1|K(Q_i)|=h_i+1, so for c independent chains of heights h1,…,hch_1,…,h_c: |(Q,⪯)|=∏i=1c(hi+1)|K(Q, )|= _i=1^c(h_i+1). The scalability bottleneck is the exponential dependence of exact BLIM inference and exact DP on |||K| and |reach||K_reach|. For c independent components with chain heights h1,…,hch_1,…,h_c: ||=∏i=1c(hi+1)|K|= _i=1^c(h_i+1). For c=5c=5, hi=3h_i=3: ||≤45=1024|K|≤ 4^5=1024 (fully tractable); for c=15c=15, hi=4h_i=4: ||≤515≈3×1010|K|≤ 5^15≈ 3× 10^10 (requiring beam approximation). The incremental update procedures operate in near-linear time per event, ensuring responsiveness at interaction frequency regardless of exploration space size. Worked Example This section traces user u through a complete execution of the ESRS pipeline on the five-POI instance of Figure 1. The objectives are: (1) verify that interest score computations are well-defined; (2) confirm that each intermediate exploration state is a valid order ideal, verifying Corollary 3.11; (3) trace the memoization mechanism of Algorithm 3; (4) verify the sub-path optimality of Proposition 5.4; and (5) illustrate the feedback loop of Algorithm 7. Instance Setup Q=q1,…,q5Q=\q_1,…,q_5\: q1q_1 = City Museum, q2q_2 = Latin Quarter, q3q_3 = Medieval Library, q4q_4 = Art Gallery, q5q_5 = Rooftop Bar. Surmise relation: q1≺q4≺q5q_1 q_4 q_5 and q2≺q3q_2 q_3, all other pairs incomparable. ||=4×3=12|K|=4× 3=12. Principal ideals: ↓q1=q1 q_1=\q_1\, ↓q2=q2 q_2=\q_2\, ↓q3=q2,q3 q_3=\q_2,q_3\, ↓q4=q1,q4 q_4=\q_1,q_4\, ↓q5=q1,q4,q5 q_5=\q_1,q_4,q_5\. Sizes: |↓q1|=|↓q2|=1| q_1|=| q_2|=1, |↓q3|=|↓q4|=2| q_3|=| q_4|=2, |↓q5|=3| q_5|=3. Synthetic scores are calibrated to reflect plausible relative rankings: user u has an architectural history interest (high PrefPref for q1q_1, q4q_4, q5q_5) and moderate literary heritage interest (q2q_2, q3q_3). Phase 1: State Assessment Confirmed state Eu(t)=q1E_u(t)=\q_1\. No additional engagement signals, so BLIM leaves PuP_u unchanged and E^u=q1 E_u=\q_1\. RelRel values w.r.t. E^u=q1 E_u=\q_1\: Rel(q2,q1)=0,Rel(q3,q1)=0,Rel(q4,q1)=12,Rel(q5,q1)=13.Rel(q_2,\q_1\)=0, (q_3,\q_1\)=0, (q_4,\q_1\)= 12, (q_5,\q_1\)= 13. Remark 6.1 (Rel=0Rel=0 for prerequisite-free fringe items). When ↓Li=Li L_i=\L_i\, Rel(Li,E^u)=0Rel(L_i, E_u)=0 if Li∉E^uL_i∉ E_u. For q2q_2: Rel(q2,q1)=0Rel(q_2,\q_1\)=0 yet q2∈Fringe(q1)q_2 (\q_1\), since the fringe condition ↓q2∖q2=∅⊆q1 q_2 \q_2\= \q_1\ holds trivially. These two facts coexist without contradiction. The wδ⋅Relw_δ·Rel term is 0 for such items regardless of wδw_δ; structural differentiation within the fringe for prerequisite-free items can be provided by the depth-normalized score Depth(Li)=|↓Li|/nDepth(L_i)=| L_i|/n, which is state-independent and complements RelRel. With equal weights wα=wβ=wγ=wδ=0.25w_α=w_β=w_γ=w_δ=0.25: Table 3: Interest score components given E^u=q1 E_u=\q_1\. “excl.” denotes that q1∈E^uq_1∈ E_u and is excluded from recommendation scoring. q3q_3 and q5q_5 are labelled “blocked” because they are not in Fringe(E^u)Fringe( E_u) (Phase 2 fringe gate); q2q_2 is fringe-accessible despite Rel=0Rel=0 (Remark 6.1). q1q_1 q2q_2 q3q_3 q4q_4 q5q_5 Prefu,iPref_u,i 0.90 0.60 0.50 0.80 0.85 PropiProp_i 0.85 0.70 0.65 0.75 0.80 Collabu,iCollab_u,i 0.80 0.65 0.55 0.70 0.80 Rel(Li,E^u)Rel(L_i, E_u) 11 (visited) 0 0 12 12 13 13 ℐ(u,Li,E^u)I(u,L_i, E_u) excl. 0.48750.4875 blocked 0.68750.6875 blocked ℐ(u,q2,q1)=0.25×(0.60+0.70+0.65+0)=0.4875,ℐ(u,q4,q1)=0.25×(0.80+0.75+0.70+0.5)=0.6875.I(u,q_2,\q_1\)=0.25×(0.60+0.70+0.65+0)=0.4875, (u,q_4,\q_1\)=0.25×(0.80+0.75+0.70+0.5)=0.6875. Phase 2: Fringe Construction Applying Definition 3.8 to K=q1K=\q_1\: • q2q_2: ↓q2∖q2=∅⊆q1 q_2 \q_2\= \q_1\ ✓ • q3q_3: ↓q3∖q3=q2⊈q1 q_3 \q_3\=\q_2\ \q_1\ × • q4q_4: ↓q4∖q4=q1⊆q1 q_4 \q_4\=\q_1\ \q_1\ ✓ • q5q_5: ↓q5∖q5=q1,q4⊈q1 q_5 \q_5\=\q_1,q_4\ \q_1\ × Hence F=q2,q4F=\q_2,q_4\. Augmented states q1,q2\q_1,q_2\ and q1,q4\q_1,q_4\ are both valid order ideals (verified by checking downward closure), confirming Lemma 3.9. Phase 3: Path Recommendation via Memoized DP (kmax=2k_ =2) The memoized recursion starts with DPVal(q1,2)(\q_1\,2). This triggers two recursive calls, DPVal(q1,q2,1)(\q_1,q_2\,1) and DPVal(q1,q4,1)(\q_1,q_4\,1), before resolving the root. At horizon k=1k=1: • Fringe(q1,q2)=q3,q4Fringe(\q_1,q_2\)=\q_3,q_4\ (verified: ↓q3∖q3=q2⊆q1,q2 q_3 \q_3\=\q_2\ \q_1,q_2\ ✓; ↓q4∖q4=q1⊆q1,q2 q_4 \q_4\=\q_1\ \q_1,q_2\ ✓; ↓q5∖q5=q1,q4⊈q1,q2 q_5 \q_5\=\q_1,q_4\ \q_1,q_2\ ×) • Fringe(q1,q4)=q2,q5Fringe(\q_1,q_4\)=\q_2,q_5\ (verified similarly) Interest scores at intermediate states, computed via Eq. (2) (fringe items satisfy Rel=(|↓Li|−1)/|↓Li|Rel=(| L_i|-1)/| L_i|, not 1): Rel(q5,q1,q4) (q_5,\q_1,q_4\) =|q1,q4,q5|−1|q1,q4,q5|=23, = |\q_1,q_4,q_5\|-1|\q_1,q_4,q_5\|= 23, Rel(q2,q1,q4) (q_2,\q_1,q_4\) =|q2|−1|q2|=0, = |\q_2\|-1|\q_2\|=0, Rel(q4,q1,q2) (q_4,\q_1,q_2\) =|q1,q4|−1|q1,q4|=12, = |\q_1,q_4\|-1|\q_1,q_4\|= 12, Rel(q3,q1,q2) (q_3,\q_1,q_2\) =|q2,q3|−1|q2,q3|=12. = |\q_2,q_3\|-1|\q_2,q_3\|= 12. ℐ(u,q5,q1,q4) (u,q_5,\q_1,q_4\) =0.25×(0.85+0.80+0.80+23)≈0.7792, =0.25×(0.85+0.80+0.80+ 23)≈ 0.7792, ℐ(u,q2,q1,q4) (u,q_2,\q_1,q_4\) =0.25×(0.60+0.70+0.65+0)=0.4875, =0.25×(0.60+0.70+0.65+0)=0.4875, ℐ(u,q4,q1,q2) (u,q_4,\q_1,q_2\) =0.25×(0.80+0.75+0.70+12)=0.6875, =0.25×(0.80+0.75+0.70+ 12)=0.6875, ℐ(u,q3,q1,q2) (u,q_3,\q_1,q_2\) =0.25×(0.50+0.65+0.55+12)=0.5500. =0.25×(0.50+0.65+0.55+ 12)=0.5500. Memo table (base cases zero; memoization avoids recomputing q1,q2,q4\q_1,q_2,q_4\, reached by two distinct length-2 paths): State j memo q1,q2,q3\q_1,q_2,q_3\ 0 0 q1,q2,q4\q_1,q_2,q_4\ 0 0 q1,q4,q5\q_1,q_4,q_5\ 0 0 q1,q2\q_1,q_2\ 1 max(0.6875, 0.5500)=0.6875 (0.6875,\,0.5500)=0.6875 [=q4 pred=q_4] q1,q4\q_1,q_4\ 1 max(0.7792, 0.4875)≈0.7792 (0.7792,\,0.4875)≈ 0.7792 [=q5 pred=q_5] q1\q_1\ 2 max(0.4875+0.6875, 0.6875+0.7792)=max(1.1750, 1.4667)≈1.4667 (0.4875+0.6875,\;0.6875+0.7792)= (1.1750,\,1.4667) 1.4667 Backtracking: [(q1,2)]=q4 pred[(\q_1\,2)]=q_4, then [(q1,q4,1)]=q5 pred[(\q_1,q_4\,1)]=q_5. Optimal path: π∗=(q4,q5)π^*=(q_4,q_5), V∗=1116+187240=352240=2215≈1.4667V^*= 1116+ 187240= 352240= 2215≈ 1.4667. Table 4: Complete DP path evaluation from E^u=q1 E_u=\q_1\, kmax=2k_ =2. ℐ2I_2 values use exact Rel scores per Eq. (2); ℐ(q5,⋅)I(q_5,·) involves Rel=2/3Rel=2/3, giving the exact fraction 187/240=0.77916¯187/240=0.7791 6 (a non-terminating repeating decimal), approximated to 4 d.p. The state q1,q2,q4\q_1,q_2,q_4\ is reached by two paths but evaluated once (memoization). “State valid?” confirms Corollary 3.11. Step 1 State Step 2 ℐ1I_1 ℐ2I_2 V Valid? q4q_4 q1,q4\q_1,q_4\, Fringe=q2,q5Fringe=\q_2,q_5\ q5q_5 0.6875 ≈ 0.7792 ≈1.4667 1.4667 ✓ q2q_2 0.6875 0.4875 1.1750 ✓ q2q_2 q1,q2\q_1,q_2\, Fringe=q3,q4Fringe=\q_3,q_4\ q4q_4 0.4875 0.6875 1.1750 ✓ q3q_3 0.4875 0.5500 1.0375 ✓ Structural verification. Path π∗=(q4,q5)π^*=(q_4,q_5) traverses: q1→+q4q1,q4→+q5q1,q4,q5\q_1\ +q_4\q_1,q_4\ +q_5\q_1,q_4,q_5\, each an upward edge in the Hasse diagram of (,⊆)(K, ), ascending two levels. This demonstrates the well-graded property (Proposition 3.4(iv)). Sub-path optimality: ℐ(u,q5,q1,q4)≈0.7792>0.4875=ℐ(u,q2,q1,q4)I(u,q_5,\q_1,q_4\)≈ 0.7792>0.4875=I(u,q_2,\q_1,q_4\) confirms q5q_5 is uniquely optimal from K1K_1, verifying Proposition 5.4. Memoization saving: at scale (20 POIs, kmax=5k_ =5), there are at most (205)=15,504 205=15,504 distinct size-5 state sets, each reached by up to 5!=1205!=120 orderings of the same items. Memoization collapses all orderings reaching the same state into a single computation, giving a factor-of-120120 reduction in evaluations before any structural pruning from ⪯ . Feedback Processing User u visits q4q_4 with high-confidence signal (Iobs=0.9I_obs=0.9). Algorithm 7 executes: Step 1 (preference): pu,4(t′)=0.80+0.1×(0.9−0.80)=0.81p_u,4(t )=0.80+0.1×(0.9-0.80)=0.81. Step 2 (BLIM): With β4=0.05 _4=0.05, η4=0.10 _4=0.10, states containing q4q_4 receive prior ×0.95× 0.95; others receive prior ×0.05× 0.05. After normalization, Pu′P_u concentrates on states containing q4q_4, with MAP E^u′=q1,q4 E_u =\q_1,q_4\. Step 3 (confirmed state): q4∈Fringe(q1)=q2,q4q_4 (\q_1\)=\q_2,q_4\ ✓. Eu(t′)=q1∪q4=q1,q4∈E_u(t )=\q_1\∪\q_4\=\q_1,q_4\ ✓. Incremental fringe update: The sole direct successor of q4q_4 is q5q_5: [q5]←0 cnt[q_5]← 0, so q5q_5 enters the fringe. New fringe: Fringe(q1,q4)=q2,q5Fringe(\q_1,q_4\)=\q_2,q_5\, computed in O(degH+(q4))=O(1)O(deg_H^+(q_4))=O(1). The visit to q4q_4 is a structural event: the confirmed state advanced one level in the lattice, unlocking q5q_5 and raising Rel(q5,E^u)Rel(q_5, E_u) from 13 13 to 23 23 (fringe item of depth 3, per Eq. (2)). The next pipeline cycle produces a substantively different recommendation set from any preference-based system lacking the structural layer. Summary of Verified Properties Table 5: Formal properties verified in the worked example. Property Result Instance check Outcome States q1,q1,q4,q1,q4,q5∈\q_1\,\q_1,q_4\,\q_1,q_4,q_5\ Lemma 3.9 ↓qi⊆Kj q_i K_j verified ✓ π∗=(q4,q5)π^*=(q_4,q_5) items distinct Corollary 3.11(i) q4≠q5q_4≠ q_5; each added before next step ✓ Sub-path (q5)(q_5) optimal from q1,q4\q_1,q_4\ Proposition 5.4 ≈0.7792>0.4875≈0.7792>0.4875 ✓ Fringe(q1)=q2,q4Fringe(\q_1\)=\q_2,q_4\ Definition 3.8 Verified by ideal check ✓ Lattice path ascends via fringe Prop. 3.4(iv) q1→q1,q4→q1,q4,q5\q_1\→\q_1,q_4\→\q_1,q_4,q_5\ ✓ Fringe update after q4q_4 confirmed Prop. 3.10 [q5] cnt[q_5] decremented; q5q_5 enters fringe ✓ Eu(t)E_u(t) not modified in Phase 1–3 Remark 5.1 Only Alg. 7 modifies Eu(t)E_u(t) ✓ Conceptual Analysis Representational Capacity Definition 7.1 (User Model, Item Model, Recommendation Model). A recommender system is characterized by three representational choices. The user model U specifies the formal object representing a user. The item model ℒL specifies the formal object representing a location. The recommendation model ℳℛM_R specifies the formal function mapping (,ℒ)(U,L) to a recommendation. Table 6 characterizes each paradigm across these dimensions, with two additional columns: state completeness (whether the user model can represent a user’s structural position in a formally defined space) and recommendation validity certificate (whether the system can prove, not merely estimate, that a recommendation is valid for the current state). Table 6: Representational capacity analysis. ✓ = supported; ∘ = partially or under restrictions; × = not representable. “Ordered item structure” means the item model encodes a partial order, not merely pairwise similarity. “Validity certificate” means the system can prove a recommendation is structurally valid. Dimension CF/ Content Seq. (MK/RNN) Seq. (Transf.) TTDP CBRS ESRS (ours) User: preference vector ✓ ∘ ✓ × ∘ ✓ User: interaction history ∘ ✓ ✓ × × ∘ User: cumulative exploration state × × × × × ✓ User: state completeness × × × × × ✓ Item: attribute vector ✓ ∘ ✓ ✓ ✓ ∘ Item: ordered structure × × × × ∘ ✓ Rec.: relevance estimation ✓ ✓ ✓ ∘ ✓ ✓ Rec.: formal path optimization × × × ✓ × ✓ Rec.: validity certificate × × × × ∘ ✓ Rec.: state-dependent scoring × × × × × ✓ The gap from CF/sequential models to EST (no cumulative state representation) is not resolvable by additional data or model capacity: no amount of training data teaches a CF or Transformer model to represent the downward-closure property of exploration states. The converse gap (EST’s collaborative signal is coarser than a full latent factor model) is resolvable by integration: EST can adopt any CF-derived preference estimate as Prefu,iPref_u,i without modifying other components. Paradigm-by-Paradigm Structural Analysis Collaborative Filtering and Content-Based. CF’s user model is a preference vector encoding preference intensity and similarity, but no relational structure over items. The question “is the user ready for this POI?” is not representable. CF’s latent factor model captures the collaborative signal with far greater precision than EST’s Jaccard-based approximation—but this gap is resolvable by integration, while the representational gap is not. Sequential and Session-Based Recommendation. Sequential models learn f:ℋ→Δ(Q)f:H→ (Q) from observed transitions. Even with infinite training data and perfect capacity, these models cannot reliably recover a ground-truth surmise order ⪯ because: (i) prerequisite transitivity may not manifest as pairwise co-occurrence if users always visit intermediate items; (i) universal prerequisites show no variance in the training data; (i) geographic and temporal co-occurrence confounds genuine prerequisites. EST does not compete with sequential models on next-POI accuracy under standard conditions; it introduces an orthogonal modeling dimension that sequential models cannot represent by design. Sequential models excel at capturing contextual transition patterns—session dynamics, physical position, time of day, fatigue—that the cumulative exploration state Eu(t)E_u(t) does not encode. This is a genuine strength of sequential approaches that EST does not replicate. The Tourist Trip Design Problem. TTDP optimizes ∑Li∈πsi _L_i∈πs_i with fixed scores; ESRS optimizes ∑j=1kℐ(u,qj,Kj−1) _j=1^kI(u,q_j,K_j-1) where the value of visiting LiL_i depends on the state Kj−1K_j-1. This state-dependence makes the ESRS problem a sequential decision problem over a state space rather than an orienteering instance, requiring the Bellman principle (Proposition 5.4) for tractability. Formally: TTDP’s path optimization objective is a special case of the ESRS DP component (Eq. (4)) when ℐI is constant in K and ⪯ contains only reflexive pairs (i.e., (Q,⪯)=2QK(Q, )=2^Q); this equivalence applies to the optimization structure only and does not extend to the BLIM state estimator, feedback loop, or cold-start components. ESRS augmented with time constraints (Remark 5.7) is a strictly richer model than TTDP. Constraint-Based Recommender Systems. CBRS models a static requirement profile; EST models a dynamic lattice state. CBRS is a one-shot filtering paradigm; EST is a multi-step state-transition paradigm. Two users with identical current interest profiles but different visit histories receive structurally different recommendation sets in EST but identical ones in CBRS. CBRS can in principle encode an ordering constraint as a logical rule, but the resulting system lacks the lattice-theoretic structure enabling EST’s algorithmic guarantees (CBRS earns ∘ in Table 1). A Formal Theory of EST Explanations Definition 7.2 (Structural Explanation). A structural explanation for the recommendation of POI LiL_i to user u in state E^u E_u is a pair (πpre,σ)( _pre,σ) where: πpre _pre is a path in H through ↓Li∖Li L_i \L_i\ passing only through items in E^u E_u; and σ maps each covering relation in πpre _pre to a natural-language justification stored in the Location Database. Proposition 7.3 (Every ESRS Recommendation Admits a Structural Explanation). For any E^u∈ E_u and Li∈Fringe(E^u)L_i ( E_u), there exists a structural explanation (πpre,σ)( _pre,σ) for the recommendation of LiL_i. Proof. Since Li∈Fringe(E^u)L_i ( E_u), we have ↓Li∖Li⊆E^u L_i \L_i\ E_u. Two cases arise. Case 1 (↓Li∖Li=∅ L_i \L_i\= , no prerequisites): set πpre=() _pre=() (the empty chain) and let σ map the empty set of covering relations to the natural-language justification “LiL_i is accessible to any user without prior visits.” The pair ((),σ)((),σ) is a valid structural explanation. Case 2 (↓Li∖Li≠∅ L_i \L_i\≠ ): any maximal chain in the finite partial order (↓Li∖Li,⪯)( L_i \L_i\, ) constitutes πpre _pre (non-empty by hypothesis), and its covering relations can be annotated with semantic justifications from the Location Database. In both cases the pair (πpre,σ)( _pre,σ) exists. ■ Example 7.4 (Five-POI Instance). When ESRS recommends q4q_4 to a user in state q1\q_1\: πpre=(q1) _pre=(q_1); σ(q1⋖q4)σ(q_1 q_4): “The Art Gallery’s collection is curated around artefacts whose historical provenance was established in the medieval period documented in the City Museum. Prior engagement with the City Museum provides the contextual grounding to understand the Gallery’s curatorial logic.” For subsequently recommending q5q_5 from q1,q4\q_1,q_4\: πpre=(q1,q4) _pre=(q_1,q_4); σ(q4⋖q5)σ(q_4 q_5): “The Rooftop Bar’s panoramic view synthesizes urban perspectives from the preceding cultural visits.” Remark 7.5 (Distinction from Post-Hoc Explainability). EST’s structural explanations differ from post-hoc methods (LIME (Ribeiro et al., 2016), SHAP (Lundberg and Lee, 2017)) in two fundamental ways. First, Proposition 7.3 proves existence unconditionally; post-hoc methods compute approximations with no existence guarantee. Second, the structural explanation is the recommendation process—the chain πpre _pre is the actual sequence of prerequisite constraints determining fringe membership. No gap exists between explanation and model (Rudin, 2019). A Taxonomy of EST’s Properties 7.4.1 Class I: Structural Guarantees Unconditional consequences of the mathematical results in Section 3, holding for any surmise relation on any finite POI set: (SG1) Lattice structure (Propositions 3.4, 3.6) (SG2) Fringe validity (Lemma 3.9) (SG3) Path validity (Corollary 3.11) (SG4) Cold-start entry points (Proposition 4.2) (SG5) Fringe efficiency (Proposition 3.10) (SG6) DP sub-path optimality (Proposition 5.4) (SG7) Explanation existence (Proposition 7.3) 7.4.2 Class I: Design Properties Hold when architectural choices are correctly implemented and preconditions satisfied: (DP1) Confirmed state integrity: Eu(t)E_u(t) always satisfies downward closure iff Algorithm 7 is the sole modifier and the fringe guard is correctly enforced. (DP2) Cold-start robustness (Proposition 4.1): Collabu,iCollab_u,i is well-defined iff u(t0)≠p_u(t_0) 0. (DP3) Beam MAP faithfulness (Remark 5.3): exact iff the true MAP state is in the beam. (DP4) Surmise acyclicity: ⪯ is a valid partial order iff Algorithm 5 correctly resolves all cycles. (DP5) Interest score normalization: ℐ∈[0,1]I∈[0,1] iff all components are normalized and weights sum to 1. 7.4.3 Class I: Empirical Hypotheses Require empirical validation on real data: (EH1) Perceived coherence: ESRS users report higher journey coherence than CF/sequential baselines (controlled user study). (EH2) Exploration depth: ESRS users achieve higher coverage |Eu(t)|/|Q||E_u(t)|/|Q| over sessions (longitudinal study). (EH3) Next-POI accuracy: ESRS achieves competitive Recall@K and NDCG@K relative to SASRec, GETNext, BERT4Rec (offline benchmark evaluation, explicitly deferred). (EH4) Cold-start quality: structural cold-start outperforms popularity-based and demographic filtering on first-session quality (A/B test). (EH5) Surmise validity: Algorithm 5 with expert validation produces relations judged correct by domain experts for ≥80%≥ 80\% of pairs (annotation study). Note on EH3: ESRS is not designed to maximize next-POI accuracy on standard benchmarks but to maximize semantic coherence. Lower Recall@K than GETNext with higher exploration coherence would be scientifically significant rather than damaging—confirming that EST and sequential models optimize different objectives. Conditions for EST Advantage and Limitation Conditions favoring EST. (1) Semantically rich domain: the city contains genuine prerequisite structure. (2) Users in unfamiliar environments: users who cannot self-select appropriate entry points based on existing familiarity benefit most from the fringe structure. (3) Multi-session exploration: the cumulative state compounds value across visits. (4) Sparse interaction data: structural cold-start requires no historical data. Conditions limiting EST. (1) Invalid surmise relation: the quality floor is set by the quality of ⪯ . (2) Shallow states: near-empty states make the fringe nearly the full prerequisite-free item set, providing little guidance. (3) High-density mobility: rapid accumulation may make the fringe non-binding. (4) Order-independent domains: an empty surmise relation reduces EST to an unconstrained recommender. Complementarity and Integration Opportunities EST and existing paradigms are more complementary than competitive. Four integration architectures exploit this: EST + Transformer. Apply a fringe mask to the Transformer output: aij′=aij⋅[Li∈Fringe(Eu(t))]a_ij =a_ij·1[L_i (E_u(t))]. This preserves the Transformer’s contextual transition patterns while guaranteeing prerequisite validity (SG2, SG3). EST + GNN. A GNN trained on the POI attribute graph (category hierarchy, geographic proximity, semantic embeddings) can predict surmise edges, addressing the trajectory-data dependence of Algorithm 5 and enabling zero-shot surmise relation initialization for new cities. EST + CF. Replace the Jaccard-based collaborative signal with a CF model trained on (u,i,Eu(t))(u,i,E_u(t)) triples, learning that affinity for LiL_i changes as the exploration state evolves. EST + TTDP. The augmented DP state (K,telapsed)(K,t_elapsed) of Remark 5.7 combines structural prerequisite validity with TTDP time-feasibility, producing itineraries with both guarantees simultaneously. Theoretical Properties: A Synthesizing View EST’s mathematical structure forms a three-level hierarchy: Level 1: Surmise relation (Q,⪯)(Q, ) Fringe extraction, O(n+|EH|)O(n+|E_H|) computation Level 2: Knowledge / Learning Space Well-graded property, path validity via ∪ and ∩ Level 3: Distributive Lattice (,⊆)(K, ) Birkhoff representation, FCA-based visualization +closure under union+distributivity (Birkhoff) Level 1 delivers efficient fringe computation. Level 2 delivers path validity and the well-graded property. Level 3 delivers the compact canonical representation connecting EST to FCA. The full strength of EST requires all three levels. Three open theoretical questions are the following: (i) the approximation ratio for beam DP — specifically, whether Vbeam≥(1−ε(B))⋅V∗V_beam≥(1- (B))· V^* holds and how ε(B) (B) depends on the structure of (Q,≺)(Q, ); (i) the sample complexity for surmise relation inference (PAC-learning bounds on the number of trajectories required for reliable recovery of ≺ ); (i) the sensitivity of BLIM estimation to parameter misspecification and its propagation to MAP estimate error. These questions are precisely statable within the formal framework developed here, which is itself a consequence of the explicit algebraic structure. Discussion Implications 8.1.1 For Recommender Systems Research EST’s most significant implication is not a better algorithm for an existing task but the introduction of a new evaluation dimension: structural validity. Current metrics (Recall@K, NDCG@K, MRR, Hit Rate) assess whether a system predicts the next visited item; they do not assess whether recommended sequences respect semantic ordering or guide users through coherent exploration narratives. EST provides the formal apparatus for defining and measuring these properties. Three concrete research implications follow. First, to the best of our knowledge, no existing LBRS benchmark contains surmise relation labels: creating an annotated city trajectory dataset where domain experts have labeled prerequisite relationships would enable systematic empirical evaluation and motivate new surmise inference algorithms. Second, EST provides a formal language for “coherent exploration journey”—a lattice path never violating the fringe condition—enabling the auditing of existing systems and datasets for structural validity. Third, the BLIM inference procedure adapts naturally to active assessment contexts, enabling minimal probe-question strategies for user state elicitation at session start. 8.1.2 For Urban Computing and Tourism EST provides theoretical grounding for recommendation systems that pursue both personalization and structural coherence simultaneously. In heritage tourism, the surmise relation encodes interpretive structure built into historic districts; EST ensures visitors accumulate contextual layers necessary for deep engagement. In newcomer orientation, EST can model urban literacy as a formal exploration space, guiding new residents through cultural prerequisites for integration. A critical caution applies: EST’s structural guidance is appropriate when users seek structured discovery. Users who prefer free, non-linear exploration may experience the fringe constraint as paternalistic. An implementation should expose the structural layer as an opt-in feature and allow users to override the fringe gate, logging such overrides as potential signals of surmise relation errors. 8.1.3 For Adjacent Domains EST’s mathematical foundations are domain-agnostic. Promising applications include: museum audio guides (exhibits as POIs, surmise relation from curatorial prerequisites, exploration state accumulating across the visit); professional training (skills as POIs, prerequisite graph from program requirements, DP formulation as multi-skill sequencer); academic advising (courses as POIs, institutional prerequisites as surmise relation, ESRS DP as degree-plan optimizer); digital humanities (primary sources organized by historiographic dependencies, fringe guiding researchers from foundational to specialized material). Limitations L1. Absence of empirical validation. The most significant limitation is the complete absence of empirical evaluation. No real-world deployment has been conducted; no standard benchmark has been used. All performance claims are classified as empirical hypotheses precisely to acknowledge this gap. Empirical investigation is the primary direction for future work. L2. The engagement signal operationalization problem. The distinction between meaningful and non-meaningful visits must be operationalized through observable signals (dwell time, check-in, rating), and the threshold θd _d is a modeling choice without a theoretically grounded default. A long dwell time may reflect confusion or rest rather than engaged cultural consumption. The validity of engagement signals as proxies for meaningful visits is an empirical question requiring instrumentation beyond standard check-in datasets. L3. Monotonicity of the exploration state. The confirmed state is monotonically non-decreasing; the model has no mechanism for exploration state decay, time-discounted visit relevance, or revisit semantics. A user who visited the City Museum ten years ago and returns with no contextual memory is modeled identically to one who visited yesterday. Temporal decay is a significant future research direction. L4. Validity of the downward-closure assumption. Users frequently engage meaningfully with a POI through prior education, informal exposure, or group tours—without a formal visit to prerequisites. The downward-closure invariant may systematically underestimate the structural accessibility of advanced users. Relaxing it would require replacing the learning space model with a more permissive structure, losing the lattice-theoretic algorithmic guarantees. L5. The surmise relation elicitation bottleneck. Deploying ESRS in a new city requires domain experts to validate inferred surmise links. This validation cost—in time, expert availability, and institutional access—constitutes a significant deployment barrier. Domain experts may also disagree: the surmise relation reflects a particular curatorial perspective rather than a single objective ground truth. L6. Cross-city and cross-domain transfer. The surmise relation is city-specific with no formal mechanism for transfer, even when two cities share cultural or architectural structures. A tourist with deep experience of Rome’s classical heritage visiting Athens should have a higher structural starting point than a first-time visitor, but the current framework models them identically. Cross-city structural transfer is a significant open problem. L7. Privacy of exploration states. Accumulated exploration states are detailed behavioral profiles. Knowing that a user has visited a Holocaust Memorial, an LGBTQ+ History Museum, and a specific religious institution in sequence provides sensitive identity information. EST deployments must implement differential privacy mechanisms, user-controlled state reset, and data minimization policies. L8. Computational bottleneck for large exploration spaces. The practical threshold at which beam approximation becomes necessary—and its empirical accuracy loss—has not been characterized on real exploration data. Tighter complexity bounds for practically relevant structures (sparse, decomposable, nearly-tree-structured surmise relations) are an important theoretical direction. Future Research Directions Priority 1: Empirical implementation and evaluation. Dataset construction (annotated LBRS benchmark with expert surmise relation labels); offline evaluation of Algorithm 5’s surmise recovery accuracy; recommendation quality benchmarking against SASRec, GETNext, STAN, BERT4Rec on standard and EST-specific metrics (fringe validity rate, structural coverage, explanation satisfaction); controlled user study testing EH1 and EH3. Priority 2: Theoretical gaps. 1. Approximation ratio for beam DP: establish Vbeam≥(1−ε(B))⋅V∗V_beam≥(1- (B))· V^*. 2. Sample complexity of surmise inference: PAC-learning bounds on trajectory requirements for reliable surmise recovery. 3. BLIM sensitivity: characterize propagation of parameter misspecification to MAP estimate error and recommendation quality. Priority 3: Surmise relation learning and transfer. 1. Causal inference from trajectory data to distinguish genuine prerequisites from geographic and temporal confounders. 2. Cross-city transfer via joint POI embeddings across shared cultural heritage. 3. Active surmise elicitation: minimal query strategies maximally reducing uncertainty about ⪯ . Priority 4: Temporal dynamics and privacy. 1. Time-discounted exploration states via recency-weighted membership, extending to fuzzy order ideals. 2. Privacy-preserving EST: differential privacy for state distributions, federated inference, consent-aware state management. Priority 5: Hybrid architectures. 1. Prove that the fringe-masked Transformer preserves validity guarantees SG2 and SG3 and evaluate its effect on next-POI accuracy. 2. Evaluate GNN-based surmise prediction for zero-shot city initialization. 3. Design the (u,i,Eu(t))(u,i,E_u(t)) interaction matrix, specify factorization, and evaluate exploration-state-aware CF against standard CF. Conclusion The prerequisite structure of urban experience is real, pervasive, and consequential: certain visits contextually ground others, and a recommender system blind to this structure can optimize relevance only in a degraded sense. Current location-based systems achieve considerable sophistication within this blind spot. Exploration Space Theory removes it by giving prerequisite structure a rigorous mathematical form. The framework rests on a single observation: the set of locations a user has meaningfully visited is an order ideal of a prerequisite partial order. This observation generates an entire mathematical apparatus. Order ideals form a distributive lattice; Birkhoff’s theorem canonically identifies this lattice with the ideal lattice of the surmise order; the lattice is well-graded; and every fringe-guided recommendation admits a structural explanation whose existence is provable. The architecture follows from the mathematics. The formal core consists of six proven results: (M1) (Proposition 3.4) The family of all order ideals of any surmise partial order is a well-graded learning space. (M2) (Proposition 3.6, Remark 3.7) The exploration space is a finite distributive lattice canonically isomorphic to the ideal lattice of the surmise order via Birkhoff’s theorem. (M3) (Proposition 3.10) The exploration fringe is computable in O(n+|EH|)O(n+|E_H|); incremental updates cost O(degH+(q∗))O(deg_H^+(q^*)). (M4) (Lemma 3.9, Corollary 3.11) Any fringe-guided transition produces a valid exploration state; any fringe-guided path consists of valid states and non-repeating items. (M5) (Proposition 5.4) Under additive interest gains, the DP value function satisfies Bellman’s sub-path optimality principle. (M6) (Proposition 7.3) Every ESRS recommendation admits a structural explanation faithful to the model by construction. Building on M1–M6, the paper specifies a complete system: a memoized DP exploiting state-identity to avoid exponential path enumeration; a BLIM state estimator with EM parameter learning and beam approximation; a feedback loop as the sole authorized modifier of the confirmed state; an incremental surmise inference pipeline preventing spurious relation propagation; and three cold-start strategies, of which the structural one provides a formal validity guarantee (see §4.4 and Limitation L5). EST’s limitations are documented and its empirical hypotheses are clearly distinguished from proven structural guarantees. The absence of empirical validation is the primary limitation and the primary direction for future work. The prerequisite structure of urban experience is not a statistical artifact that more data will eventually surface; it is a semantic property that must be represented explicitly. Knowledge Space Theory, developed over four decades to model exactly this kind of structured prerequisite dependency, provides the mathematical language. The translation to urban exploration introduces new definitions, new proofs, and new algorithms. The empirical question of whether these tools—deployed in a real system with a real surmise relation— produce recommendations that feel coherent and meaningful to real users remains open. It is, we believe, a question worth asking precisely. The theoretical foundations laid here make that empirical investigation possible. References G. Adomavicius and A. Tuzhilin (2005) Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering 17 (6), p. 734–749. Cited by: §1. G. Adomavicius and A. Tuzhilin (2011) Context-aware recommender systems. In Recommender Systems Handbook, F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor (Eds.), p. 217–253. Cited by: §2.1. R. E. Bellman (1957) Dynamic programming. Princeton University Press, Princeton, NJ. Cited by: §5.3.1. G. Birkhoff (1937) Rings of sets. Duke Mathematical Journal 3 (3), p. 443–454. Cited by: §2.5, Remark 3.7. R. Burke (2002) Hybrid recommender systems: survey and experiments. User Modeling and User-Adapted Interaction 12 (4), p. 331–370. Cited by: §2.1, §4.4.1. A. T. Corbett and J. R. Anderson (1994) Knowledge tracing: modeling the acquisition of procedural knowledge. User Modeling and User-Adapted Interaction 4 (4), p. 253–278. Cited by: §1. B. A. Davey and H. A. Priestley (2002) Introduction to lattices and order. 2nd edition, Cambridge University Press, Cambridge. Cited by: §2.5, Remark 3.7. M. C. Desmarais and R. S. J. d. Baker (2012) A review of recent advances in learner and skill modeling in intelligent learning environments. User Modeling and User-Adapted Interaction 22 (1–2), p. 9–38. Cited by: §1, §4.2, Remark 5.3. J. Doignon and J. Falmagne (1985) Spaces for the assessment of knowledge. International Journal of Man-Machine Studies 23 (2), p. 175–196. Cited by: §1, §2.4. J. Doignon and J. Falmagne (1999) Knowledge spaces. Springer, Berlin. Cited by: §1, §2.4. J. Falmagne and J. Doignon (1988) A class of stochastic procedures for the assessment of knowledge. The British Journal of Mathematical and Statistical Psychology 41 (1), p. 1–23. Cited by: §2.4, §4.2, §5.2.1. J. Falmagne and J. Doignon (2011) Learning spaces: interdisciplinary applied mathematics. Springer, Berlin. Cited by: §1, §2.4, §2.4, §2.4, Definition 3.1. W. Fan, Y. Ma, Q. Li, Y. He, E. Zhao, J. Tang, and D. Yin (2019) Graph neural networks for social recommendation. In Proceedings of the 28th International Conference on World Wide Web (W 2019), p. 417–426. Cited by: §2.1. A. Felfernig, R. Burke, D. Jannach, and M. Zanker (2011) Knowledge-based recommender systems. In Recommender Systems Handbook, F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor (Eds.), p. 301–346. Cited by: §2.6. A. Felfernig, G. Friedrich, D. Jannach, and M. Zanker (2006) An integrated environment for the development of knowledge-based recommender applications. International Journal of Electronic Commerce 11 (2), p. 11–34. Cited by: §2.6. J. Feng, Y. Li, C. Zhang, F. Sun, F. Meng, A. Guo, and D. Jin (2017) DeepMove: predicting human mobility with attentional recurrent networks. In Proceedings of the 26th International Conference on World Wide Web (W 2017), p. 1459–1468. Cited by: §2.2. B. Ganter and R. Wille (1999) Formal concept analysis: mathematical foundations. Springer, Berlin. Cited by: §2.5. D. Gavalas, C. Konstantopoulos, K. Mastakas, and G. Pantziou (2014) A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics 20 (3), p. 291–328. Cited by: §1, §2.3. X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T. Chua (2017) Neural collaborative filtering. In Proceedings of the 26th International Conference on World Wide Web (W 2017), p. 173–182. Cited by: §2.1. B. Hidasi, A. Karatzoglou, L. Baltrunas, and D. Tikk (2016) Session-based recommendations with recurrent neural networks. In 4th International Conference on Learning Representations (ICLR 2016), Cited by: §1, §2.2. W. Kang and J. McAuley (2018) Self-attentive sequential recommendation. In Proceedings of the IEEE International Conference on Data Mining (ICDM 2018), p. 197–206. Cited by: §1, §2.2. K. H. Lim, J. Chan, C. Leckie, and S. Karunasekera (2018) Personalized trip recommendation for tourists based on user interests, points of interest visit durations and visit recency. Knowledge and Information Systems 54 (2), p. 375–406. Cited by: §2.3. P. Lops, M. de Gemmis, and G. Semeraro (2011) Content-based recommender systems: state of the art and trends. In Recommender Systems Handbook, F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor (Eds.), p. 73–105. Cited by: §2.1. S. M. Lundberg and S. Lee (2017) A unified approach to interpreting model predictions. Advances in Neural Information Processing Systems 30, p. 4768–4777. Cited by: Remark 7.5. Y. Luo, Q. Liu, and Z. Liu (2021) STAN: spatio-temporal attention network for next location recommendation. In Proceedings of the Web Conference 2021 (W 2021), p. 2177–2185. Cited by: §2.2. M. J. Pazzani and D. Billsus (2007) Content-based recommendation systems. In The Adaptive Web, p. 325–341. Cited by: §2.1. J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. Hsu (2001) PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth. In Proceedings of the 17th International Conference on Data Engineering (ICDE 2001), p. 215–224. Cited by: 3. S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme (2010) Factorizing personalized Markov chains for next-basket recommendation. In Proceedings of the 19th International Conference on World Wide Web (W 2010), p. 811–820. Cited by: §1, §2.2. M. T. Ribeiro, S. Singh, and C. Guestrin (2016) "Why should I trust you?": explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, p. 1135–1144. Cited by: Remark 7.5. F. Ricci, L. Rokach, and B. Shapira (2011) Introduction to recommender systems handbook. In Recommender Systems Handbook, p. 1–35. Cited by: §1. C. Rudin (2019) Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence 1 (5), p. 206–215. Cited by: Remark 7.5. M. Sadallah and G. Smits (2023) Learning path recommendation from an inferred learning space. In Responsive and Sustainable Educational Futures: 18th European Conference on Technology Enhanced Learning (EC-TEL 2023), Aveiro, Portugal, September 4–8, 2023, Proceedings, O. Viberg, I. Jivet, P. J. Muñoz-Merino, M. Perifanou, and T. Papathoma (Eds.), Lecture Notes in Computer Science, Vol. 14200, Cham, p. 630–635. External Links: Document Cited by: §2.4. J. B. Schafer, D. Frankowski, J. Herlocker, and S. Sen (2007) Collaborative filtering recommender systems. In The Adaptive Web: Methods and Strategies of Web Personalization, p. 291–324. Cited by: §2.1. A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock (2002) Methods and metrics for cold-start recommendations. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 253–260. Cited by: §2.7, §4.4.1. F. Sun, J. Liu, J. Wu, C. Pei, X. Lin, W. Ou, and P. Jiang (2019) BERT4Rec: sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM 2019), p. 1441–1450. Cited by: §2.2. P. Vansteenwegen, W. Souffriau, and D. Van Oudheusden (2011) The orienteering problem: a survey. European Journal of Operational Research 209 (1), p. 1–10. Cited by: §2.3. R. Wille (1982) Restructuring lattice theory: an approach based on hierarchies of concepts. In Ordered Sets, I. Rival (Ed.), p. 445–470. Cited by: §2.5. Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu (2021) A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems 32 (1), p. 4–24. External Links: Document Cited by: §2.1. S. Yang, J. Liu, and K. Zhao (2022) GETNext: trajectory flow map enhanced transformer for next POI recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2022), p. 1144–1153. Cited by: §1, §2.2. M. Ye, Y. Zheng, W. Cheng, X. Xie, and W. Ma (2011) Exploiting geographical influence for collaborative point-of-interest recommendation. In Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 325–334. Cited by: §2.1. Q. Yuan, G. Cong, Z. Ma, A. Sun, and N. Magnenat-Thalmann (2013) Time-aware point-of-interest recommendation. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 363–372. Cited by: §1, §2.1.