An Automata Theoretic Characterization of Weighted First-Order Logic - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020)
Communication Dans Un Congrès Année : 2023

An Automata Theoretic Characterization of Weighted First-Order Logic

Benjamin Monmege

Résumé

Since the 1970s with the work of McNaughton, Papert and Schützenberger, a regular language is known to be definable in the first-order logic if and only if its syntactic monoid is aperiodic. This algebraic characterisation of a fundamental logical fragment has been extended in the quantitative case by Droste and Gastin, dealing with polynomially ambiguous weighted automata and a restricted fragment of weighted first-order logic. In the quantitative setting, the full weighted first-order logic (without the restriction that Droste and Gastin use, about the quantifier alternation) is more powerful than weighted automata, and extensions of the automata with two-way navigation, and pebbles or nested capabilities have been introduced to deal with it. In this work, we characterise the fragment of these extended weighted automata that recognise exactly the full weighted first-order logic, under the condition that automata are polynomially ambiguous.
Fichier principal
Vignette du fichier
conf.pdf (1.27 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
licence

Dates et versions

hal-04281052 , version 1 (12-11-2023)

Licence

Identifiants

Citer

Dhruv Nevatia, Benjamin Monmege. An Automata Theoretic Characterization of Weighted First-Order Logic. International Symposium on Automated Technology for Verification and Analysis, 2023, Singapore, Singapore. pp.115-133, ⟨10.1007/978-3-031-45329-8_6⟩. ⟨hal-04281052⟩
143 Consultations
66 Téléchargements

Altmetric

Partager

More