Mostrando postagens com marcador LIAMF. Mostrar todas as postagens
Mostrando postagens com marcador LIAMF. Mostrar todas as postagens

terça-feira, 28 de abril de 2009

Revisão de Crenças em Lógica de Horn e Outros Fragmentos


------------------------------------------------------------------------------------------
 Seminário do Grupo de Lógica, Inteligência Artificial
 e Métodos Formais - LIAMF
 Seminário Registrado na CPG do IME/USP
 Página: http://www.ime.usp.br/~liamf/seminarios/index.html

-------------------------------------------------------------------------------------------

Título: Revisão de Crenças em Lógica de Horn e Outros Fragmentos
Palestrante:  Renata Wassermann

Data:   30/04/2009, 14h00
Local:  Sala 241A, IME-USP

Resumo:
--------------
A teoria clássica de revisão de crenças, conhecida como teoria AGM
graças aos trabalhos iniciais de Alchourrón, Gärdenfors e Makinson,
geralmente assume que a lógica por trás do raciocínio do agente contém
no mínimo a lógica clássica. No entanto, nos últimos anos surgiu um
grande interesse por aplicações de revisão de crenças a lógicas
sub-clássicas, como a lógica de Horn e as lógicas de descrição. Neste
seminário pretendo apresentar os problemas que surgem quando abandonamos
a supraclassicalidade e algumas tentativas minhas e de outros de
solucioná-los.

Todos são benvindos!

--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 9688, 3091
6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814
4135


quinta-feira, 23 de abril de 2009

Next Steps in Propositional Horn Contraction



Amanhã teremos a visita do Ivan Varzinczak, que foi aluno de doutorado do
Andreas Herzig em Toulouse e atualmente trabalha no Instituto Meraka, na África
do Sul. Faremos um seminário extra às 11:30, na sala de reuniões do bloco C.
Seguem os dados abaixo.


------------------------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-------------------------------------------------------------------------------------------

Título: Next Steps in Propositional Horn Contraction

Palestrante: Ivan J. Varzinczak

Data:   23/04/2009, 11h30
Local:  Sala de reuniões, bloco C, IME-USP


Abstract: Standard belief contraction assumes an underlying logic containing
full classical propositional logic, but there are good reasons for considering
contraction in less expressive logics. In this paper we focus on Horn logic. In
addition to being of interest in its own right, our choice is motivated by the
use of Horn logic in several areas, including ontology reasoning in description
logics. We consider three versions of contraction: entailment-based and
inconsistency-based contraction (e-contraction and i-contraction, resp.),
introduced by Delgrande for Horn logic, and package contraction (p-contraction),
studied by Fuhrmann and Hansson for the classical case. We show that the
standard basic form of contraction, partial meet, is too strong in the Horn
case. We define more appropriate notions of basic contraction for all three
types above, and provide associated representation results in terms of
postulates. Our results stand in contrast to Delgrande's conjectures that
orderly maxichoice is the appropriate contraction for both e- and i-contraction.
Our interest in p-contraction stems from its relationship with an important
reasoning task in ontological reasoning: repairing the subsumption hierarchy in
EL. This is closely related to p-contraction with sets of basic Horn clauses
(Horn clauses of the form p -> q). We show that this restricted version of
p-contraction can also be represented as i-contraction.

Todos são benvindos.


O Algoritmo de Dubois e a transição de fase


-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título:O Algoritmo de Dubois e a transição de fase
Palestrante: Eduardo Menezes

Data:   23/04/2009, 14h00
Local:  Sala 241A, IME-USP

A transição de fase no problema da satisfatibilidade booleana (SAT)  é um
fenômeno que afeta a maioria dos algoritmos utilizados hoje em dia e dificulta
muito o problema SAT para um certo intervalo de instâncias.
Neste seminário, será apresentado um algoritmo criado em 1989 por Olivier
Dubois. Esse algoritmo possui uma propriedade interessante: parece não sofrer
alteração no comportamento quando está na região da transição de fase.
Também serão apresentados idéia de otimizações que podem ser aplicadas ao
algoritmo de Dubois na tentativa de torná-lo mais competitivo em comparação com
os algoritmos atuais.
--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135



quinta-feira, 16 de abril de 2009

Classes de Complexidade de Linguagens


==========================================
Adolfo Neto
Departamento Acadêmico de Informática
Universidade Tecnológica Federal do Paraná
Fone: (41) 3310-4644 / Fax: (41) 3310-4646
Web: http://www.dainf.ct.utfpr.edu.br/~adolfo
Blog: http://professoradolfo.blogspot.com
==========================================



---------- Forwarded message ----------
From: Rafael Testa <rafaeltesta@gmail.com>
Date: 2009/4/16
Subject: [seminarios-CLE] seminário
To: seminarios-CLE@yahoogroups.com
Prezados,
lembro que próxima quarta, dia 22, teremos seminário do Prof. José Guimarães - como sempre às 16h00, no CLE. Título e resumo abaixo.
Contamos com a presença de todos.
Abraços,
Rafael Testa

+++++++++++++++++++++++++++=

Título: Classes de Complexidade de Linguagens
Resumo:
    Uma linguagem formal pode ser classificada de acordo com a complexidade das máquinas de Turing que podem decidir se um elemento pertence ou não a ela. As medidas de complexidade mais comuns são tempo e espaço. As linguagens formais podem ser agrupadas em classes de complexidade, que são conjuntos que contém linguagens com características de complexidade comum. Por exemplo, temos a class P das linguagens que podem ser decididas por uma máquina de Turing em um número de passos Polinomial no tamanho da entrada. E a classe NP das linguagens que podem ser aceitas por uma máquina de Turing não-determinística em tempo polinomial.
     Este seminário apresentará os teoremas básicos desta área de pesquisa e também os relacionamentos entre as mais importantes classes de complexidade, que são P, NP, PSPACE, NPSPACE e EXP. Finalizaremos apresentando uma sugestão de pesquisa nesta área.
   
José de Oliveira Guimarães é Professor da UFSCar desde 1992, atualmente no Campus de Sorocaba, tendo feito graduação, mestrado e doutorado em Computação. Suas áreas de atuação em pesquisa são Linguagens de Programação, Programação Orientada a Objetos, Reflexão Computacional e Compiladores. Suas áreas de interesse são Lógica (principalmente Computabilidade), Classes de Complexidade e Computação Quântica.



__._,_.___


terça-feira, 10 de março de 2009

Problemas em Aberto em Lógica Computacional e em Lógica Probabilística -- Seminário LIAMF dia 12/03/2009

---------- Forwarded message ----------
From: Marcelo Finger <mfinger AT ime.usp.br>
Date: 2009/3/10
Subject: Seminário LIAMF dia 12/03/2009


------------------------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-------------------------------------------------------------------------------------------

Título: Problemas em Aberto em Lógica Computacional e em Lógica Probabilística
Palestrante:  Marcelo Finger

Data:   12/03/2009, 14h00
Local:  Sala 241A, IME-USP

Resumo:
--------------

 Neste primeiro seminário do ano, apresentaremos uma série de problemas em
 aberto relacionados a temas de Lógica Computacional e Lógica e
 Probabilidade.  Muitos destes problemas rondam o problema central P=?NP, mas
 formam uma série de outras frentes de pesquisa em melhoria da eficiência
 na resolução de problemas em áreas tão diversas como IA, sistemas
 distribuídos, algoritmos, etc.

 Este seminário destina-se aos alunos que estão procurando temas de
 pesquisa e/ou estão querendo saber dos diversos desafios na área.

Todos são benvindos!
--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





quinta-feira, 4 de dezembro de 2008

Reasoning about Dynamic Depth Profiles

------------------------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-------------------------------------------------------------------------------------------


Título: Reasoning about Dynamic Depth Profiles

Palestrante: Paulo E. Santos (FEI)

Data: 08/12/2008, 14h30

Local: Sala 03B, IME-USP


Abstract: Reasoning about perception of depth and about spatial
relations between moving physical objects is a challenging problem.
We investigate the representation of depth and motion
by means of depth profiles whereby each object in the world
is represented as a single peak. We propose a logical theory,
formulated in the situation calculus (SC), that is used for reasoning
about object motion (including motion of the observer).
The theory proposed here is comprehensive enough to accommodate reasoning
about both sensor data and actions in the world. We show that
reasoning about depth profiles is sound and complete with
respect to actual motion in the world.
This shows that in the conceptual neighbourhood diagram (CND) of
all possible depth perceptions, the transitions between perceptions are
logical consequences of the proposed theory of depth and motion.

At the end of the talk I'll present some current work on the  integration of
 probabilistic reasoning in this framework.

sexta-feira, 28 de novembro de 2008

Real-Time Dynamic Programming

------------------------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-------------------------------------------------------------------------------------------

Título: Real-Time Dynamic Programming

Palestrante: Renato Schattan Pereira Coelho

Data: 01/12/2008, 14h30

Local: Sala 03B, IME-USP

Resumo:

O problema de tomada automática de decisão em geral envolve a questão de levar o
agente de um estado inicial a estados com alguma característica de nosso
interesse (estados meta) com o menor custo possível. Assim, queremos que o
agente seja capaz de, para cada estado do mundo, escolher uma ação que minimize
o custo esperado de se chegar a um estado meta, ou seja, queremos definir uma
política que mapeie estados às melhores ações que o agente deve executar.

Uma das abordagens que tem conseguido mais sucesso na resolução desses
problemas, tanto teoricamente quanto em competições de planejamento
probabilístico, é a de programação dinâmica com atualizações assíncronas dos
valores dos estados.
Neste seminário vamos apresentar o algoritmo Real-Time Dynamic Programming
(RTDP), e duas de suas extensões (LRTDP, FRTDP e BRTDP), cuja idéia básica é
fazer várias simulações da execução de uma política gulosa (como se o agente
estivesse treinando) e
atualizar os valores dos estado enquanto se faz a simulação. Por fim, vamos
falar brevemente sobre as alterações que devem ser feitas em um desses
algoritmos (LRTDP) para que ele resolva problemas em que as probabilidades de
transição de estados não são totalmente conhecidas.

domingo, 23 de novembro de 2008

SPUDD: usando Diagramas de Decisão para resolver Processos Markovianos de Decisão fatorados.

------------------------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-------------------------------------------------------------------------------------------

Título:

SPUDD: usando Diagramas de Decisão para resolver Processos Markovianos de
Decisão fatorados.

Palestrante: Karina Valdivia Delgado (estudante de doutorado IME)
Data: 24/11/2008, 14h30
Local: Sala 03B, IME-USP

Resumo:

Planejamento probabilístico é uma sub-área de planejamento da Inteligência
Artificial que usa Processos Markovianos de Decisão (MDPs) como modelo
matemático. MDPs fornecem um arcabouço matemático para modelar e resolver
problemas de decisão sequencial com incerteza em ambientes completamente
observáveis.

Um MDP modela a interação entre um agente e seu ambiente. A cada instante o
agente faz uma escolha de ações (com efeitos probabilísticos) e decide executar
uma ação que produzirá um estado futuro e uma recompensa. O objetivo do agente é
maximizar a recompensa ganha ao longo de uma sequência de escolhas de ações.

Uma das dificuldades para resolver um problema MDP é que frequentemente o
tamanho do espaço de estados é muito grande.  Resultados recentes têm
demonstrado que é possível resolver uma formulação fatorada de um MDP chamada de
MDP-fatorado numa maneira mais eficiente (com millões de estados) quando
comparados com soluções clássicas baseados em programação dinâmica e com o
espaço de estados enumerativo.

Nesta palestra mostraremos o algoritmo SPUDD em que os estados são agregados
implicitamente usando ADDs (diagramas de decisão algébricos) para representar a
função valor e as políticas, evitando assim  trabalhar com o espaço de estados
enumerativos.  SPUDD modifica o algoritmo clássico de iteração de valor usando
ADDs permitindo que o cálculo do valor esperado e  as maximizações sejam feitas
eficientemente.


--
 Marcelo Finger


quinta-feira, 13 de novembro de 2008

Revising Specifications with CTL Properties using Bounded Model Checking


==========================================
Adolfo Neto
Departamento Acadêmico de Informática
Universidade Tecnológica Federal do Paraná
Fone: (41) 3310-4644 / Fax: (41) 3310-4646
Web: http://www.dainf.ct.utfpr.edu.br/~adolfo
Blog: http://professoradolfo.blogspot.com
==========================================



---------- Forwarded message ----------
From: Marcelo Finger <mfinger@ime.usp.br>
Date: Thu, Nov 13, 2008 at 2:27 PM
Subject: Seminário LIAMF dia 17/11/2008
To: liamf-anuncios@ime.usp.br
Cc: liamf-seminarios@ime.usp.br

Título: Revising Specifications with CTL Properties using Bounded Model Checking

Palestrantes:  Marcelo Finger e Renata Wassermann

Data:   17/11/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:

 During the process of software development, it is very common that
 inconsistencies arise between the formal specification and some
 desired property. Belief Revision deals with the problem of
 accommodating new information that may be inconsistent with an
 existing knowledge base.

 In this paper, we propose the use of belief revision techniques in
 order to deal with inconsistencies in formal specifications. The
 main problem to be solved is that the most well known results for
 belief revision only hold for logics which are monotonic and
 compact, while most discrete-time temporal logics used to
 express system properties -- and in particular, CTL --- are not
 compact.  We suggest the use of bounded model-checking, transforming
 the problem from CTL into classical propositional logic and then
 transforming back the results to suggest revisions to the user.

--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





quinta-feira, 6 de novembro de 2008

Alternating-time Temporal Logic, Coalition Logic and STIT theory of agency and their epistemic extensions

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Alternating-time Temporal Logic, Coalition Logic and STIT theory of
agency and their epistemic extensions

Palestrante:  Andreas Herzig (prof. Visitante IME-USP), IRIT-CNRS (Toulouse,
France)

Data:   10/11/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:
Alternating-time Temporal Logic (ATL), Coalition Logic and so-called STIT
theories of agency (`seeing-to-it-that') are three different formalisms to
model the capability of agents and groups of agents to ensure some
outcome. While they come from 3 different traditions (theoretical computer
science, game theory and philosophy of action), in all of them the notion
of independence of agents is fundamental. I shall give an overview, and
explain that only STIT theories allow to reason about uniform strategies,
i.e. strategies where it does not suffice that the agent has the
capability to ensure some fact, but he must also know that he has that
ability.

--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





sábado, 1 de novembro de 2008

Ontological Engineering and its Applications (emphasis in Educational Contexts)


-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Ontological Engineering and its Applications (emphasis in Educational
Contexts)

Palestrante:  Seiji Isotani
Department of Knowledge Systems
ISIR, Osaka University, Japan
http://www.ei.sanken.osaka-u.ac.jp/~isotani

Data:   3/11/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:

In recent years, with the increasing use of technology, Artificial
Intelligence has been gradually and successfully introduced into
a variety of systems (including educational ones). However, major
challenges still remain. Among these, we are interested in how to
represent the knowledge of intelligent authoring systems and then how
to use this knowledge efficiently. Usual approaches to such issues
provide their systems with a kind of expertise using a set of
heuristics and domain theories built-in the procedures (programming
languages). This means that the programmers, not the systems, have an
understanding about the knowledge being used. To deal with this
problem, we will show some of the efforts the ontology engineering
community has been done in order to create better intelligent systems.
First of all, we will try to create a basic common understanding about
the difference between heavy- and light-weight ontologies. Then, we
will explain the research being done in Japan to define heavy-weight
ontologies that support the development of intelligent systems.
Finally, we will present the development of an ontology for Education
used to support collaborative learning and its results to (a) produce
semantically-enabled intelligent systems; and (b) help instructors to
design effective collaboration in real scenarios.


 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





sexta-feira, 24 de outubro de 2008

Alternating-time Temporal Logic, Coalition Logic and STIT theory of agency and their epistemic extensions


-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Alternating-time Temporal Logic, Coalition Logic and STIT theory of
agency and their epistemic extensions

Palestrante:  Andreas Herzig (prof. Visitante IME-USP), IRIT-CNRS (Toulouse,
France)

Data:   27/10/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:
Alternating-time Temporal Logic (ATL), Coalition Logic and so-called STIT
theories of agency (`seeing-to-it-that') are three different formalisms to
model the capability of agents and groups of agents to ensure some
outcome. While they come from 3 different traditions (theoretical computer
science, game theory and philosophy of action), in all of them the notion
of independence of agents is fundamental. I shall give an overview, and
explain that only STIT theories allow to reason about uniform strategies,
i.e. strategies where it does not suffice that the agent has the
capability to ensure some fact, but he must also know that he has that
ability.


--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





sábado, 18 de outubro de 2008

Depuração de programas baseada em modelos: uma abordagem hierárquica

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Depuração de programas baseada em modelos: uma abordagem hierárquica
Palestrante:  Wellington Pinheiro

Data:   20/10/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:

Diagnóstico baseado em modelos (Model based diagnosis - MBD) é uma técnica
de Inteligência Artificial usada para encontrar componentes falhos em
dispositivos físicos (sistemas). MBD também tem sido utilizado para auxiliar
programadores experientes a encontrarem falhas em seus programas, sendo essa
técnica chamada de depuração de programas baseada em modelos (Model
based software debugging - MBSD). Embora o MBSD possa auxiliar programadores
experientes a entenderem e corrigirem seus erros, essa abordagem precisa ser
aprimorada para aprendizes de programação.

Nesse seminário, mostraremos uma proposta de uso da técnica de diagnóstico
hierárquico para dar suporte a aprendizes de programação explorando a idéia de
componentes abstratos, tais como: padrões elementares, funções e
procedimentos. Com a utilização de uma abordagem de diagnóstico hierárquico,
será possível encontrar falhas no programa do aluno em diversos níveis de
abstração. Com isso, espera-se que o aluno seja capaz de compreender a origem
de seus erros e aprender durante esse processo.


--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





quarta-feira, 8 de outubro de 2008

An optimal method for reasoning about actions

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: An optimal method for reasoning about actions
Palestrante:  Andreas Herzig (prof. Visitante IME-USP), IRIT-CNRS (Toulouse,
France)

Data:   13/10/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:
(paper with Hans van Ditmarsch and Tiago de Lima "Optimal regression for
reasoning about knowledge and actions" at AAAI'07; later version available
at http://drops.dagstuhl.de/portals/index.php?semnr=07351)

The frame problem is one of the major obstacles on the road towards
logical reasoning about actions in AI. Two versions can be distinguished.
The representational version is the problem of designing a logical
language and a semantics such that domains can be described without
stating all the non-effects of each action. The inferential version is to
design an efficient reasoning method for a given solution to the
representational problem. Several solutions to the representational
problem where proposed in the past. The solution of Reiter (1991), further
extended by Scherl and Levesque (1993), relies on the hypothesis of
inertia: each action only changes the truth value of a small number of
facts, leaving all the others unchanged. Reiter's associated regression
inference method eliminates action symbols from formulas by rewriting them
to formulas of propositional logic (or formulas of epistemic logic in
Scherl and Levesque's case). In the general case, however, the regressed
formula may be exponentially larger than the original formula, and hence
non-optimal. We here present the first optimal reasoning method for
Reiter's and Scherl and Levesque's solution. We first show that their
solution to the representational frame problem can be encoded into dynamic
epistemic logic of van Ditmarsch, van der Hoek and Kooi (2005). We then
give a polynomial reduction to epistemic logic. We also establish some
complexity results for our reasoning method: NP-completeness for a single
agent, PSPACE-completeness for multiple agents, and EXPTIME-completeness
when common knowledge is involved.


domingo, 5 de outubro de 2008

Construção de mapas semânticos com robôs móveis


-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Construção de mapas semânticos com robôs móveis
Palestrante:  Fabiano Rogério Corrêa

Data:   06/10/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:

A robótica móvel teve um avanço considerável na última década devido ao
emprego de modelos probabilísticos e técnicas de aprendizado computacional.
Hoje em dia é possível mapear de maneira eficiente e robusta um ambiente e
simultaneamente localizar o robô móvel, apenas com as informações espaciais
obtidas de seus sensores. No entanto, novos desafios estão sendo abordados
na área, e a incorporação de informação semântica (classificação das
informações espaciais) vem sendo adotada por alguns pesquisadores como a
direção a ser seguida na solução dos problemas.

Nessa palestra será exposto um panorama dos trabalhos mais recentes na área
de construção de mapas semânticos, seguida de uma indicação de que modelos
probabilísticos de primeira ordem possibilitam um melhor tratamento da
natureza relacional dos dados obtidos pelos robôs móveis para classificação
semântica.


--
 Marcelo Finger
 Departamento de Ciencia da Computacao 
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





sexta-feira, 26 de setembro de 2008

Densidade e bolas fechadas em análise de agrupamentos

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Densidade e bolas fechadas em análise de agrupamentos
Palestrante: Carlos Gonzalez

Data: 29/09/2008, 14h30
Local: Sala 03B, IME-USP

Resumo:
-------

Uma das conceitualizações possíveis em análise de agrupamentos
consiste em selecionar as áreas do espaço de características (feature
space) que apresentam maior densidade. O conceito básico de densidade
surge de considerar a quantidade
de pontos que tem uma determinada região do espaço. Seguindo com esta linha de
raciocínio, precisamos determinar, de alguma maneira, a região que vai ser
considerada para calcular a densidade.

Neste sentido, noções topológicas bem conhecidas, como a de bola
fechada, podem nos auxiliar. Mas para isto precisamos analisar o
seguinte problema: dado um conjunto de elementos do espaço de
características: como determinar uma bola
fechada mínima ou minimal que inclua este conjunto? Uma vez solucionado este
problema, podemos pensar várias maneiras de aplicar este contexto metodológico
em análise de agrupamentos. Se trabalharmos em análise de agrupamentos
hierárquico acumulativo, podemos determinar que dois agrupamentos
A_{1} e A_{2} serão selecionados para formar um novo agrupamento se a
densidade da menor bola fechada que inclui A_{1} e A_{2} tem a maior
densidade ou uma densidade maximal. Denominamos a este algoritmo
``grande bola''. Também podemos usar alguma noção de distância para
determinar, para cada par de agrupamentos A_{1} e A_{2} o conjunto E
dos elementos de A_{1} e A_{2} que estão mais próximos, considerando
para a seleção de agrupamentos a densidade da menor menor bola fechada
que inclua E. Este algoritmo é denominado ``bola no meio''.

A principal vantagem (o que na realidade foi a motivação inicial)
consiste em que a generalidade de aplicação destes conceitos permite
comparar tipos de espaços e noções de noções de distância muito
diferentes. Neste trabalho, usamos este enfoque conceitual e os
algoritmos mencionados para comparar o conhecido espaço métrico que
usa a noção de distância de Jaccard com os espaços booleanos,
nos quais as distâncias são elementos da mesma álgebra de Boole usada como
espaço de características.

São mostrados alguns resultados experimentais para uma comparação inicial deste
enfoque.

Todos são benvindos

--
Marcelo Finger
Departamento de Ciencia da Computacao
Instituto de Matematica e Estatistica | home page:
Universidade de Sao Paulo | www.ime.usp.br/~mfinger
Rua do Matao, 1010 | Tel: +55 11 3091 6310, 3091 6135
05508-090 Sao Paulo, SP Brazil | Fax: +55 11 3091 6134, 3814 4135

sexta-feira, 19 de setembro de 2008

A Conferência KR 2008 (Knowledge Representation) - Seminário LIAMF dia 22/09




-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: A Conferência KR 2008 (Knowledge Representation)
Palestrante:  Renata Wasssermann e Leliane Barros

Resumo:
A Conferência KR é o maior evento internacional da área de representação de
conhecimento, e a Renata e Leliane estiveram presentes a edição de 2008 na
Austrália e vão contar o que viram por lá, quais os assuntos que estão na moda,
quais os resultados mais notáveis e como seus trabalhos foram recebidos.

Todos são benvindos.

--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





Seminário LIAMF 15/09/2008

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Using Abduction to Compute Efficient Proofs
Palestrante:  Marcelo Finger

Data:   15/09/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:
--------------

 The aim of this work is to present a solution to the problem
 of computing non-analytic cuts. Several algorithms are
 provided that compute efficient proofs with non-analytic
 cuts via extended abductive reasoning.

 Extended abductive reasoning computes an extra hypothesis
 to a statement whose validity is unknown, such that:

 -- The statement becomes provable with the addition
   of the extra hypothesis.
 -- The extra hypothesis is not trivial (in some precisely
   defined sense).
 -- If the statement was originally valid (which is not known a priory)
   then the addition of the extra hypothesis leads to a statement
   with a much simpler proof.

 Due to the last item, this is ***not exactly*** the usual abductive
 reasoning found in literature, for the latter requires the input
 to be invalid.

 The idea is that the input is a contextual database, containing
 background knowledge, plus a goal formula representing some fact
 or evidence that one wants to explain or prove, and we want to
 compute an hypothesis that explains the evidence in the presence
 of the background knowledge or that facilitates the proof of
 $G$ from $\Gamma$.

 This is a joint work with Marcello D'Agostina and Dov Gabbay.
--
 Marcelo Finger
 Departamento de Ciencia da Computacao
 Instituto de Matematica e Estatistica | home page:
 Universidade de Sao Paulo             |   www.ime.usp.br/~mfinger
 Rua do Matao, 1010                    | Tel: +55 11 3091 6310, 3091 6135
 05508-090    Sao Paulo, SP     Brazil | Fax: +55 11 3091 6134, 3814 4135





quinta-feira, 22 de novembro de 2007

Soluções aproximadas para um MDPIP fatorado

----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Soluções aproximadas para um MDPIP fatorado

Palestrante: Karina Valdivia Delgado

Data:  dia 26.11.07 às 14:00 hs

Local: Sala 252 - Bloco A - IME - USP


Resumo:

O tema principal desse seminário  está relacionado à área de planejamento sob incerteza da Inteligência Artificial (IA). Trabalhos recentes nessa área adotam modelos estocásticos, com soluções bem conhecidas. No entanto, modelos com informação incompleta são de grande interesse na área de IA por serem mais aplicáveis em problemas práticos. Nesse seminário, fazemos uma breve revisão dos principais conceitos da área de processos Markovianos de Decisão (MDPs) e apresentamos um algoritmo aproximado baseado em programação linear, para resolver MDPs fatorados (isto é, uma representação compacta para MDPs que envolvam um grande número de estados). Em seguida, definimos um MDP impreciso (MDPIP), isto é, um MDP em que as distribuições de probabilidade sob as transições de estado não são completamente conhecidas. O objetivo desse seminário é propor diferentes soluções aproximadas para um MDPIP fatorado, uma vez que não são conhecidas soluções na literatura para esse problema.

domingo, 11 de novembro de 2007

Desktops Semânticos

----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

Título: Desktops semânticos

Palestrante: Rodrigo Rage Ferro

Data:  dia 12.11.07 às 14:00 hs

Local: Sala 252 - Bloco A - IME - USP


Resumo:
A quantidade crescente e a diversidade de dados armazenados em computadores fazem a organização e a localização da informação uma tarefa difícil. Usuários tentam por meio de uma estrutura de diretórios realizar a organização dos arquivos. Infelizmente, o sistema tradicional hierárquico de arquivos não está conseguindo mais atender de forma satisfatória este propósito. A tarefa de localizar então torna-se penosa, fazendo com que muitas vezes seja mais cômodo para o usuário usar ferramentas de busca na Web do que procurar o arquivo no seu próprio HD. Tentando integrar Web Semântica com aplicações de desktop, surge o chamado Semantic Desktop.

Entre os objetivos do desktop semântico está vincular o arquivo com a informação contextual obtida no momento em que ele é usado/salvo por meio de metadados em RDF. Assim, quando o usuário busca por um arquivo espera-se, que mais do que palavras-chave, uma semântica seja explorada de forma a restringir e tornar mais eficiente o processo de busca.

Nessa apresentação, será abordado sobre Semantic Desktop: objetivos, arquitetura típica e projetos existentes, além de como web semântica pode auxiliar nesse processo de busca mais eficiente.

Todos são bem-vindos!