Regular Tree Languages Definable in FO and in FOmod
We consider regular languages of labeled trees. We give an effective characterization of the regular languages over such trees that are definable in first-order logic in the language of labeled graphs. These languages are the analog on trees of the locally threshold testable languages on strings. We...
Main Authors: | Benedikt, M, Segoufin, L |
---|---|
Format: | Journal article |
Language: | English |
Published: |
2009
|
Similar Items
-
Deciding definability in FO2(<h,<v) on trees
by: Thomas Place, et al.
Published: (2015-09-01) -
FO2(<,+1,~) on data trees, data tree automata and branching vector addition systems
by: Florent Jacquemard, et al.
Published: (2016-04-01) -
Tree Languages Defined in First-Order Logic with One Quantifier Alternation
by: Mikolaj Bojanczyk, et al.
Published: (2010-10-01) -
On logical hierarchies within FO^2-definable languages
by: Manfred Kufleitner, et al.
Published: (2012-08-01) -
Piecewise testable tree languages
by: Mikołaj Bojańczyk, et al.
Published: (2012-09-01)