Characterizing non counting operator precedence languages in a locally testable manner

The aim of this thesis is to expand the knowledge about Operator Precedence Languages (OPL) by finding one of its subclasses such that it is Non-Counting. In order to achieve such a goal, there has been taken inspiration from the LTO family of languages, which corresponds to the Non-Counting Regular Language family. The found class (LTOP) is shown to coincide with the family of Non-Counting Operator Precedence Languages, and its relation with other representations from the literature is studied. In the end, the problem of deciding whether a language is LTOP or not is proven to be decidable.

Lo scopo della tesi è di trovare una sottoclasse dei linguaggi a precedenza ad operatori che sia non counting. Per raggiungere tale obiettivo ci si è ispirati alla classe dei linguaggi LTO, che corrisponde ai linguaggi Non Counting Regolari. La classe cosi trovata (LTOP) si dimostra coincidere con la classe dei linguaggi Non Counting OP, e viene studiata la sua relazione con le altre rappresentazioni presenti in letteratura. In conclusione, viene dimostrato che il problema di decidere se un linguaggio è o meno LTOP è decidibile.