@article{PRZYBYLKO2021104595,
    Abstract = {We consider the problem of computing the measure of a regular set of infinite binary trees. While the general case remains unsolved, we show that the measure of a language can be computed when the set is given in one of the following three formalisms: a first-order formula with no descendant relation; a Boolean combination of conjunctive queries (with descendant relation); or by a non-deterministic safety tree automaton. Additionally, in the first two cases the measure of the set is always rational, while in the third it is an algebraic number. Moreover, we provide an example of a first-order formula that uses descendant relation and defines a language of infinite trees having an irrational (but algebraic) measure.},
    Author = {Przyby{\l}ko, Marcin and Skrzypczak, Micha{\l}},
    File = {The uniform measure of simple regular sets of infinite trees - 1-s2.0-S0890540120300833-main.pdf},
    ISSN = {0890-5401},
    Journal = {Information and Computation},
    Keywords = {Infinite trees, Uniform measure, Random tree, First-order logic},
    Note = {Special Issue on Ninth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2018)},
    Pages = {104595},
    Title = {The uniform measure of simple regular sets of infinite trees},
    URL = {https://www.sciencedirect.com/science/article/pii/S0890540120300833},
    Volume = {278},
    Year = {2021},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0890540120300833},
    bdsk-url-2 = {https://doi.org/10.1016/j.ic.2020.104595},
    date-added = {2021-06-25 16:27:12 +0200},
    date-modified = {2021-06-25 16:27:12 +0200},
    doi = {10.1016/j.ic.2020.104595}
}

@article{PRZYBYLKO2021104595, Abstract = {We consider the problem of computing the measure of a regular set of infinite binary trees. While the general case remains unsolved, we show that the measure of a language can be computed when the set is given in one of the following three formalisms: a first-order formula with no descendant relation; a Boolean combination of conjunctive queries (with descendant relation); or by a non-deterministic safety tree automaton. Additionally, in the first two cases the measure of the set is always rational, while in the third it is an algebraic number. Moreover, we provide an example of a first-order formula that uses descendant relation and defines a language of infinite trees having an irrational (but algebraic) measure.}, Author = {Przyby{\l}ko, Marcin and Skrzypczak, Micha{\l}}, File = {The uniform measure of simple regular sets of infinite trees - 1-s2.0-S0890540120300833-main.pdf}, ISSN = {0890-5401}, Journal = {Information and Computation}, Keywords = {Infinite trees, Uniform measure, Random tree, First-order logic}, Note = {Special Issue on Ninth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2018)}, Pages = {104595}, Title = {The uniform measure of simple regular sets of infinite trees}, URL = {https://www.sciencedirect.com/science/article/pii/S0890540120300833}, Volume = {278}, Year = {2021}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0890540120300833}, bdsk-url-2 = {https://doi.org/10.1016/j.ic.2020.104595}, date-added = {2021-06-25 16:27:12 +0200}, date-modified = {2021-06-25 16:27:12 +0200}, doi = {10.1016/j.ic.2020.104595} }