REAL

The Order Type of Scattered Context-Free Orderings of Rank One is Computable

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] Text
2020_Book_SOFSEM2020TheoryAndPracticeOfC.pdf
Restricted to Registered users only

Download (191kB)

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 Edit Item