Semantic flowers for good-for-games and deterministic automata

Dell'Erba, Daniele, Schewe, Sven ORCID: 0000-0002-9093-9518, Tang, Qiyi ORCID: 0000-0002-9265-3011 and Zhanabekova, Tansholpan (2024) Semantic flowers for good-for-games and deterministic automata. Information Processing Letters, 185. p. 106468.

PDF
Semantic Flowers for Good-for-Games and Deterministic Automata.pdf - Author Accepted Manuscript
Download (771kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.ipl.2023.106468

Abstract

We present an innovative approach for capturing the complexity of ω-regular languages using the concept of flowers. This semantic tool combines two syntax-based definitions, namely the Mostowski hierarchy of word languages and syntactic flowers. The former is based on deterministic parity automata with a limited number of priorities, while the latter simplifies deterministic parity automata by reducing the number of priorities used, without altering their structure. Synthesising these two approaches yields a semantic concept of flowers, which offers a more effective way of dealing with the complexity of ω-regular languages. This letter provides a comprehensive definition of semantic flowers and shows that it captures the complexity of ω-regular languages. We also show that this natural concept yields simple proofs of the expressive power of good-for-games automata.

Item Type:	Article
Uncontrolled Keywords:	Clinical Research
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	04 Dec 2023 15:08
Last Modified:	15 Mar 2024 09:05
DOI:	10.1016/j.ipl.2023.106468
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3177155