Property testing for bounded degree databases
From MaRDI portal
Recommendations
Cites work
- \(\omega\)-regular languages are testable with a constant number of queries
- Elements of finite model theory.
- Every property of hyperfinite graphs is testable
- Fast integer programming in fixed dimension
- Graph structure and monadic second-order logic. A language-theoretic approach
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 3266604 (Why is no real title available?)
- Integer Programming with a Fixed Number of Variables
- Notions of locality and their logical characterizations over finite models
- On Context-Free Languages
- On spectra of sentences of monadic second order logic with counting
- Property testing in bounded degree graphs
- Property testing of regular tree languages
- Realizability and uniqueness in graphs
- Regular languages are testable with a constant number of queries
- Relating two property testing models for bounded degree directed graphs
- Testing properties of directed graphs: acyclicity and connectivity*
Cited in
(8)- Testing unboundedness of database schemes and functional dependencies
- On the tree-width of even-hole-free graphs
- Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
- An approach for testing the primeness of attributes in relational schemas
- Faster Property Testers in a Variation of the Bounded Degree Model
- On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
- Faster property testers in a variation of the bounded degree model
- Learning concepts definable in first-order logic with counting
This page was built for publication: Property testing for bounded degree databases
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304100)
