O teorema de Immerman-Vardi afirma que PTIME (ou P) é precisamente a classe de idiomas que pode ser descrita por uma frase da Lógica de Primeira Ordem, juntamente com um operador de ponto fixo, sobre a classe de estruturas ordenadas. O operador de ponto fixo pode ser o ponto menos fixo (como...
É possível testar algoritmicamente se um número computável é racional ou inteiro? Em outras palavras, seria possível para uma biblioteca que implementa números computáveis fornecer as funções isIntegerou isRational? Suponho que isso não seja possível e que isso esteja de alguma forma relacionado...
Na teoria dos autômatos (autômatos finitos, autômatos de empilhamento, ...) e na complexidade, existe a noção de "ambiguidade". Um autômato é ambíguo se houver uma palavra com pelo menos duas execuções de aceitação distintas. Uma máquina é ambígua se, para cada palavra aceita pela máquina, houver...
Contexto: relações entre lógica e autômatos O Teorema de Büchi afirma que a lógica monádica de segunda ordem sobre seqüências de caracteres (MSO) captura a classe de linguagens regulares. A prova realmente mostra que o MSO existencial ( ou EMSO ) sobre cadeias de caracteres é suficiente para...
O problema de manutenção de pedidos (ou "manutenção de pedidos em uma lista") é dar suporte às operações: singleton: cria uma lista com um item, retorna um ponteiro para ele insertAfter: dado um ponteiro para um item, insere um novo item depois dele, retornando um ponteiro para o novo...
Eu sei que a pergunta "uma fórmula de primeira ordem tem um modelo" é indecidível em geral.ϕϕ\phi Alguém poderia me dar um link ou um livro que dê a resposta para modelos finitos. Se eu tiver uma fórmula de primeira ordem , é decidível se ϕ possui um modelo finito? Tenho certeza de que a pergunta...
Parece que em linguagens de consulta populares para bancos de dados relacionais, é possível criar consultas que exigirão muitos recursos para serem respondidas. Na prática, os administradores de banco de dados gerenciam isso limitando a quantidade de memória por consulta e verificando se há...
Minha pergunta é sobre teoria finita de modelos / complexidade descritiva, então significará "primeira ordem sobre palavras binárias finitas, usando os predicados Rs e um predicado unário P verdadeiro na posição do 1 na palavra".FO(R)FO(R)FO(R) Gostaria de saber, existe alguma caracterização de...
Para entender melhor um artigo, estou tentando entender brevemente a lógica do ponto menos fixo. Existem alguns pontos em que estou preso. Se é um gráfico eG=(V,E)G=(V,E)G = (V,E) Φ(P) = { ( a , b )∣G⊨E( a ,b)∨P( a , b )∨∃z(E(a,z)∧P(z, b ) ) }Φ(P)={(uma,b)∣G⊨E(uma,b)∨P(uma,b)∨∃z(E(uma,z)∧P(z,b))}...
Não se acredita que seja o seguinte: L ⊆ L - uniforme N C1L⊆L−uniform NC1\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1 Você pode me ajudar a ver onde o argumento termina? O problema de acessibilidade direcionada está completo para . Argumento que está em -uniforme .L N C...
É bem conhecido na teoria dos modelos finitos que, sem uma ordem na entrada, a expressividade é muito limitada. Por exemplo, sabe-se que é igual a PSPACE , e (sem nenhuma ordem na entrada) é apenas relacional para PSPACE , uma noção definida por Abiteboul e Vianu quando provaram seu teorema: iff ....