The ordinal generated by an ordinal grammar is computable

Gelle, Kitti and Iván, Szabolcs (2019) The ordinal generated by an ordinal grammar is computable. THEORETICAL COMPUTER SCIENCE, 793 (1). pp. 1-13. ISSN 0304-3975

Text The ordinal generated by an ordinal grammar is computable - TCS 2019.pdf Restricted to Registered users only Download (802kB)

Abstract

A prefix grammar is a context-free grammar whose nonterminals generate prefix-free languages. A prefix grammar G is an ordinal grammar if the language is well-ordered with respect to the lexicographic ordering. It is known that from a finite system of parametric fixed point equations over ordinals one can construct an ordinal grammar G such that the lexicographic order of G is isomorphic with the least solution of the system, if this solution is well-ordered. In this paper we show that given an ordinal grammar, one can compute (the Cantor normal form of) the order type of the lexicographic order of its language, yielding that least solutions of fixed point equation systems defining algebraic ordinals are effectively computable (and thus, their isomorphism problem is also decidable).

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:	28 Sep 2020 13:53
Last Modified:	28 Sep 2020 13:53
URI:	http://real.mtak.hu/id/eprint/115165

Available Versions of this Item

• The ordinal generated by an ordinal grammar is computable. (deposited 23 Sep 2019 11:42)
  • The ordinal generated by an ordinal grammar is computable. (deposited 28 Sep 2020 13:53) [Currently Displayed]

Actions (login required)

Edit Item