Computational semantics for monadic quantifiers


Συγγραφέας: Marcin Mostowski


Marcin Mostowski: Computational semantics for monadic quantifiers (pdf, 16 pages)
The paper gives a survey of known results related to computational devices (finite and push–down automata) recognizing monadic generalized quantifiers in finite models. Some of these results are simple reinterpretations of descriptive—feasible correspondence theorems from finite–model theory. Additionally a new result characterizing monadic quantifiers recognized by push down automata is proven.