Abstrakt. Vi ger en enkel översättning av satisfiability problem för vanliga grammatiklogik med konversation i GF 2, vilket är skärningspunkten mellan den bevakade fragment och 2-variabel fragment av första ordningen logik. Denna översättning är teoretiskt intressant eftersom den översätter modala logiker med vissa ramvillkor till första ordningens logik, utan att uttryckligen uttrycka villkoren. En följd av översättningen är att det allmänna tillfredsställande problemet för regelbunden grammatiklogik med omvänt är i EXPTIME. Detta utökar ett tidigare resultat av den första författaren för grammatiklogik utan att konversera. Med samma metod visar vi hur vissa andra modala logiker naturligt kan översättas till GF 2, inklusive nominell spänd logik och intuitionistisk logik. Enligt vår uppfattning visar resultaten i detta dokument att det naturliga första ordningens fragment som motsvarar vanlig grammatiklogik helt enkelt är GF 2 utan extra maskiner såsom fasta punktoperatorer.
I REF gav Demri och de Nivelle en översättning av satisfiability-problemet för grammatiklogik med att konversera in i det tvåvariabla bevakade fragmentet GF 2 av första ordningens logik, och visade att det allmänna satisfiability-problemet för regelbunden grammatiklogik med konversering är i EXPTime.
Deciding regular grammar logics with converse through first-order logic
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}