Computational semantics for monadic quantifiers. (English) Zbl 0920.03044
Van Benthem, Büchi, Ladner and others, including the author, used classes of finite automata to characterize classes of monadic quantifiers – those Lindström quantifiers which are defined via universes equipped with a finite number of subsets only.
In this paper, the author gives a comprehensive survey of such characterization results.
In this paper, the author gives a comprehensive survey of such characterization results.
Reviewer: D.Mundici (Milano)
MSC:
| 03C13 | Model theory of finite structures |
| 03C80 | Logic with extra quantifiers and operators |
| 03D05 | Automata and formal grammars in connection with logical questions |
| 03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |
References:
| [1] | Van benthem J., Essays in Logical Semantics, D. Reidel Publishing Company (1986) · Zbl 0619.03021 · doi:10.1007/978-94-009-4540-1 |
| [2] | Van benthem J., Generalized Quantifiers pp 31– |
| [3] | Krynicki M., Quantifiers: Logics, Models and Computation pp 1– (1995) |
| [4] | Ladner R. E., Information and Control 33 pp 281– (1977) · Zbl 0387.68037 · doi:10.1016/S0019-9958(77)90443-0 |
| [5] | Llndström P., Theoria 32 pp 186– (1966) |
| [6] | Makowsky J. A., Quantifiers: Logics, Models and Computation pp 313– (1995) |
| [7] | Mostowski M., Bulletin of the Section of Logic 20 pp 67– (1991) |
| [8] | Mostowski M., The Journal of Symbolic Logic. |
| [9] | Mostowski M., Nauka i jezyk, Wydzial Filozofii i Socjologii Uuiwersytetu Warszawskiego, Warszawa pp 201– (1994) |
| [10] | Väänänen J., Prace Naukowe Instytutu Matematyki Politechniki Wroclawskiej, Wroclaw, in: Set Theory and Hierarchy Theory pp 117– (1977) |
| [11] | Straubing H., Lec. Notes in Comput. Sci. 317 88, in: Proc. 15th ICALP pp 561– |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
