• Medientyp: E-Artikel
  • Titel: Piecewise testable tree languages
  • Beteiligte: Bojańczyk, Mikołaj; Segoufin, Luc; Straubing, Howard
  • Erschienen: Centre pour la Communication Scientifique Directe (CCSD), 2012
  • Erschienen in: Logical Methods in Computer Science, Volume 8, Issue 3 (2012)
  • Sprache: Englisch
  • DOI: 10.2168/lmcs-8(3:26)2012
  • ISSN: 1860-5974
  • Schlagwörter: General Computer Science ; Theoretical Computer Science
  • Entstehung:
  • Anmerkungen:
  • Beschreibung: <jats:p>This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its syntactic monoid is J-trivial.</jats:p>
  • Zugangsstatus: Freier Zugang