Piecewise Testable Tree Languages

This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma 1 formulas. 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 formulas if and only if its syntact...

Full description

Saved in:
Bibliographic Details
Main Authors: Bojanczyk, M., Segoufin, L., Straubing, H.
Format: Conference Proceeding
Language:English
Subjects:
Algebra
Automata
Automatic testing
Boolean functions
Computer science
Educational institutions
logic
Logic functions
Logic testing
Page description languages
tree automata
Veins
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma 1 formulas. 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 formulas if and only if its syntactic monoid is J-trivial.
ISSN:1043-6871
2575-5528
DOI:10.1109/LICS.2008.46