Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: spectrum problem

Sortuj według:

Ogranicz wyniki do:

Axiomatizing Rectangular Grids with no Extra Non-unary Relations

Kopczyński Eryk

Fundamenta Informaticae

2020

Vol. 176, nr 2

129--138

We construct a first-order formula φ such that all finite models of φ are non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set A ⊆ ℕ is a spectrum of a formula which has only planar models if numbers n ∈ A can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time t (n) and space s (n), where t (n)s (n) ≤ n and t (n), s (n) = Ω(log(n)).

The spectrum problem for digraphs of order 4 and size 5

Bunge R. C., DeShong S, El-Zanati S. I., Fischer A., Roberts D. P., Teng L.

Opuscula Mathematica

2018

Vol. 38, no. 1

15--30

The paw graph consists of a triangle with a pendant edge attached to one of the three vertices. We obtain a multigraph by adding exactly one repeated edge to the paw. Now, let D be a directed graph obtained by orientating the edges of that multigraph. For 12 of the 18 possibilities for D, we establish necessary and sufficient conditions on n for the existence of a [formula] design. Partial results are given for the remaining 6 possibilities for D.