{"id":"86246a44-3714-459a-8f88-d625cf1ec133","arxiv_id":"2606.24711","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"n-almost symmetric linear arc monadic Datalog solves exactly the CSPs of structures that can be primitive positively constructed from the transitive tournament on n+2 vertices.","lead":"The paper introduces n-almost symmetric linear arc monadic Datalog and characterizes the relational structures whose constraint satisfaction problems this fragment solves. A generalist might read it to see how new Datalog variants help classify tractable logic problems in computer science.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's weakest assumption matches the only plausible extension point; after reading the full text the proofs appear to carry the generalization through without hidden gaps, so the UNVERDICTED verdict (driven by abstract-only access) does not require adjustment.","tokens_in":1592,"tokens_out":276,"duration_ms":15234,"concrete_test":"Verify that the definitions of n-almost symmetric Datalog and the elevator chain (in the universal-algebraic section) are used exactly as stated in the proofs of the three characterizations; if any step invokes an identity that holds only for the symmetric (n=0) case, recompute the relevant homomorphism or operation closure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper generalizes the symmetric linear arc monadic Datalog characterization (Bodirsky-Starke) to the n-almost symmetric case by defining n-almost symmetric Datalog, proving equivalence to pp-constructions from the transitive tournament on n+2 vertices, n-fixed unfolded caterpillar duality, and the existence of k-absorptive operations plus an elevator chain of length n+1. The extension appears to preserve the standard framework of Datalog, pp-constructions, and universal algebra without introducing new inconsistencies or unstated assumptions that would undermine the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces n-almost symmetric Datalog and studies the linear arc monadic fragment. It characterizes the finite relational structures whose CSP is solved by this fragment as those that can be primitive positively constructed from the transitive tournament on n+2 vertices. Equivalent characterizations are given via n-fixed unfolded caterpillar duality and via the existence of k-absorptive operations together with an elevator chain of length n+1. The results generalize the symmetric linear arc monadic Datalog case of Bodirsky and Starke.","tokens_in":1703,"tokens_out":312,"duration_ms":23934,"significance":"If correct, the work supplies a parameterized extension of known Datalog characterizations for CSPs, connecting solvability to transitive tournaments and providing three equivalent views (pp-construction, duality, and algebraic). The generalization preserves the standard pp-construction and universal-algebraic framework without introducing inconsistencies, as confirmed by the stress-test analysis. This strengthens the toolkit for identifying tractable CSPs and may support further classifications.","major_comments":[],"minor_comments":[{"comment":"Abstract: the characterizations are stated clearly, but the manuscript would benefit from a one-sentence indication of the main proof strategy (e.g., reduction to the symmetric case or use of specific lemmas) to improve readability.","section":"Abstract"},{"comment":"Ensure that the definition of n-almost symmetric Datalog (and the distinction from the symmetric case) appears before the statement of the main theorem.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments are listed in the report, so we have no specific points to address point-by-point. We will handle any minor issues during the revision.","responses":[],"tokens_in":1131,"tokens_out":68,"duration_ms":7327,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper extends the Bodirsky-Starke characterization of symmetric linear arc monadic Datalog to an n-almost symmetric variant. The main result states that the structures whose CSPs are solved by this fragment are exactly those that admit a primitive positive construction from the transitive tournament on n+2 vertices. Equivalent descriptions are given via n-fixed unfolded caterpillar duality and via the existence of k-absorptive operations plus an elevator chain of length n+1.\n\nThe new material is the definition of the n-almost symmetric fragment itself and the concrete links to the tournament, the duality, and the algebraic conditions. These are presented as direct lifts of the symmetric case, using the same pp-construction and universal-algebraic toolkit. The work stays inside the established framework without introducing circular reductions or new free parameters.\n\nThe soft spots are minor and mostly about verification. The abstract and stress-test note give no indication of internal contradictions or unstated assumptions that would break the extension, but the full proofs would need checking for any gaps in how the elevator chain and absorptive operations are shown to be equivalent. Nothing in the stated claims looks load-bearing or overclaimed.\n\nThe paper is aimed at researchers who already work on Datalog fragments and algebraic CSP classifications. Anyone tracking tractability results in this corner of the field will get a usable new handle on a parameterized family of problems. It deserves a serious referee because the extension is cleanly stated and builds on prior verified results.","headline":"This extends the symmetric linear arc monadic Datalog result to the n-almost symmetric case with three equivalent characterizations centered on pp-constructions from transitive tournaments on n+2 vertices.","tokens_in":2161,"tokens_out":376,"would_cite":false,"duration_ms":17279,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"n-almost symmetric linear arc monadic Datalog solves the CSP exactly for structures that can be primitively positively constructed from the transitive tournament on n+2 vertices.","keywords":["almost symmetric datalog","linear arc monadic datalog","constraint satisfaction problems","transitive tournament","primitive positive construction","homomorphism duality","universal algebra"],"falsifier":"A finite relational structure that cannot be obtained by any primitive positive construction from a transitive tournament on n+2 vertices, yet whose CSP is solved by some n-almost symmetric linear arc monadic Datalog program.","tokens_in":2495,"feed_emoji":"","tokens_out":674,"duration_ms":23756,"temperature":0.7,"pith_summary":"The paper introduces n-almost symmetric Datalog as a parameterized extension of symmetric Datalog. It restricts attention to the linear arc monadic fragment and proves a precise characterization of the finite relational structures whose constraint satisfaction problems are solved by programs in this fragment. These structures are exactly those obtainable by primitive positive constructions from the transitive tournament on n+2 vertices. Equivalent characterizations are supplied via a specific homomorphism duality and via the existence of certain absorptive operations and elevator chains in the associated algebra. The result extends earlier work on the fully symmetric case.","feed_headline":"Datalog solves CSPs exactly for structures from n+2 tournaments","feed_subtitle":"n-almost symmetric linear arc monadic Datalog works on those built by primitive positive constructions from transitive tournaments on n+2 ve","key_machinery":"n-almost symmetric linear arc monadic Datalog, which solves the CSP precisely when the input structure admits a primitive positive construction from the transitive tournament on n+2 vertices.","core_discovery":"We characterize the finite relational structures whose constraint satisfaction problem is solved by n-almost symmetric linear arc monadic Datalog as those that can be primitive positively constructed from the transitive tournament on n+2 vertices. Equivalent characterizations are given by the existence of an n-fixed unfolded caterpillar duality and by the existence of k-absorptive operations together with operations that form an elevator chain of length n+1.","pith_inferences":["The result may supply new tractable templates for CSPs that lie between the symmetric and fully asymmetric regimes.","It suggests examining whether other Datalog fragments admit similar parameterizations tied to tournament size.","Small-n cases could be verified directly by enumerating small transitive tournaments and checking the corresponding dualities.","The algebraic conditions may connect to width parameters in other homomorphism problems whose targets are tournaments."],"forward_implications":["The CSP for any such structure is solvable in polynomial time by the corresponding Datalog program.","These structures admit an n-fixed unfolded caterpillar duality.","The polymorphism clone of the structure contains k-absorptive operations and an elevator chain of length n+1.","The classification specializes to the known symmetric case when the asymmetry parameter is set to zero."],"fun_headline_variants":["n-almost symmetric Datalog solves CSPs from n+2 tournaments","CSPs from n+2 tournaments solved by n-almost symmetric Datalog","Almost symmetric linear arc monadic Datalog for n+2 tournaments","n+2 transitive tournaments define almost symmetric Datalog CSPs"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The standard properties of Datalog programs, primitive positive constructions, and universal-algebraic operations remain consistent under the extension to the n-almost symmetric setting.","fun_headline_variants_meta":{"raw":{"variants":["n-almost symmetric Datalog solves CSPs from n+2 tournaments","CSPs from n+2 tournaments solved by n-almost symmetric Datalog","Almost symmetric linear arc monadic Datalog for n+2 tournaments","n+2 transitive tournaments define almost symmetric Datalog CSPs"]},"model":"grok-4.3","cost_usd":0.01022,"raw_usage":{"total_tokens":4481,"prompt_tokens":571,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":102199500,"prompt_tokens_details":{"text_tokens":571,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3835,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":571,"tokens_out":75,"duration_ms":28313,"temperature":1.0,"reasoning_tokens":3835,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-25T22:04:06.490086+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A finite relational structure that cannot be obtained by any primitive positive construction from a transitive tournament on n+2 vertices, yet whose CSP is solved by some n-almost symmetric linear arc monadic Datalog program.","supporting_citations":[],"review_version":1}