2026/06/25 by Fabio F. G. Buono · 1 voice · 1 citation
Computer Science · #cs.FL #cs.LO
We introduce the observational hierarchy, a new axis of classification for formal languages, orthogonal to the Chomsky hierarchy. An observer is a function O : Σ^* → S that determines which information about the input is accessible to a computational system. The order-blind automaton, which perceives the input as a multiset of symbols rather than a sequence, constitutes the paradigmatic case. We prove that the class of languages recognisable by any machine equipped with such an observer coincides exactly with the permutation-closed languages. We then define a partial order on observers that induces a hierarchy of language classes parametrised not by the computational power of the machine, but by the structure of the observer. We prove that this hierarchy has the structure of a partial order with a diamond-shaped profile sub-lattice, comprising the length branch O_\bot \prec Olen \prec Oprof \prec O_\top and the parity branch O_\bot \prec Opar \prec Oprof \prec O_\top, with Olen and Opar incomparable, and an infinite subsequence branch O_\bot \prec O1 \prec O2 \prec ⋯ \prec O_\top, both converging to the complete observer. We prove that the observational hierarchy is strictly incomparable with the Chomsky hierarchy, and introduce the notion of observational complexity of a language. We further define observer-parametrised complexity classes PO and NPO, and show that computational hardness and structural blindness are two independent phenomena. In particular, P_Oprof = NP_Oprof holds as a structural collapse strictly inside P.