Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.
Zhen Dong, Haiping Wang, Wei Tu, Yuan Liu, Bing Wang, Xuan Sun, Jinzhou Cao, Ronald Clark 等 17 位作者
Cities must coordinate domains like infrastructure, mobility, environmental management, emergency response, and public services as conditions evolve. An urban Spatio-Temporal Intelligence (STI) system helps the city monitor citywide states, analyze problems, plan and execute interventions, and adapt through feedback, making urban governance more timely, effective, and transparent. Recent urban twinning and agentic AI techniques provide foundations for such systems. From a twin-agent perspective, this survey takes a system-level view of how these disparate techniques can be coherently integrated into an urban STI system. Specifically, we review how the twin reconstructs and represents a persistent, information-enriched urban environment, and how the agent understands the twin via interfaces, reasons over it, acts reliably, and continuously evolves with the city. Built upon this synthesis, we summarize a two-loop blueprint, where an inner agent loop for grounding, reasoning, and verification, and an outer system loop linking data, twin, agentic action, feedback, and update. We then use this to structure an STI research agenda and show how a shared prototype supports diverse urban domains.
Zeyu Zhang Amazon AGI, Kexuan Sun Amazon, Zheng Tang Amazon, Jens-S. Vöckler Amazon, Thien Huu Nguyen University of Oregon, Thuy Vu Amazon AGI
Knowledge Graph (KG) retrieval is a promising augmentation to address knowledge gaps and hallucinations in LLMs. As KGs in practice are stored in graph databases (e.g., Wikidata, Freebase), accurate retrieval requires translating natural language questions into structured queries (query generation). A key challenge of query generation is Text-to-Cypher, which generates Cypher queries for property graphs (e.g., Neo4j), a paradigm increasingly adopted in industry for their scalable architectures and expressive schemas. However, compared to other query generation tasks such as Text-to-SQL or Text-to-SPARQL, Text-to-Cypher remains underexplored due to scarce public KGs and datasets. Existing datasets are small, domain-limited, and lack diversity, constraining LLM progress. To address this, we introduce CypherSmith, an instruction-tuning dataset over 12\times larger than prior public Text-to-Cypher datasets, spanning diverse domains to better support LLM fine-tuning. Our key distinction lies in fully leveraging open-source LLMs for large-scale synthetic data generation and introducing a novel likelihood-based filtering technique to ensure high-quality Text-to-Cypher data. Extensive experiments demonstrate the effectiveness of CypherSmith, achieving state-of-the-art LLM performance.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表
Xing Ma, Yangjie Zhou National University of Singapore, Wu Sun, Zihan Liu, Jingwen Leng Shanghai Jiao Tong University, Yun Lin Shanghai Jiao Tong University, Shixuan Sun Shanghai Jiaotong University, Minyi Guo Shanghai Jiao Tong University 等 9 位作者
Efficient CUDA implementations of attention mechanisms are critical to modern deep learning systems, yet supporting diverse and evolving attention variants remains challenging. Existing frameworks and compilers trade performance for flexibility, while expert-written kernels achieve high efficiency but are difficult to adapt. Recent work explores large language models (LLMs) for GPU kernel generation, but prior studies report unstable correctness and significant performance gaps for complex operators such as attention.We present CuBridge, an LLM-based framework that adapts expert-written attention kernels through a structured lift–transfer–lower workflow. CuBridge starts from expert-written CUDA attention kernels and lifts them into an executable intermediate representation that makes execution orchestration explicit while abstracting low-level CUDA syntax. Given a user-provided PyTorch specification, CuBridge generates and verifies a target IR program, then reconstructs optimized CUDA code via reference-guided lowering. Across diverse attention variants and GPU platforms, CuBridge consistently produces correct kernels and substantially outperforms general frameworks, compiler-based approaches, and prior LLM-based methods.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表