Squares of regular languages

Mathematical Logic Quarterly 51 (3):299 (2005)
  Copy   BIBTEX

Abstract

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context-free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties

Categories

Keywords

Reprint years

DOI

10.1002/malq.200410032

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,069

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

Some Properties of Iterated Languages.Shane Steinert-Threlkeld - 2016 - Journal of Logic, Language and Information 25 (2):191-213.
Corrigendum to “Generalized periodicity and primitivity for words”.Masami Ito & Gerhard Lischke - 2007 - Mathematical Logic Quarterly 53 (6):642-643.
Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics.Linh Nguyen - 2008 - Logic Journal of the IGPL 16 (2):175-193.
Formal languages defined by the underlying structure of their words.J. P. Ressayre - 1988 - Journal of Symbolic Logic 53 (4):1009-1026.
Timing diagrams: Formalization and algorithmic verification. [REVIEW]Kathi Fisler - 1999 - Journal of Logic, Language and Information 8 (3):323-361.
Restorations of punctured languages and similarity of languages.Gerhard Lischke - 2006 - Mathematical Logic Quarterly 52 (1):20-28.
Monadic Monadic Second Order Logic.Mikołaj Bojańczyk, Bartek Klin & Julian Salamanca - 2023 - In Alessandra Palmigiano & Mehrnoosh Sadrzadeh (eds.), Samson Abramsky on Logic and Structure in Computer Science and Beyond. Springer Verlag. pp. 701-754.
The Search for Regularity in Irregularity: Defectiveness and its Implications for our Knowledge of Words.Marianne Mithun - 2010 - In Defective Paradigms: Missing Forms and What They Tell Us. pp. 125.
Regular Ultrapowers at Regular Cardinals.Juliette Kennedy, Saharon Shelah & Jouko Väänänen - 2015 - Notre Dame Journal of Formal Logic 56 (3):417-428.
Aural Pattern Recognition Experiments and the Subregular Hierarchy.James Rogers & Geoffrey K. Pullum - 2011 - Journal of Logic, Language and Information 20 (3):329-342.

Analytics

Added to PP
2013-12-01

Downloads
21 (#762,344)

6 months
5 (#710,385)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references