Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable

Tytuł:
Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
Autorzy:
Grimson, R.
Kuijpers, B.
Data publikacji:
2014
Słowa kluczowe:
second-order logic
equivalence of formulas
containment
(un)decidability results
predicates
Język:
angielski
Dostawca treści:
BazTech
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
We consider the Σ10 -fragment of second-order logic over the vocabulary [+;x; 0; 1; <; S1; …..., Sk], interpreted over the reals, where the predicate symbols Si are interpreted as semi algebraic sets. We show that, in this context, satisfiability of formulas is decidable for the first-order THERE EXISTS-quantifier fragment and undecidable for the THERE EXISTS*FOR ALL- and FOR ALL*-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies