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
- 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
-
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://www.teses.usp.br/teses/disponiveis/45/45134/tde-17062021-163257/. Acesso em: 24 abr. 2024. -
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://www.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 2024 abr. 24 ] Available from: https://www.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 2024 abr. 24 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-17062021-163257/ - Proving properties of binary classification neural networks via Łukasiewicz logic
- Linking Łukasiewicz logic and boolean maximum satisfiability
- Polyhedral semantics and the tractable approximation of Łukasiewicz infinitely-valued logic
- An efficient algorithm for representing piecewise linear functions into logic
- Effective reasoning over neural networks using Lukasiewicz logic
- Coherence of probabilistic constraints on Nash equilibria
- Representing rational McNaughton functions via MODSAT relativisation
- Probably half true: probabilistic satisfiability over Łukasiewicz infinitely-valued logic
- Benchmarking Łukasiewicz logic solvers with properties of neural networks
- Efficient representation of piecewise linear functions into Łukasiewicz logic modulo satisfiability
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
