On computing the measures of first-order definable sets of trees

MaRDI QIDQ3384891zbMATH OpenFDO

Authors Marcin Przybyłko

Publication date 17 December 2021

Full work available at URL https://arxiv.org/abs/1809.03104, http://eptcs.web.cse.unsw.edu.au/paper.cgi?GandALF18.15

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• The uniform measure of simple regular sets of infinite trees
• On the problem of computing the probability of regular sets of trees
• STACS 2005
• Measure properties of regular sets of trees
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)

Cites work

• 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 3078993 (Why is no real title available?)
• 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
• Measure Properties of Game Tree Languages
• Model Checking Stochastic Branching Processes
• 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

Cited in

(8)

• Frame Definability for Classes of Trees in the μ-calculus
• First-Order Definability of Trees and Sparse Random Graphs
• scientific article; zbMATH DE number 3894467 (Why is no real title available?)
• First-order properties of trees, star-free expressions, and aperiodicity
• scientific article; zbMATH DE number 6000848 (Why is no real title available?)
• First-order theories of bounded trees
• The Computable Dimension of I-Trees of Infinite Height
• scientific article; zbMATH DE number 4051033 (Why is no real title available?)

This page was built for publication: On computing the measures of first-order definable sets of trees

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