Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Fundamenta Informaticae

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: word problem

Sortuj według:

Ogranicz wyniki do:

Residuated Algebraic Structures in the Vicinity of Pre-rough Algebra and Decidability

Lin Zhe, Chakraborty Mihir Kumar, Ma Minghui

Fundamenta Informaticae

2021

Vol. 179, nr 3

239--274

Varieties of topological quasi-Boolean algebras in the vicinity of pre-rough algebras [28, 29] are expanded to residuated algebraic structures by introducing a new implication operation and its residual in these structures. Sequent calculi for some classes of residuated algebraic structures are established. These sequent calculi have the strong finite model property which yields the decidability of the word problem for corresponding classes of algebraic structures.

One Henkin Quantifier in the Empty Vocabulary Suffices for Undecidability

Zdanowski Konrad

Fundamenta Informaticae

2019

Vol. 164, nr 4

375--386

We prove that there are single Henkin quantifiers such that first order logic augmented by one of these quantifiers is undecidable in the empty vocabulary. We estimate the size of such quantifiers proving undecidability of Lø(H12) and Lø(E10).

Representation Theorems and Locality for Subsumption Testing and Interpolation in the Description Logics εL; εL+ and their Extensions with n-ary Roles and Numerical Domains

Sofronie-Stokkermans V.

Fundamenta Informaticae

2017

Vol. 156, nr 3/4

361--411

In this paper we show that subsumption problems in lightweight description logics (such as εL and εL+) can be expressed as uniform word problems in classes of semilattices with monotone operators. We use possibilities of efficient local reasoning in such classes of algebras, to obtain uniform PTIME decision procedures for CBox subsumption in εL, εL+ and extensions thereof. These locality considerations allow us to present a new family of (possibly many-sorted) logics which extend εL and εL+ with n-ary roles and/or numerical domains. As a by-product, this allows us to show that the algebraic models of εL and εL+ have ground interpolation and thus that εL, εL+, and their extensions studied in this paper have interpolation.

An Algebraic Characterization of the Halting Probability

Chaitin G.

Fundamenta Informaticae

2007

Vol. 79, nr 1-2

17-23

Using 1947 work of Post showing that the word problem for semigroups is unsolvable, we explicitly exhibit an algebraic characterization of the bits of the halting probability W. Our proof closely follows a 1978 formulation of Post's work by M. Davis. The proof is self-contained and not very complicated.