Dynamic membership for any fixed regular tree language is maintained in O(log n / log log n) per relabeling, with an exact constant-time class under a standard hardness conjecture.
Recognisable languages over monads
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
The principle behind algebraic language theory for various kinds of structures, such as words or trees, is to use a compositional function from the structures into a finite set. To talk about compositionality, one needs some way of composing structures into bigger structures. It so happens that category theory has an abstract concept for this, namely a monad. The goal of this paper is to propose monads as a unifying framework for discussing existing algebras and designing new algebras.
fields
cs.FL 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
Dynamic Membership for Regular Tree Languages
Dynamic membership for any fixed regular tree language is maintained in O(log n / log log n) per relabeling, with an exact constant-time class under a standard hardness conjecture.