On the Order Type of Scattered Context-Free Orderings
We show that if a context-free grammar generates a language whose lexicographic ordering is well-ordered of type less than ω^2, then its order type is effectively computable.
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2019-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1909.08543v1 |
| _version_ | 1819017134398767104 |
|---|---|
| author | Kitti Gelle Szabolcs Iván |
| author_facet | Kitti Gelle Szabolcs Iván |
| author_sort | Kitti Gelle |
| collection | DOAJ |
| description | We show that if a context-free grammar generates a language whose lexicographic ordering is well-ordered of type less than ω^2, then its order type is effectively computable. |
| first_indexed | 2024-12-21T02:58:42Z |
| format | Article |
| id | doaj.art-74dc4199d5784bd08957330873570534 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-21T02:58:42Z |
| publishDate | 2019-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-74dc4199d5784bd089573308735705342022-12-21T19:18:14ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802019-09-01305Proc. GandALF 201916918210.4204/EPTCS.305.12:13On the Order Type of Scattered Context-Free OrderingsKitti Gelle0Szabolcs Iván1 University of Szeged, Hungary University of Szeged, Hungary We show that if a context-free grammar generates a language whose lexicographic ordering is well-ordered of type less than ω^2, then its order type is effectively computable.http://arxiv.org/pdf/1909.08543v1 |
| spellingShingle | Kitti Gelle Szabolcs Iván On the Order Type of Scattered Context-Free Orderings Electronic Proceedings in Theoretical Computer Science |
| title | On the Order Type of Scattered Context-Free Orderings |
| title_full | On the Order Type of Scattered Context-Free Orderings |
| title_fullStr | On the Order Type of Scattered Context-Free Orderings |
| title_full_unstemmed | On the Order Type of Scattered Context-Free Orderings |
| title_short | On the Order Type of Scattered Context-Free Orderings |
| title_sort | on the order type of scattered context free orderings |
| url | http://arxiv.org/pdf/1909.08543v1 |
| work_keys_str_mv | AT kittigelle ontheordertypeofscatteredcontextfreeorderings AT szabolcsivan ontheordertypeofscatteredcontextfreeorderings |