A Unified Algebraic Framework for Hedge Automata Using Horizontal Language Expressions

This paper presents a unified algebraic and computational framework for classical hedge automata and related algebraic structures. The framework extends the open-source TARgET library with support for hedge-based structures. The formal development discusses classical hedge automata and establishes their correspondence with regular hedge expressions through a derivative-based construction. The framework provides multiple acceptance mechanisms, including in-memory tree-based acceptance and streaming acceptance based on regular expressions and word deterministic finite automata for representing horizontal hedge languages. As a use case, the streaming mechanisms are applied to the incremental validation of JSON documents without constructing the entire input tree. Their behavior is evaluated experimentally on synthetically generated JSON files ranging from small inputs to multi-gigabyte documents, demonstrating the ability of the streaming acceptors to process large inputs while preserving the corresponding hedge automaton’s acceptance behavior. The implementation and benchmark datasets are publicly available to support reproducibility.