Information content in formal languages

Abstract

Motivated by creating physical theories, formal languages $S$ with variables are considered and a kind of distance between elements of the languages is defined by the formula $d(x,y)=\ell (x\nabla y)-\ell (x)\wedge \ell (y)$, where $\ell$ is a length function and $x\nabla y$ means the united theory of $x$ and $y$. Actually we mainly consider abstract abelian idempotent monoids $(S,\nabla )$ provided with length functions $\ell$. The set of length functions can be projected to another set of length functions such that the distance $d$ is actually a pseudometric and satisfies $d(x\nabla a,y\nabla b)\le d(x,y)+d(a,b)$. We also propose a "signed measure" on the set of Boolean expressions of elements in $S$, and a Banach-Mazur-like distance between abelian, idempotent monoids with length functions, or formal languages.

arXiv commentContent is completely unchanged, but explanatory text is inserted between lemmas, theorems and proofs for better understandability of the paper