Vi anser en förlängning av monadisk andra ordningen logik, tolkas över det oändliga binära trädet, av den kvalitativa vägmätning kvantifier. Denna kvantifier säger att uppsättningen av oändliga stigar i trädet uppfyller en formel har Lebesgue-mått ett. Vi bevisar att denna logik är obeslutbar. För att göra detta bevisar vi att problemet med tomheten i den kvalitativa universella paritetsträdautomaten är obeslutbart. Kvalitativ innebär att en körning av en trädautomaton accepterar om uppsättningen stigar i loppet som uppfyller acceptansvillkoret har Lebesgue-mått ett. Formella språk och automatateori → Trädspråk; Formella språk och automatateori → Automata över oändliga objekt; Logik → Högre ordning logik; Matematik vid beräkning → Sannolikhet och statistik Nyckelord och fraser MSO, trädautomata,.-regelbundna förhållanden, nästan-säkra semantik Monadic Second-Order logik (MSO) är en förlängning av första ordningen logik med kvantifiering på uppsättningar. Det grundläggande resultatet om MSO är att dess teori om det oändliga binära trädet är decidable [19]. Det finns ett antal sätt att utvidga detta resultat: till strukturer som genereras av vissa verksamheter (se undersökningen [20], av vissa ytterligare unary predikat [11], och av vissa generella kvantifiers [2, 15]. I denna not anser vi att MSO+ ska =1 väg, förlängningen av MSO av den mått-teoretiska kvantifiern  och =1 väg X, infördes i [14]. Här anges att den uppsättning stigar i trädet som uppfyller kraven har Lebesgue-mått som är lika med 1. Detta innebär, intuitivt, att en slumpmässig väg nästan säkert uppfyller  ska, där en slumpmässig väg genereras genom att upprepade gånger vända ett rättvist mynt för att bestämma sig för att gå till vänster eller höger. Ett svagt fragment av detta * Vi blev medvetna om att detta resultat redan bevisats av Mikołaj Bojańczyk, Edon Kelmendi och Michał Skrzypczak genom ett arbete som utfördes oberoende av vårt [6]. Vår bevisteknik bygger på probabilistisk automata, som skiljer sig från Bojańczyk et al.
Mer nyligen, Berthon et al. REF visade den något svagare obeslutbarhet resultat att tomhet är obeslutsam för universella paritet träd automata med kvalitativa semantik.
Monadic Second-Order Logic with Path-Measure Quantifier is Undecidable
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}