Some Properties of Iterated Languages

Journal of Logic, Language and Information 25 (2):191-213 (2016)
  Copy   BIBTEX

Abstract

A special kind of substitution on languages called iteration is presented and studied. These languages arise in the application of semantic automata to iterations of generalized quantifiers. We show that each of the star-free, regular, and deterministic context-free languages are closed under iteration and that it is decidable whether a given regular or determinstic context-free language is an iteration of two such languages. This result can be read as saying that the van Benthem/Keenan ‘Frege Boundary’ is decidable for large subclasses of natural language quantifiers. We also determine the state complexity of iteration of regular languages.

Categories

Keywords

Reprint years

DOI

10.1007/s10849-016-9239-6

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,592

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Iterating semantic automata.Shane Steinert-Threlkeld & I. I. I. Thomas F. Icard - 2013 - Linguistics and Philosophy 36 (2):151-173.
Almost All Complex Quantifiers are Simple.Jakub Szymanik - 2010 - In C. Ebert, G. Jäger, M. Kracht & J. Michaelis (eds.), Mathematics of Language 10/11, Lecture Notes in Computer Science 6149. Springer.
Squares of regular languages.Gerhard Lischke - 2005 - Mathematical Logic Quarterly 51 (3):299.
Basic Properties of Quantum Automata.Stanley Gudder - 2000 - Foundations of Physics 30 (2):301-319.
Generalized quantifiers and modal logic.Wiebe Van Der Hoek & Maarten De Rijke - 1993 - Journal of Logic, Language and Information 2 (1):19-58.
Generalized quantifiers and modal logic.Wiebe Hoek & Maarten Rijke - 1993 - Journal of Logic, Language and Information 2 (1):19-58.
Decidability problems in languages with Henkin quantifiers.Michał Krynicki & Marcin Mostowski - 1992 - Annals of Pure and Applied Logic 58 (2):149-172.
Beyond the Frege boundary.Edward L. Keenan - 1992 - Linguistics and Philosophy 15 (2):199-221.
Automata for Epistemic Temporal Logic with Synchronous Communication.Swarup Mohalik & R. Ramanujam - 2010 - Journal of Logic, Language and Information 19 (4):451-484.
Timing diagrams: Formalization and algorithmic verification. [REVIEW]Kathi Fisler - 1999 - Journal of Logic, Language and Information 8 (3):323-361.
On the expressive power of monotone natural language quantifiers over finite models.Jouko Väänänen & Dag Westerståhl - 2002 - Journal of Philosophical Logic 31 (4):327-358.
Corrigendum to “Generalized periodicity and primitivity for words”.Masami Ito & Gerhard Lischke - 2007 - Mathematical Logic Quarterly 53 (6):642-643.
Understanding Quantifiers in Language.Jakub Szymanik & Marcin Zajenkowski - 2009 - In N. A. Taatgen & H. van Rijn (eds.), Proceedings of the 31st Annual Conference of the Cognitive Science Society.
Formal languages defined by the underlying structure of their words.J. P. Ressayre - 1988 - Journal of Symbolic Logic 53 (4):1009-1026.
Index sets for ω‐languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.

Analytics

Added to PP
2016-04-04

Downloads
25 (#628,404)

6 months
5 (#627,481)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Shane Steinert-Threlkeld
University of Washington

Citations of this work

Add more citations

References found in this work

Generalized quantifiers and natural language.John Barwise & Robin Cooper - 1981 - Linguistics and Philosophy 4 (2):159--219.
Generalized Quantifiers and Natural Language.Jon Barwise - 1980 - Linguistics and Philosophy 4:159.
Quantifiers in Language and Logic.Stanley Peters & Dag Westerståhl - 2006 - Oxford, England: Oxford University Press UK.
Quantifiers in Language and Logic.Stanley Peters & Dag Westerståhl - 2006 - Oxford, England: Clarendon Press.

View all 22 references / Add more references