Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: infinite graphs

Sortuj według:

Ogranicz wyniki do:

On the Erdős–Dushnik–Miller theorem without AC

Banerjee Amitayu, Gopaulsingh Alexa

Bulletin of the Polish Academy of Sciences. Mathematics

2023

Vol. 71, no 1

1--21

In ZFA (Zermelo–Fraenkel set theory with the Axiom of Extensionality weakened to allow the existence of atoms), we prove that the strength of the proposition EDM (“If G = (VG,EG) is a graph such that VG is uncountable, then for every coloring f : [VG]2 → {0, 1} either there is an uncountable set monochromatic in color 0, or there is a countably infinite set monochromatic in color 1”) is strictly between DCN1 (where DCN1 is Dependent Choices for N1, a weak choice form stronger than Dependent Choices (DC)) and Kurepa’s principle (“Any partially ordered set such that all of its antichains are finite and all of its chains are countable is countable”). Among other new results, we study the relations of EDM to BPI (Boolean Prime Ideal Theorem), RT (Ramsey’s theorem), De Bruijn–Erdős’ theorem for n-colorings, König’s lemma and several other weak choice forms. Moreover, we answer a part of a question raised by Lajos Soukup.

Thue specifications, infinite graphs and synchronized product

Payet E.

Fundamenta Informaticae

2000

Vol. 44, Nr 3

265-290

This paper presents some formal verification-oriented results about the class of graphs associated with Thue specifications. It is shown that this class is closed, up to isomorphism, under synchronized product. It is also established that every rational graph with no edge labeled by the empty word is isomorphic to the graph of a Thue specification. A consequence of this result is that the first-order theory of the graphs of Thue specifications is undecidable. Connections between graphs of Thue specifications and those of Turing machines are finally investigated. The main result is that the graph of each Thue specification is observationally equivalent to that of a Turing machine but the reverse does not hold.

Thue specifications and their monadic second-order properties

Knapik T., Calbrix H.

Fundamenta Informaticae

1999

Vol. 39, Nr 3

305-325

This paper introduces oriented Thue specifications and their models which are simple directed edge-labeled graphs. The monadic second-order theory of these models is investigated and shown decidable for the class of suffix-bounded rational oriented Thue specifications. In addition, a characterization of prefix-closed context-free languages is given in terms of oriented Thue specifications.