City Research Online

Register complexity and determinisation of max-plus automata

Daviaud, L. ORCID: 0000-0002-9220-7118 (2020). Register complexity and determinisation of max-plus automata. ACM SIGLOG News, 7(2), pp. 4-11. doi: 10.1145/3397619.3397621

Abstract

We survey some results about the sequentiality problem for max-plus automata and its generalisation, the register complexity problem for cost register automata. We compare classes of functions computed by maxplus automata and by cost register automata with respect to the notion of ambiguity. The two models are introduced gently, so the novice reader is welcome!

Publication Type: Article
Additional Information: Copyright © 2020 Copyright is held by the owner/author(s). This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM SIGLOG News, http://dx.doi.org/10.1145/3397619
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
Date Deposited: 13 Aug 2020 10:46
URI: https://openaccess.city.ac.uk/id/eprint/24682
[img]
Preview
Text - Accepted Version
Download (296kB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login