The uniform measure of simple regular sets of infinite trees

DOI10.1016/J.IC.2020.104595MaRDI QIDQ2029602zbMATH OpenOpenAlexFDO

Authors Marcin Przybyłko, Michał Skrzypczak

Publication date 3 June 2021

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.11576

zbMATH Keywords

first-order logicinfinite treesrandom treeuniform measure

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Applications of branching processes (60J85) Formal languages and automata (68Q45) Stochastic games, stochastic differential games (91A15)

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.

Recommendations

• On the problem of computing the probability of regular sets of trees
• Measure properties of regular sets of trees
• Measure Properties of Game Tree Languages
• scientific article; zbMATH DE number 176157
• The Cantor-Bendixson analysis of finite trees

Cites work

• A survey of stochastic -regular games
• An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
• Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
• Conjunctive query containment over trees
• Deciding low levels of tree-automata hierarchy
• scientific article; zbMATH DE number 4179422 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 1236373 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 194935 (Why is no real title available?)
• scientific article; zbMATH DE number 7362735 (Why is no real title available?)
• scientific article; zbMATH DE number 2206362 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• scientific article; zbMATH DE number 3078993 (Why is no real title available?)
• Measure properties of regular sets of trees
• Model Checking Stochastic Branching Processes
• Model Theory Makes Formulas Large
• On the complexity of branching games with regular conditions
• On the problem of computing the probability of regular sets of trees
• Probabilistic databases
• Probabilistic modal \(\mu\)-calculus with independent product
• Provenance circuits for trees and treelike instances
• Recursive Markov decision processes and recursive stochastic games
• The complexity of elementary algebra and geometry
• Tree-Walking Automata

Cited in

(6)

• Trees, ultrametric spaces and bases with uniform structure
• Measure properties of regular sets of trees
• The Cantor-Bendixson analysis of finite trees
• On computing the measures of first-order definable sets of trees
• On the problem of computing the probability of regular sets of trees
• Full-splitting Miller trees and infinitely often equal reals

This page was built for publication: The uniform measure of simple regular sets of infinite trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029602)