Displaying 1241 – 1260 of 8549

Showing per page

Atomic compactness for reflexive graphs

Christian Delhommé (1999)

Fundamenta Mathematicae

A first order structure with universe M is atomic compact if every system of atomic formulas with parameters in M is satisfiable in provided each of its finite subsystems is. We consider atomic compactness for the class of reflexive (symmetric) graphs. In particular, we investigate the extent to which “sparse” graphs (i.e. graphs with “few” vertices of “high” degree) are compact with respect to systems of atomic formulas with “few” unknowns, on the one hand, and are pure restrictions of their...

Atoms and partial orders of infinite languages

Werner Kuich, N. W. Sauer (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under . This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

Atoms and partial orders of infinite languages

Werner Kuich, N. W. Sauer (2010)

RAIRO - Theoretical Informatics and Applications

We determine minimal elements, i.e., atoms, in certain partial orders of factor closed languages under ⊆. This is in analogy to structural Ramsey theory which determines minimal structures in partial orders under embedding.

Automata-based representations for infinite graphs

Salvatore La Torre, Margherita Napoli (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and the last...

Automata-based Representations for Infinite Graphs

Salvatore La Torre, Margherita Napoli (2010)

RAIRO - Theoretical Informatics and Applications

New compact representations of infinite graphs are investigated. Finite automata are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach consists of a general framework where vertices are represented by a regular prefix-free language and edges are represented by a regular language and a function over tuples. We consider three different functions over tuples: given a tuple the first function returns its first difference, the second one returns its suffix and...

Currently displaying 1241 – 1260 of 8549