Title

Strict LT2: Regular:: Local: Recognizable

Abstract

We provide a characterization of the local sets (sets of trees generated by CFGs) in terms of definability in a restricted logical language, which we contrast with a similar characterization of the recognizable sets (sets of trees accepted by finite-state tree automata). In a strong sense, the distinction between these two captures abstractly the distinction between ordinary CFGs and those in which labels are finitely extended with additional features (as in GPSG). In terms of descriptive complexity, the contrast is quite profound--while the recognizable sets axe characterized by a monadic second-order language, the local sets axe characterized by a severely restricted modal language. In the domain of strings, there is an analogous contrast between the regular languages and the strict 2-locally testable languages, a weak subclass of the star-free sets.

Publication Date

1-1-1997

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

1328

Number of Pages

366-385

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/bfb0052167

Socpus ID

84949752805 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84949752805

This document is currently not available here.

Share

COinS