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


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,
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
Text - Accepted Version
Download (296kB) | Preview



Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login