Gelle, Kitti and Iván, Szabolcs (2020) The Order Type of Scattered Context-Free Orderings of Rank One is Computable. LECTURE NOTES IN COMPUTER SCIENCE, 12011. pp. 273-284. ISSN 0302-9743
![[img]](http://real.mtak.hu/style/images/fileicons/text.png) |
Text
2020_Book_SOFSEM2020TheoryAndPracticeOfC.pdf Restricted to Registered users only Download (191kB) |
Official URL: https://doi.org/10.1007/978-3-030-38919-2_23
Abstract
A linear ordering is called context-free if it is the lexicographic ordering of some context-free language and is called scattered if it has no dense subordering. Each scattered ordering has an associated ordinal, called its rank. It is known that the isomorphism problem of context-free orderings is undecidable in general. In this paper we show that it is decidable whether a context-free ordering is scattered with rank at most one, and if so, its order type is effectively computable.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | PhD Szabolcs Iván |
| Date Deposited: | 29 Sep 2020 07:33 |
| Last Modified: | 29 Sep 2020 07:33 |
| URI: | http://real.mtak.hu/id/eprint/115224 |
Actions (login required)
 |
Edit Item |
