2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27398 2026-08-21T14:42:38Z ddc:004 open_access

Boolean Combinations of ω-Rational Trace Languages: Emptiness, Rationality, Regularity Kuske, Dietrich Mazurkiewicz traces rational and regular languages degrees of unsolvability This paper studies decision problems for Boolean combinations of ω-rational trace languages. The complexities of these decision problems (emptiness, regularity, rationality) are classified depending on properties of the independence alphabets and of the Boolean combinations allowed. For any of the problems, we obtain a trichotomy ranging from decidable over a low level of the arithmetical hierarchy to a low level of the analytical hierarchy. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dietrich Kuske 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.17 urn:nbn:de:0030-drops-273981 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode