2026-07-23T07:58:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10973 2024-03-06T10:46:57Z ddc:004 open_access

The Quantifier Alternation Hierarchy of Synchronous Relations Figueira, Diego Ramanathan, Varun Weil, Pascal synchronous relations automatic relations first-order logic characterization quantifier alternation The class of synchronous relations, also known as automatic or regular, is one of the most studied subclasses of rational relations. It enjoys many desirable closure properties and is known to be logically characterized: the synchronous relations are exactly those that are defined by a first-order formula on the structure of all finite words, with the prefix, equal-length and last-letter predicates. Here, we study the quantifier alternation hierarchy of this logic. We show that it collapses at level Sigma_3 and that all levels below admit decidable characterizations. Our results reveal the connections between this hierarchy and the well-known hierarchy of first-order defined languages of finite words. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Figueira and Varun Ramanathan and Pascal Weil 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.29 urn:nbn:de:0030-drops-109735 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.29 eng https://creativecommons.org/licenses/by/3.0/legalcode