Semantics modulo satisfiability with applications: function representation, probabilities and game theory (2021)
- Authors:
- Autor USP: PRETO, SANDRO MÁRCIO DA SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2021.tde-17062021-163257
- Subjects: REDES NEURAIS; LÓGICA MATEMÁTICA
- Keywords: Coerência de restrições; Coherence of constraints; Equilíbrio de Nash; Formal methods; Funções lineares por partes; Funções racionais de McNaughton; Function representation; Jogos com incerteza; Lógica infinito-valorada de Lukasiewicz; Lógicas proposicionais; Lukasiewicz infinitely-valued logic; Métodos formais; Nash equilibrium; Neural networks; Non-classical probabilities; Piecewise linear functions; Probabilidades não clássicas; Probabilistic constraints; Probabilistic satisfiability; Propositional logics; Rational McNaughton functions; Representação de funções; Restrições probabilísticas; Satisfatibilidade probabilística; Semânticas de valoração; Uncertain games; Valuation semantics
- Agências de fomento:
- Language: Inglês
- Abstract: No contexto das lógicas proposicionais, aplicamos semânticas módulo satisfatibilidade - uma semântica restrita que contempla somente valorações que satisfazem algum conjunto específico de fórmulas - com o objetivo de resolver de forma eficiente algumas tarefas computacionais. Três destas possíveis aplicações são desenvolvidas. Começamos estudando a possibilidade de representar implicitamente funções racionais de McNaughton na Lógica Infinito-valorada de Lukasiewicz por meio de semânticas módulo satisfatibilidade. Investigamos teoricamente algumas abordagens para este conceito de representação, chamado representação módulo satisfatibilidade, e descrevemos um algoritmo polinomial que constrói representações no sistema recém-introduzido. Uma implementação do algoritmo, resultados de testes e formas de gerar aleatoriamente funções racionais de McNaughton para os testes são apresentados. Mais que isso, propomos uma aplicação destas representações à verificação formal de propriedades de redes neurais através do ferramental de inferência da Lógica Infinito-valorada de Lukasiewicz. Então, passamos a investigar a satisfatibilidade da atribuição conjunta de probabilidades a fórmulas da Lógica Infinito-valorada de Lukasiewicz, um problema sabidamente NP-completo. Fornecemos um algoritmo exato de decisão derivado da combinação de métodos de álgebra linear com semânticas módulo satisfatibilidade. Fornecemos também uma implementação para tal algoritmo para o qual o fenômeno da transiçãode fase é empiricamente detectado. Por último, estudamos a situação em teoria dos jogos dos chamados jogos observáveis, que são jogos que sabidamente alcançam um equilíbrio de Nash, entretanto, um observador externo não conhece qual o exato perfil de ações que ocorre em uma instância específica; então, tal observador atribui probabilidades subjetivas às ações do jogadores. Estudamos o problema de decisão de determinar se um conjunto dessas restrições probabilísticas é coerente reduzindo-o aos problemas de satisfatibilidade de atribuições probabilísticas a fórmulas lógicas tanto na Lógica Proposicional Clássica quanto na Lógica Infinito-valorada de Lukasiewicz dependendo se somente equilíbrios puros são permitidos ou, também, equilíbrios mistos. Tais reduções dependem das propriedades das semânticas módulo satisfatibilidade. Oferecemos discussões sobre complexidade e algoritmos para o problema de coerência e, também, para o problema de computar restrições probabilísticas maximal e minimal sobre ações que preservem a coerência
- Imprenta:
- Data da defesa: 04.06.2021
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
PRETO, Sandro Márcio da Silva. Semantics modulo satisfiability with applications: function representation, probabilities and game theory. 2021. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2021. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-17062021-163257/. Acesso em: 11 abr. 2026. -
APA
Preto, S. M. da S. (2021). Semantics modulo satisfiability with applications: function representation, probabilities and game theory (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-17062021-163257/ -
NLM
Preto SM da S. Semantics modulo satisfiability with applications: function representation, probabilities and game theory [Internet]. 2021 ;[citado 2026 abr. 11 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-17062021-163257/ -
Vancouver
Preto SM da S. Semantics modulo satisfiability with applications: function representation, probabilities and game theory [Internet]. 2021 ;[citado 2026 abr. 11 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-17062021-163257/ - Effective reasoning over neural networks using Lukasiewicz logic
- Probably half true: probabilistic satisfiability over Łukasiewicz infinitely-valued logic
- Polyhedral semantics and the tractable approximation of Łukasiewicz infinitely-valued logic
- Benchmarking Łukasiewicz logic solvers with properties of neural networks
- Linking Łukasiewicz logic and boolean maximum satisfiability
- Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics
- Proving properties of binary classification neural networks via Łukasiewicz logic
- Representing rational McNaughton functions via MODSAT relativisation
- Efficient representation of piecewise linear functions into Łukasiewicz logic modulo satisfiability
- An efficient algorithm for representing piecewise linear functions into logic
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
