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...
| প্রধান লেখক: | , |
|---|---|
| বিন্যাস: | Journal article |
| ভাষা: | English |
| প্রকাশিত: |
2009
|
| _version_ | 1826271524405903360 |
|---|---|
| author | Benedikt, M Segoufin, L |
| author_facet | Benedikt, M Segoufin, L |
| author_sort | Benedikt, M |
| collection | OXFORD |
| description | 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 show that this characterization yields a decision procedure for determining whether a regular tree language is first-order definable: The procedure is polynomial time in the minimal automaton presenting the regular language. We also provide an algorithm for deciding whether a regular language is definable in first-order logic supplemented with modular quantifiers. © 2009 ACM. |
| first_indexed | 2024-03-06T21:58:01Z |
| format | Journal article |
| id | oxford-uuid:4d9987d0-5b8c-4378-a197-7a2942a82353 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:58:01Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | oxford-uuid:4d9987d0-5b8c-4378-a197-7a2942a823532022-03-26T15:56:18ZRegular Tree Languages Definable in FO and in FOmodJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:4d9987d0-5b8c-4378-a197-7a2942a82353EnglishSymplectic Elements at Oxford2009Benedikt, MSegoufin, LWe 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 show that this characterization yields a decision procedure for determining whether a regular tree language is first-order definable: The procedure is polynomial time in the minimal automaton presenting the regular language. We also provide an algorithm for deciding whether a regular language is definable in first-order logic supplemented with modular quantifiers. © 2009 ACM. |
| spellingShingle | Benedikt, M Segoufin, L Regular Tree Languages Definable in FO and in FOmod |
| title | Regular Tree Languages Definable in FO and in FOmod |
| title_full | Regular Tree Languages Definable in FO and in FOmod |
| title_fullStr | Regular Tree Languages Definable in FO and in FOmod |
| title_full_unstemmed | Regular Tree Languages Definable in FO and in FOmod |
| title_short | Regular Tree Languages Definable in FO and in FOmod |
| title_sort | regular tree languages definable in fo and in fomod |
| work_keys_str_mv | AT benediktm regulartreelanguagesdefinableinfoandinfomod AT segoufinl regulartreelanguagesdefinableinfoandinfomod |