commit 83f4b5de7712cd02ee4f53979d071bddb2b9769f
parent a963b6c4fba9522a4b8e48cb18a7bacb212845bc
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 21 Feb 2025 11:35:27 +0100
commit with codex
Diffstat:
27 files changed, 218 insertions(+), 15 deletions(-)
diff --git a/automata_complementation b/automata_complementation
@@ -5,3 +5,5 @@
- hard also for [word_automaton_unambiguous]
Up: [complementation], [automata]
+
+Aliases: automaton complement, automaton complementation
diff --git a/automata_evaluation b/automata_evaluation
@@ -0,0 +1,12 @@
+# Automata evaluation
+
+Given an [automaton] A and a [word] w, determine if A accepts w
+
+- for [DFAs]: can be done in O(|w|), simply by following [transitions]
+- for [NFAs]: can be done in O(|w| |A|) by [state_set_simulation]
+ - [conditional_lower_bound] in [backurs2016which]
+ - reduction from [OV_conjecture]
+
+- [automata_evaluation_practice]
+
+Up: [automata_problems]
diff --git a/automata_weighted b/automata_weighted
@@ -12,6 +12,8 @@ given a [word]:
- [sum] over possible [run]s
- [product] over [transitions] and [final_states] used
+Can be seen as multiplying [matrices] (one [matrix] for each letter), with a [vector] of [initial_weights] and [final_weights]
+
Schützenberger, 1961
- [automata_weighted_conjugacy]
diff --git a/certain_answers b/certain_answers
@@ -1,9 +1,11 @@
# Certain answers
-Given a [query] Q and [uncertain_data] D, a *certain answer* is a [query_answer] which is true on every [possible_world] of D. If Q is a [Boolean_query], we talk about the query being certain
+Given a [query] Q and [uncertain_data] D, a *certain answer* is a [query_answer] which is true on every [possible_world] of D. If Q is a [Boolean_query], we talk about the query being *certain*
- [gheerbrant2023querying]
Up: [uncertain_data]
Aliases: certain answer
+
+See also: [possible_answers]
diff --git a/downwards_closure_cfl_state_complexity b/downwards_closure_cfl_state_complexity
@@ -0,0 +1,9 @@
+# Downwards closure CFL state complexity
+
+We can construct [automata] recognizing the downwards closure of a [CFL]: cf [bachmeier2014finite].
+- As an [NFA], it can be done with an [exponential] set of [states], and there is also an [exponential] [lower_bound].
+- As a [DFA], it can be done with a [doubly_exponential] set of [states], and there is also a [doubly_exponential] [lower_bound]
+
+Up: [downwards_closure_state_complexity], [CFL]
+
+See also: [upwards_closure_cfl_state_complexity]
diff --git a/downwards_closure_state_complexity b/downwards_closure_state_complexity
@@ -0,0 +1,11 @@
+# Downwards closure state complexity
+
+- [karandikar2014state]: transforming a [DFA] to a [DFA] for the set of [subwords] has [exponential] [lower_bound] (not trivial)
+ - [lower_bound] on larger alphabet already in [okhotin2010state]
+- [downwards_closure_cfl_state_complexity]
+
+Up: [downwards_closure], [state_complexity]
+
+Aliases: downward closure state complexity
+
+See also: [upwards_closure_state_complexity]
diff --git a/final_weight b/final_weight
@@ -0,0 +1,9 @@
+# Final weight
+
+The [weight] in a [weighted_automaton] given to each [state] when ending a [run] at this state; in a non-weighted [automaton], the [final_states] would have weight 1 and the [nonfinal_states] would have weight 0
+
+Can be represented as a [vector] of weights
+
+Up: [automata_weighted]
+
+Aliases: final weights
diff --git a/inconsistency b/inconsistency
@@ -0,0 +1,5 @@
+# Inconsistency
+
+- [inconsistency_quantitative]
+
+Up: [uncertain_data]
diff --git a/inconsistency_quantitative b/inconsistency_quantitative
@@ -0,0 +1,13 @@
+# Inconsistency quantitative
+
+[Quantitative] measures of inconsistency ([constraint_violations]):
+
+- number of minimal inconsistent subsets
+- number of tuples that participate to a violation
+- minimal number of tuples to remove to satisfy the constraints
+ - see [database_repairs] and [subset_repairs]
+- number of maximal consistent subsets
+
+Up: [inconsistency]
+
+See also: [database_repairs]
diff --git a/initial_weight b/initial_weight
@@ -0,0 +1,9 @@
+# Initial weight
+
+The [weight] in a [weighted_automaton] given to each [state] when beginning a [run] at this state; in a non-weighted [automaton], the [initial_states] would have weight 1 and the others would have weight 0
+
+Can be represented as a [vector] of weights
+
+Up: [automata_weighted]
+
+Aliases: initial weights
diff --git a/lower_bounds b/lower_bounds
@@ -1,6 +1,7 @@
# Lower bounds
-[complexity_lower_bounds]
+- [complexity_lower_bounds]
+- [conditional_lower_bound]
Up: [computational_complexity]
diff --git a/network_reliability b/network_reliability
@@ -2,6 +2,7 @@
- [st_reliability]
- [network_reliability_fpras]
+- [all_terminal_network_reliability]
Up: [graph]
diff --git a/possible_answers b/possible_answers
@@ -0,0 +1,9 @@
+# Possible answers
+
+Given a [query] Q and [uncertain_data] D, a *possible answer* is a [query_answer] which is true on some [possible_world] of D.
+
+See also: [certain_answers]
+
+Up: [uncertain_data]
+
+Aliases: possible answer
diff --git a/pqe_ucq b/pqe_ucq
@@ -0,0 +1,11 @@
+# PQE for UCQ
+
+- [dichotomy]: [dalvi2012dichotomy]
+- new presentation: [kenig2020dichotomy]
+
+The complexity in the [query] of the [meta_dichotomy] criterion is open
+ - cf [amarilli2020dichotomy] which says so explicitly
+
+Up: [pqe] for [union_of_conjunctive_queries]
+
+See also: [pqe_unsafe]
diff --git a/probabilistic_database_model b/probabilistic_database_model
@@ -1,8 +1,10 @@
# Probabilistic database model
-- [tuple_independent_database]
-- [block_independent_disjoint] [database]
+- [tuple_independent_database] (TID)
+- [block_independent_disjoint] [database] (BID)
- [pc_table]
- also: [probabilistic_xml]
+Relevant source: "Uncertain Data Models", [Encyclopedia_of_Database_Systems], page numbered 4297
+
Up: [probabilistic_databases], [database_model]
diff --git a/probabilistic_database_neighboring_fields b/probabilistic_database_neighboring_fields
@@ -0,0 +1,10 @@
+# Probabilistic database neighboring fields
+
+- [graphical_models]
+- [knowledge_compilation]
+- other [uncertain_data] / [incomplete_data]
+ - recent survey on incomplete data: [console2020coping]
+- [network_reliability] problem ([all_terminal_network_reliability], etc.)
+- [shapley_value] computation or [query_resilience] ([reshef2020impact]) and other such measures
+
+Up: [probabilistic_databases]
diff --git a/probabilistic_databases b/probabilistic_databases
@@ -0,0 +1,30 @@
+# Probabilistic databases
+
+- [probabilistic_database_model],
+- [probabilistic_database_neighboring_fields]
+- [provenance] / [lineage]
+ - [semirings]
+ - tractable [circuit] representations
+ - lower bounds from [amarilli2019connecting]
+- [probabilistic_query_evaluation]
+ - [self-join-free_CQs]
+ - [UCQs]: [pqe_ucq] [dalvi2012dichotomy]
+ - [q9_conjecture]: [monet2020solving]
+ - [recursive_queries]: [amarilli2020dichotomy]
+- [pqe_treelike]
+ - [pqe_MSO], via [provenance_circuits]
+ - historical motivation: [probabilistic_XML]
+ - [lower_bounds] in [amarilli2016tractable]
+- [pqe_combined]
+- [pqe_unweighted]
+ - [kenig2020dichotomy]
+ - [amarilli2022uniform]
+ - [symmetric_model_counting]
+- [pqe_new_directions]
+
+- [pqe_applications]
+- [probabilistic_databases_practice]
+
+See also: [relational_algebra], [relational_calculus]
+
+Up: [database_theory]
diff --git a/quantitative b/quantitative
@@ -0,0 +1,5 @@
+# Quantitative
+
+- [quantitative_mso]
+
+Up: [logic]
diff --git a/representation_system b/representation_system
@@ -0,0 +1,11 @@
+# Representation system
+
+A way to represent *uncertain data*: you have [representations], and each representation is a concise representation of a set of [possible_worlds]. For instance:
+
+- [NULLs]
+- [v_tables]
+- [c_tables]
+
+Presented in [imielinski1984incomplete]
+
+Up: [uncertain_data]
diff --git a/semiring_idempotent b/semiring_idempotent
@@ -1,10 +1,7 @@
# Idempotent semiring
-A [semiring] satisfying the equation a+a = a for every a, i.e., [additively_idempotent]
-
-Not the case of all [semirings], e.g., not the [natural_numbers]
-
-Also [semiring_multiplicative_idempotent]
+- [semiring_additively_idempotent]
+- [semiring_multiplicative_idempotent]
Up: [semiring], [idempotent]
diff --git a/sjfcq b/sjfcq
@@ -6,4 +6,4 @@
Up: [conjunctive_query], [self_join]
-Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free
+Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs
diff --git a/state_complexity b/state_complexity
@@ -0,0 +1,13 @@
+# State complexity
+
+https://en.wikipedia.org/wiki/State_complexity
+
+- For [automaton_complement] of an [automaton] with n [states] on a binary alphabet you may need 2^n states
+- [minimization] / [canonical_automata]
+ - for [DFAs]: can be done in [PTIME]
+ - (quibble about whether it should be [complete_automata] or not)
+ - for [NFAs]: [pspace]-complete
+- [upward_closure_state_complexity]
+- [downward_closure_state_complexity]
+
+Up: [automata]
diff --git a/tdta b/tdta
@@ -0,0 +1,21 @@
+# tDTA
+
+Defined by a set of [states], an [initial_state], a set of [final_states], and a [transition_function] describing the state of the children of each tree node as a function of the state of the node and the label of the node.
+
+[acceptance_condition]: all [leaves] are labeled with a [final_state]
+
+The [tree_languages] that can be recognized by tDTAs are a proper subset of the [regular_tree_languages]
+- In particular, if such an automaton accepts f(a,b) and f(a',b') then they accept f(a,b') and f(a',b)
+
+To understand the [expressive_power] of such [automata]: they only depend on the [word_language] of the [paths] from the [root] to the [leaves] in the input [tree]
+- A [tree] t is accepted by a tDTA A if and only if the set of root-to-leaf [paths] of t is included in the set of root-to-leaf paths of the [trees] accepted by A
+
+Membership to the class of languages recognized by tDTAs is [decidable]. Generalization: [Boolean_closure_tDTA]
+
+Generalization: [tDTA_set_acceptance]
+
+Up: [tree_automaton_top_down], [automata_deterministic]
+
+See also: [bDTA], [tNTA], [tUTA]
+
+Aliases: deterministic top-down tree automaton
diff --git a/tree_automaton b/tree_automaton
@@ -5,9 +5,7 @@ Defines [regular_tree_language]
## Types
- [tree_automaton_bottom_up]
-- [tree_automaton_top_down]:
- - [automata_deterministic] leads to a weaker class of languages
- - [unambiguous]: is the same as unambiguous bottom-up (the unambiguity condition is symmetric)
+- [tree_automaton_top_down]
## Variants
diff --git a/tree_automaton_bottom_up b/tree_automaton_bottom_up
@@ -2,7 +2,11 @@
- [initialization_function] / [initialization_relation]
- [transition_function] / [transition_relation]
-- can be [automaton_deterministic] ([bDTA]) or [automaton_nondeterministic] ([bNTA])
-- can be [automaton_unambiguous] ([bUTA])
+
+types:
+
+- [automaton_deterministic]: [bDTA]
+- [automaton_unambiguous]: [bUTA]
+- [automaton_nondeterministic]: [bNTA]
Up: [tree_automaton], [bottom_up]
diff --git a/tree_automaton_top_down b/tree_automaton_top_down
@@ -0,0 +1,12 @@
+# Tree automaton top down
+
+- [automata_deterministic]: [tDTA]
+ - leads to a weaker class of languages
+ - [Boolean_closure]: [Boolean_closure_tDTA]
+- [unambiguous]: [tUTA]
+ - has same [expressiveness] as [bUTA]
+ - (the unambiguity condition is symmetric)
+- [nondeterministic]: [tNTA]
+ - has same [expressiveness] as [bNTA]
+
+Up: [tree_automaton]
diff --git a/uncertain_data b/uncertain_data
@@ -2,5 +2,9 @@
- [inconsistency]
- [certain_answers]
+- [possible_answers]
+- [representation_system]
+- [consistent_query_answering]
+- [open_world_query_answering]
Up: [probabilistic_databases]
