CBCL: Safe Self-Extending Agent Communication

Computer Science > Cryptography and Security [Submitted on 16 Apr 2026] CBCL: Safe Self-Extending Agent Communication Hugo O'Connor Agent communication languages (ACLs) enable heterogeneous agents to share knowledge and coordinate across diverse domains. This diversity demands extensibility, but expressive extension mechanisms can push the input language beyond the complexity classes where full validation is tractable. We present CBCL (Common Business Communication Language), an agent communication language that constrains all messages, including runtime language extensions, to the deterministic context-free language (DCFL) class. CBCL allows agents to define, transmit, and adopt domain-specific "dialect" extensions as first-class messages; three safety invariants (R1--R3), machine-checked in Lean 4 and enforced in a Rust reference implementation, prevent unbounded expansion, applying declared resource limits, and preserving core vocabulary. We formalize the language and its safety properties in Lean 4, implement a reference parser and dialect engine in Rust with property-based and differential tests, and extract a verified parser binary. Our results demonstrate that homoiconic protocol design, where extension definitions share the same representation as ordinary messages, can be made provably safe. As autonomous agents increasingly extend their own communication capabilities, formally bounding what they can express to each other is a precondition for oversight. Comments: 10 pages. Accepted at IEEE LangSec Workshop 2026 (camera-ready). Reference implementation, Lean 4 formalization, and verified parser: this https URL ; Nostr transport binding: this https URL Subjects: Cryptography and Security (cs.CR); Artificial Intelligence (cs.AI); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO) ACM classes: D.2.4; D.3.1; F.4.2; F.4.3 Cite as: arXiv:2604.14512 [cs.CR]   (or arXiv:2604.14512v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.14512 Focus to learn more Submission history From: Hugo O'Connor Mr [view email] [v1] Thu, 16 Apr 2026 00:57:48 UTC (23 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.AI cs.FL cs.LO References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)