Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Shelah-Stupp’s Iteration and Muchnik’s Iteration

Caucal D., Knapik T.

Fundamenta Informaticae

2018

Vol. 159, nr 4

327--359

In the early seventies, Shelah proposed a model-theoretic construction, nowadays called “iteration”. This construction is an infinite replication in a tree-like manner where every vertex possesses its own copy of the original structure. Stupp proved that the decidability of the monadic second-order (MSO) theory is transferred from the original structure onto the iterated one. In its extended version discovered by Muchnik and introduced by Semenov, the iteration became popular in computer science logic thanks to a paper by Walukiewicz. Compared to the basic iteration, Muchnik’s iteration has an additional unary predicate which, in every copy, marks the vertex that is the clone of the possessor of the copy. A widely spread belief that this extension is crucial is formally confirmed in the paper. Two hierarchies of relational structures generated from finite structures by MSO interpretations and either Shelah-Stupp’s iteration or Muchnik’s iteration are compared. It turns out that the two hierarchies coincide at level 1. Every level of the latter hierarchy is closed under Shelah-Stupp’s interation. In particular, the former hierarchy collapses at level 1.

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.