Let be two elements with atoms. The pair satisfies the following universal property: supports both and , and if is another element with this property, then supports .
We demonstrate the existence of an element denoted , with a dual property: is supported both by and by , and if is another element with this property, then is supported by . The construction does not require any assumptions on the symmetry.
There are several decision problems for certain computation models with atoms that are decidable when atoms admit certain well quasi order (WQO), and undecidable otherwise. We recall the problems and formulate few questions related to WQOs.
Continue reading
Again, a question closely related to a characterization of standard atoms (not to be confused with standard alphabets:). The question is a refinement of a question posted in Automorphisms vs color-preserving automorphisms in Fraisse classes, which has been answered negatively (see the recent post The colored open question closed).
In Automata theory in nominal sets (Thm. 9.3), we provided a necessary and sufficient criterion for the existence of least finite supports for arbitrary atoms. It was not clear whether the criterion could be significantly simplified for Fraisse atoms. I show that it cannot be made as simple as we originally conjectured.
This is a straightforward generalization of the classical Pumping Lemma for regular languages. It was proved independently by the Warsaw team and by Filippo Bonchi, Daniela Petrisan and Alexandra Silva.
This post discusses equivalence of:
1. existence of the least supports
2. representation theorem