pith. sign in

arxiv: 2606.27407 · v1 · pith:YUKOZ3QRnew · submitted 2026-06-25 · 💻 cs.FL · cs.LO

Observers, Symmetries, and the Hierarchy of Language Classes: A Theory of Computation Parameterized by the Observer

Fabio F.G. Buono This is my paper

Pith reviewed 2026-06-29 01:31 UTC · model grok-4.3

classification 💻 cs.FL cs.LO
keywords observational hierarchypermutation-closed languagesprofile observerpartial orderP=NP collapseChomsky hierarchyobservational complexity
0
0 comments X

The pith

A partial order on observers induces a diamond-shaped hierarchy of language classes that collapses P and NP for the profile observer.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines observers as functions that extract specific information from input strings for a machine to use. By ordering these observers partially, it generates a hierarchy of recognizable language classes that depends on the observer's structure rather than machine power. This hierarchy forms a diamond lattice with branches for length, parity, and profile observers, plus an infinite chain, and stands apart from the Chomsky hierarchy. The profile observer, which tracks symbol frequencies, causes the polynomial-time deterministic and nondeterministic classes to coincide inside standard P, indicating that information access and computational difficulty operate separately.

Core claim

The central claim is that the observational hierarchy, induced by a partial order on observers, has a diamond-shaped profile sub-lattice with the length branch O_bot prec O_len prec O_prof prec O_top and the parity branch O_bot prec O_par prec O_prof prec O_top where O_len and O_par are incomparable, along with an infinite subsequence branch converging to the complete observer. This hierarchy is strictly incomparable with the Chomsky hierarchy, and for the profile observer the equality P_Oprof equals NP_Oprof holds as a structural collapse strictly inside P.

What carries the argument

The observer function O from strings to an information structure S, ordered by a partial order that determines the induced classes of languages recognizable by machines using that observer.

If this is right

  • The class of languages recognized by order-blind observers is exactly the permutation-closed languages.
  • The length and parity observers are incomparable under the partial order.
  • The profile observer induces a collapse where P and NP coincide for that parameterization.
  • An infinite ascending sequence of subsequence observers converges to the full observer.
  • Observational complexity of a language is defined separately from its standard complexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This parameterization could be used to analyze symmetries in other computational domains such as graphs or trees by defining suitable observers.
  • Similar observer-based hierarchies might reveal collapses in other complexity classes beyond P and NP.
  • The independence of hardness and blindness suggests that some classically hard problems could be tractable under appropriate information restrictions.
  • Testing the lattice with concrete languages like those based on symbol counts would verify the branches.

Load-bearing premise

That a partial order on observers can be defined to produce the claimed diamond lattice structure and that the profile observer causes P to equal NP independently of the machine model used.

What would settle it

An NP-complete language that is recognizable by a nondeterministic machine with the profile observer but not by any deterministic machine with that observer.

read the original abstract

We introduce the \emph{observational hierarchy}, a new axis of classification for formal languages, orthogonal to the Chomsky hierarchy. An observer is a function $O : \Sigma^* \to 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 O_{\mathrm{len}} \prec O_{\mathrm{prof}} \prec O_\top$ and the parity branch $O_\bot \prec O_{\mathrm{par}} \prec O_{\mathrm{prof}} \prec O_\top$, with $O_{\mathrm{len}}$ and $O_{\mathrm{par}}$ incomparable, and an infinite subsequence branch $O_\bot \prec O_1 \prec O_2 \prec \cdots \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 \emph{observational complexity} of a language. We further define observer-parametrised complexity classes $\mathbf{P}_O$ and $\mathbf{NP}_O$, and show that computational hardness and structural blindness are two independent phenomena. In particular, $\mathbf{P}_{O_{\mathrm{prof}}} = \mathbf{NP}_{O_{\mathrm{prof}}}$ holds as a structural collapse strictly inside $\mathbf{P}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces the observational hierarchy as an orthogonal axis to the Chomsky hierarchy for classifying formal languages. An observer is a function O: Σ* → S determining accessible information about the input. It proves that any machine equipped with an order-blind observer recognizes exactly the permutation-closed languages. A partial order on observers is defined, inducing a hierarchy of language classes with a diamond-shaped profile sub-lattice (O_⊥ ≺ O_len ≺ O_prof ≺ O_⊤ and O_⊥ ≺ O_par ≺ O_prof ≺ O_⊤ with O_len, O_par incomparable) plus an infinite subsequence branch, both converging to the complete observer O_⊤. The observational hierarchy is shown incomparable to the Chomsky hierarchy. Observer-parametrized classes P_O and NP_O are defined, with the claim that computational hardness and structural blindness are independent, and in particular P_{O_prof} = NP_{O_prof} holds as a structural collapse strictly inside P.

Significance. If the results hold, the exact coincidence between order-blind observers and permutation-closed languages provides a concrete, falsifiable characterization. The partial-order structure on observers and the claimed model-independent collapse P_{O_prof} = NP_{O_prof} inside P would constitute a novel parameterization of complexity by observer properties rather than machine power, with potential to separate structural blindness from computational hardness. The incomparability with the Chomsky hierarchy and the lattice profile add conceptual value if the induced language classes are rigorously established.

major comments (2)
  1. [observer-parametrised complexity classes] Section defining observer-parametrised complexity classes P_O and NP_O: the central claim that P_{O_prof} = NP_{O_prof} is a structural collapse independent of the underlying machine model is load-bearing but underspecified. No explicit interface is given for how O(w) is encoded and supplied to the machine (e.g., as extra input tape, oracle, or state component), whether time bounds are measured in |w| or |encoding(O(w))|, or how nondeterminism interacts with the fixed observed value. Without this, the equality may hold only for particular encodings rather than as a general fact induced by the partial order on observers.
  2. [partial order on observers] Section defining the partial order on observers and the induced language classes: the diamond-shaped profile sub-lattice (with O_len and O_par incomparable, both strictly below O_prof) is asserted to hold for the language classes, but the manuscript provides no verification that the incomparability and convergence properties survive the specific interface chosen for observer-machine interaction. This is required to substantiate that the lattice structure is independent of machine model details.
minor comments (2)
  1. Notation for the observer functions (O_len, O_par, O_prof) is introduced without an early table or diagram summarizing the partial order and the concrete S sets for each; this would improve readability of the lattice claims.
  2. The proof that order-blind automata recognize exactly the permutation-closed languages is stated in the abstract but would benefit from an explicit reference to the relevant theorem number in the main text for cross-checking.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The two major comments correctly identify that the interface between observers and machines must be made fully explicit to support the model-independence claims. We address each point below and will incorporate the requested clarifications.

read point-by-point responses

  1. Referee: Section defining observer-parametrised complexity classes P_O and NP_O: the central claim that P_{O_prof} = NP_{O_prof} is a structural collapse independent of the underlying machine model is load-bearing but underspecified. No explicit interface is given for how O(w) is encoded and supplied to the machine (e.g., as extra input tape, oracle, or state component), whether time bounds are measured in |w| or |encoding(O(w))|, or how nondeterminism interacts with the fixed observed value. Without this, the equality may hold only for particular encodings rather than as a general fact induced by the partial order on observers.

    Authors: We agree the interface requires explicit specification. In the revision we will add a subsection defining a standard interface: O(w) is supplied on a separate read-only auxiliary tape, running time is measured in |w|, and nondeterminism is the usual existential branching over machine states with the observer value held constant throughout the computation. Under this interface the proof that P_{O_prof} = NP_{O_prof} proceeds by exhibiting a deterministic polynomial-time algorithm that uses the profile information directly; nondeterminism therefore adds no power. The argument relies only on the observer being polynomial-time computable (true for O_prof) and does not depend on further encoding details. revision: yes

  2. Referee: Section defining the partial order on observers and the induced language classes: the diamond-shaped profile sub-lattice (with O_len and O_par incomparable, both strictly below O_prof) is asserted to hold for the language classes, but the manuscript provides no verification that the incomparability and convergence properties survive the specific interface chosen for observer-machine interaction. This is required to substantiate that the lattice structure is independent of machine model details.

    Authors: The diamond-shaped sub-lattice and the infinite branch are established directly at the level of the language classes induced by the observers, before any complexity interface is introduced. Strict inclusions and incomparabilities are witnessed by concrete languages (e.g., {a^n b^n} vs. its permutations) that are recognizable precisely when the observer supplies the requisite information. Because these separations depend only on which information the observer makes available, they are unaffected by the subsequent choice of how that information is presented to a machine. The same interface clarification added for the complexity classes will be stated to apply uniformly, confirming that the lattice properties remain intact. revision: yes

Circularity Check

0 steps flagged

No circularity; new definitions and proofs are self-contained

full rationale

The paper defines observers O: Σ* → S and a partial order on them, then proves that recognisable languages coincide with permutation-closed ones and that the induced hierarchy has a diamond profile with P_O_prof = NP_O_prof as a structural result. No quoted equations or steps reduce a claimed prediction or theorem to a fitted input, self-citation, or definitional renaming. The central collapse is asserted to follow from the observer parametrisation rather than being presupposed by it. This is the normal case of a self-contained definitional framework with independent proofs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract only; no specific free parameters, axioms, or invented entities can be extracted or verified from the provided text.

pith-pipeline@v0.9.1-grok · 5885 in / 1150 out tokens · 32887 ms · 2026-06-29T01:31:59.089987+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references

  1. [1]

    Equivalent comparisons of experiments.The Annals of Mathemat- ical Statistics, 24(2):265–272, 1953

    David Blackwell. Equivalent comparisons of experiments.The Annals of Mathemat- ical Statistics, 24(2):265–272, 1953

    1953

  2. [2]

    Three models for the description of language.IRE Transactions on Information Theory, 2(3):113–124, 1956

    Noam Chomsky. Three models for the description of language.IRE Transactions on Information Theory, 2(3):113–124, 1956. 1These sources shaped the conceptual framework. All formal results are independent of them and stand on their own proofs. 16

    1956

  3. [3]

    Cover and Joy A

    Thomas M. Cover and Joy A. Thomas.Elements of Information Theory. Wiley, 2 edition, 2006

    2006

  4. [4]

    Inverse kinematics of a 10 dof modular hyper-redundant robot resorting to exhaustive and error-optimization methods: A comparative study

    Mario Sáenz Espinoza, Jose Goncalves, Paulo Leitao, Jose Luis Gonzalez Sanchez, and Alberto Herreros. Inverse kinematics of a 10 dof modular hyper-redundant robot resorting to exhaustive and error-optimization methods: A comparative study. In Robotics Symposium and Latin American Robotics Symposium (SBR-LARS), 2012 Brazilian, pages 125–130. IEEE, 2012

    2012

  5. [5]

    Pereira, and José Gonçalves

    Mario Sáenz Espinoza, Ana I. Pereira, and José Gonçalves. Optimization methods for hyper-redundant robots’ inverse kinematics in biomedical applications. InAIP Conference Proceedings, volume 1479, page 818, 2012

    2012

  6. [6]

    Rohit J. Parikh. On context-free languages.Journal of the ACM, 13(4):570–581, 1966

    1966

  7. [7]

    North Oxford Academic, 1986

    Jean-Éric Pin.Varieties of Formal Languages. North Oxford Academic, 1986

    1986

  8. [8]

    Piecewise testable events

    Imre Simon. Piecewise testable events. InAutomata Theory and Formal Languages, volume 33 ofLecture Notes in Computer Science, pages 214–222. Springer, 1975

    1975

  9. [9]

    Cengage Learning, 3 edition, 2012

    Michael Sipser.Introduction to the Theory of Computation. Cengage Learning, 3 edition, 2012

    2012

  10. [10]

    Writing research theses or dissertations

    Ming Tham. Writing research theses or dissertations. University of Newcastle Upon Tyne, May 2001. A Proof of Lemma 9.2 This appendix gives the full formal proof of the simulation lemma stated and sketched in Section 9. Full proof of Lemma 9.2.LetO: Σ ∗ →Sbe computable in times(|x|)wheresis a function such that the computation halts after at mosts(|x|)step...

    2001

  11. [11]

    This takes at most s(|x|)steps

    Run the computation ofOonxto producey= enc(O(x)). This takes at most s(|x|)steps

  12. [12]

    This takes at mostp(|y|)steps

    RunMony. This takes at mostp(|y|)steps

  13. [13]

    ThetotaltimeforM ′ onxisatmosts(|x|)+p(|y|)+O(1)

    Output whateverMoutputs. ThetotaltimeforM ′ onxisatmosts(|x|)+p(|y|)+O(1). Since|y|=|enc(O(x))| ≤s(|x|), we havep(|y|)≤p(s(|x|)), giving total timeq(|x|) =s(|x|) +p(s(|x|)) +O(1). Whensis a polynomial,qis also a polynomial in|x|, soM ′ ∈PwitnessesL∈P. The conclusionP O ⊆Pfollows: everyL∈P O has a TMMdeciding it underOin polynomial time in|enc(O(x))|. The ...