commit 2f73af16ab4a6d1fb82fa898098db66df1aa4bb0 parent 7623417f24b32a46afd7d315d40ff706082e6c2e Author: Antoine Amarilli <a3nm@a3nm.net> Date: Mon, 17 Feb 2025 17:54:31 +0100 commit with codex Diffstat:
75 files changed, 439 insertions(+), 47 deletions(-)
diff --git a/absent_factor b/absent_factor @@ -0,0 +1,9 @@ +# Absent factor + +A [word] u is an *absent factor* of a [word] v if u does not occur as a [factor] of v + +Mentioned in [kosche2021absent] / [kosche2023absent] + +Up: [factor] + +See also: [absent_subsequence] diff --git a/absent_subsequence b/absent_subsequence @@ -0,0 +1,12 @@ +# Absent subsequence + +A [word] u is an *absent subsequence* of a [word] v if u does not occur as a [subsequence] of v + +Defined in [kosche2021absent] / [kosche2023absent], along with: + +- [minimal_absent_subsequence]: an absent subsequence where every strict [subsequence] is not absent +- [shortest_absent_subsequence]: an absent subsequence whose [length] is [minimal] + +Up: [subsequence] + +See also: [absent_factor] diff --git a/algebra b/algebra @@ -5,5 +5,6 @@ - [matrix] - ... - [vector_space] +- [algebra_basic_definitions] Up: [mathematics] diff --git a/all_pairs_shortest_path b/all_pairs_shortest_path @@ -23,7 +23,7 @@ connection between APSP and [distance_product] ([matrix_multiplication] in [semi Approximation: [all_pairs_shortest_path_approximate] -Beware: APSP can also mean "All pairs suffix prefix", cf [gusfield1992efficient], [zuba2024approximate] +Beware: APSP can also mean [All_pairs_suffix_prefix] Up: [shortest_path], [fine_grained_complexity_problems] diff --git a/apsp_hypothesis b/apsp_hypothesis @@ -5,7 +5,7 @@ - equivalent to [negative_triangle] - you can use [all_pairs_shortest_path] to compute [negative_triangle] - other direction more involved -- equivalent to [mpp_minimum] (find if the minimum diagonal entry of the min-plus product of three matrices A B C is <0) +- equivalent to [mpp_minimum] The equivalences to [all_pairs_shortest_path] and [mpp_minimum] are from [williams2018subcubic] diff --git a/automata_concepts b/automata_concepts @@ -3,6 +3,7 @@ - [state] - [initial_state] - [final_state] + - [nonfinal_state] - [sink_state] - [transient_state] - [transition] diff --git a/automata_weighted b/automata_weighted @@ -1,14 +1,18 @@ # Automata weighted -[automata] with [weight]s on [transition]s and on [final_state]s +[automata] with [weights] on [transitions] and on [final_states] and on [initial_states] -associates each [word] to an [integer] +associates each [word] to an [integer], or to a value in a [semiring] + +- [initial_weight] +- [final_weight] +- weight for every [transition] given a [word]: - [sum] over possible [run]s -- [product] over [transition]s and [final_state]s used +- [product] over [transitions] and [final_states] used -can be done in [semiring] +Schützenberger, 1961 Up: [automata] diff --git a/boolean_formula b/boolean_formula @@ -8,6 +8,7 @@ An [expression] which represents a [boolean_function], built from [literals] usi - [clause] - [term] - [literal] +- [Boolean_formulas_positive] Up: [representation] of [boolean_function] diff --git a/boolean_formulas_positive b/boolean_formulas_positive @@ -0,0 +1,7 @@ +# Boolean formulas positive + +A [Boolean_formula] which is [positive], i.e., does not use [negation] + +Up: [boolean_formula] + +Aliases: positive Boolean formula, positive Boolean formulas diff --git a/boolean_semiring b/boolean_semiring @@ -4,3 +4,5 @@ - it is a two-element [semiring] Up: [semiring] + +See also: [boolean] diff --git a/complexity b/complexity @@ -8,3 +8,5 @@ Up: [theoretical_computer_science] See also: [complexity_as_a_service], [complexity_zoo] + +Aliases: complexity theory diff --git a/compression_string b/compression_string @@ -6,3 +6,5 @@ - [substring_complexity] Up: [compression], [string] + +Aliases: compressed string, compressed strings diff --git a/computer_algebra b/computer_algebra @@ -2,5 +2,11 @@ - [grobner_basis], seems useful to solve [polynomial_equation] - matrixcalculus.org, calculs matriciels (différentiation etc) +- https://chadnauseam.com/coding/random/calculator-app on computer algebra for a calculator app: + - [bignum] + - [rationals] + - [algebraic_numbers] + - approximation of [reals] + - an approximate [equality_test] on expressions involving some reals Up: [mathematics] diff --git a/conjunctive_query_diversity b/conjunctive_query_diversity @@ -1,6 +1,8 @@ # Conjunctive query diversity - [merkl2023diversity] +- [arenas2024towards] + - uses [ultrametrics] Up: [diversity] of [conjunctive_query] diff --git a/context_free_grammar_linear b/context_free_grammar_linear @@ -6,4 +6,4 @@ Testing [language_emptiness] of [intersection] is already [undecidable] by reduc Up: [context_free_grammar] -Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars +Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars, linear CFG, linear CFGs diff --git a/crpq b/crpq @@ -5,7 +5,7 @@ - [rpq] - [conjunctive_query] -Generalization: [conjunctive_context_free_path_query] +[Generalization]: [conjunctive_context_free_path_query] - [crpq_containment] diff --git a/dagstuhl_semirings_val b/dagstuhl_semirings_val @@ -0,0 +1,24 @@ +# Dagstuhl semirings val + +by [val_tannen] about [semiring_provenance] + +shared an office with [Erich_Graedel] + +Mentions [Peter_Buneman] + +The [Orchestra] system for groups of scientists +- [Schema_mappings] +- when a database is updated, propagate the updates... + +[provenance_tracking] + +you have [provenance_tokens] X, and then Prov(X) is the set of [provenance_expressions] over the [provenance_tokens] +- features [product] for [conjunction] and [sum] for [disjunction] +- annotations 0 for "absent" and 1 for "untracked" + +Use [K_relations] for K = Prov(X) + +- [k_interpretation] +- [provenance_logic] + +Up: [dagstuhl_semirings_talks] diff --git a/density_function b/density_function @@ -17,3 +17,5 @@ computing its regime on [context_free_languages]: [gawrychowski2010finding] Up: [automata] See also: [universality_automata], [sharp_automaton], [slice], [degree_of_ambiguity], [growth_rate_analysis] + +Aliases: density functions diff --git a/diameter b/diameter @@ -4,6 +4,8 @@ Definition : in a [graph], the longest distance of a [shortest_path] - [incremental_maintenance_diameter] +Diameter of [random_graphs]: [addarioberry2020diameter] + Up: [graph_radius_diameter] See also: [girth], [graph_coloring_diameter] diff --git a/dioid b/dioid @@ -1,16 +0,0 @@ -# Dioid - -Semiring where 1 + 1 = 1 -- Implies [idempotence]: x + x = x -- [natural_order]: x <= y si x + y = y - -Also called an "idempotent semiring" - -Freely generated dioid over a set of variables, with no coefficients: [bool_x] -- infinite [omega_chain]: 1 < 1 + z < 1 + z + z^2 < ... - -strenghtening: [semiring_absorptive] - -Up: [semiring] - -See also: [kleene_algebra] diff --git a/downwards_closure b/downwards_closure @@ -6,6 +6,12 @@ For any [formal_language] L, the downwards closure is a [regular_language]: this The downwards closure is a [downwards_closed_language]: any [subsequence] of a [word] of the downwards closure is in the downwards closure +Given an [NFA], we can build in [linear_time] an [NFA] recognizing the upwards closure: cf [bachmeier2014finite] Lemma 8. +- this automaton is [weakly_acyclic_automaton] + +[downwards_closure_state_complexity] +- [downwards_closure_cfl_state_complexity] + See also: [language_downwards_closed], [upwards_closure] Up: [formal_language_operator], [closure_operation] on [subsequences] diff --git a/dpll b/dpll @@ -0,0 +1,21 @@ +# DPLL + +https://en.wikipedia.org/wiki/DPLL_algorithm + +[algorithm] for [satisfiability_boolean] of [CNF] + +- if there is an empty clause, return UNSAT +- if there are no clauses, return SAT with current assignment +- if there is a clause containing a single [literal], instantiate that literal ([unit_propagation]) +- if there is a [literal_pure] aka one that occurs with only one polarity, insantiate that literal +- otherwise, select a literal ([branching_rule]), and explore first one polarity, then another + +Can be modified for [sharp_SAT], but: + +- not possible to handle [literal_pure] in a special way +- must explore both values of the chosen [literal], not just one +- must count [free_variables] + +Up: [algorithm] for [satisfiability_boolean] + +See also: [CDCL] diff --git a/empty_word b/empty_word @@ -0,0 +1,5 @@ +# Empty word + +The [word] with no [letters], having [length] 0 + +Up: [word] diff --git a/factor b/factor @@ -3,6 +3,9 @@ Definition: [word] u is factor of [word] v if we have v = xuy for some [word]s x and y - [factor_universal] +- [absent_factor] + +If u is a factor of v, then v is an [extension] of u Up: [formal_language_theory] diff --git a/feferman_vaught_theorem b/feferman_vaught_theorem @@ -0,0 +1,11 @@ +# Feferman-Vaught theorem + +https://en.wikipedia.org/wiki/Feferman%E2%80%93Vaught_theorem + +[Theorem] in [model_theory] + +Within a certain [logic], relates the [theory] (the [set] of [satisfied] [formulas]) of a [direct_product] of [structures] to the [theory] of the individual [structures] + +A similar result exists for the [disjoint_union] of [structures]: [feferman_vaught_union] + +Up: [theorem], [logic] diff --git a/final_state b/final_state @@ -8,4 +8,4 @@ Up: [automata_concepts] Aliases: final states -See also: [nonfinal_state] +See also: [nonfinal_state], [initial_state] diff --git a/finite_model_theory b/finite_model_theory @@ -2,6 +2,6 @@ - [finite_controllability] -Up: [logic], [finite] +Up: [model_theory], [finite] See also: [Open_world_query_answering] diff --git a/function b/function @@ -20,6 +20,6 @@ Notions: Up: [mathematics] -See also: [functional_dependency] +See also: [functional_dependency], [function_symbol] Aliases: functions diff --git a/initial_state b/initial_state @@ -0,0 +1,9 @@ +# Initial state + +A [state] in an [automaton] in which a [run] can begin. A [DFA] has exactly one initial state, an [NFA] can have multiple initial states (but up to adding a superinitial state with [epsilon_transitions], and [eliminating_epsilon_transitions], it amounts to the same) + +Up: [automata_concepts] + +Aliases: initial states + +See also: [final_state], [nonfinal_state] diff --git a/integers b/integers @@ -0,0 +1,7 @@ +# Integers + +The set \mathbb{Z} of [natural_numbers] or the [negative_numbers] (including [zero]) + +Up: [number] + +Aliases: integer diff --git a/language_upwards_closed b/language_upwards_closed @@ -4,6 +4,8 @@ A [formal_language] is *upwards closed* if any [subword] of the [formal_language The [language_complement] of an upwards closed [formal_language] is a [downwards_closed_language]. +Testing the [automaton_equivalence] of two [NFAs] recognizing downwards closed languages is [coNP_complete], cf [bachmeier2014finite] + Up: [regular_language_family] See also: [higmans_lemma], [upwards_closure], [language_factor_minimal], [language_downwards_closed] diff --git a/length b/length @@ -0,0 +1,7 @@ +# Length + +The number of [letters] of a [word] + +Generalization: [Parikh_image] + +Up: [word] diff --git a/locally_testable_language b/locally_testable_language @@ -13,7 +13,8 @@ Membership is decidable in [ptime] with algebraic characterization, cf [schutzen ## Generalizations - [locally_threshold_testable_language] where you can count infixes up to some threshold -- mTT+MOD dans place2013separating, where you can further count [modulo] a certain value +- mTT+MOD dans [place2013separating], where you can further count [modulo] a certain value +- [garcia2000right]: [locally_testable_language_right] and [locally_testable_language_left], which strictly generalize the locally testable languages See also: [piecewise_testable_language], [local_language], [suffix_testable_language], [prefix_testable_language] diff --git a/logic b/logic @@ -66,6 +66,7 @@ - [quantifier_rank] - [logical_implication] - [sentence] +- [function_symbol] Up: [mathematics], [theoretical_computer_science] diff --git a/mathematics b/mathematics @@ -21,6 +21,7 @@ - [disequality] - [symmetry] - [composition] +- [number] ## Fields diff --git a/mathematics_basic_concepts b/mathematics_basic_concepts @@ -16,6 +16,7 @@ - [ring] - [field] - [homomorphism] +- [sum], [product] - [distance] - [vector] - [number] diff --git a/matrix b/matrix @@ -39,3 +39,5 @@ - [tensor] Up: [mathematics] + +Aliases: matrices diff --git a/matrix_multiplication b/matrix_multiplication @@ -13,3 +13,5 @@ In specific [semirings]: Up: [multiplication] of [matrix] See also: [algorithm], [matrix_product] + +Aliases: matrix product diff --git a/maximum b/maximum @@ -6,3 +6,5 @@ the largest [element] of an [order] See also: [minimum] Up: [mathematics_basic_concepts] + +Aliases: max diff --git a/min_plus_product b/min_plus_product @@ -0,0 +1,7 @@ +# Min plus product + +The [matrix_product] but in the [tropical_semiring] + +See also: [mpp_minimum] + +Up: [operation] on [matrices] diff --git a/minimum b/minimum @@ -8,3 +8,5 @@ The smallest element of an [order] Up: [mathematics_basic_concepts] See also: [maximum] + +Aliases: min diff --git a/natural_number b/natural_number @@ -0,0 +1,9 @@ +# Natural number + +The set \mathbb{N} of natural numbers + +Up: [number] + +Aliases: natural numbers, NN + +See also: [integers], [negative_numbers] diff --git a/neutral_element b/neutral_element @@ -0,0 +1,11 @@ +# Neutral element + +For S a [set] and e an [element], if you have a [operation] on S, then e is a neutral element if for every x in S, you have xe = ex = x. + +If there is a neutral element, then there is exactly one. + +When you have a [semigroup], you can add a neutral element if necessary and you get a [monoid]. + +Up: [algebra_basic_definitions] + +See also: [annihilating_element] diff --git a/nonfinal_state b/nonfinal_state @@ -0,0 +1,9 @@ +# Nonfinal state + +A [state] in an [automaton] which is not a [final_state] + +Up: [automata_concepts] + +See also: [final_state], [initial_state] + +Aliases: nonfinal states diff --git a/number b/number @@ -3,6 +3,7 @@ - [natural_number] - [diophantine_equation] - [sum_of_powers] +- [integers] - [rational_number] - [real_number] - [complex_number] diff --git a/pattern_matching b/pattern_matching @@ -21,6 +21,7 @@ - [point_set_pattern_matching] - [approximate_pattern_matching] - [maximal_exact_match] +- [internal_pattern_matching] ## Generalizations diff --git a/polynomial_hierarchy b/polynomial_hierarchy @@ -1,8 +1,9 @@ # Polynomial hierarchy (PH) -- first levels: [nptime], [conptime] +- first levels: [NPtime], [coNPtime] - see also [np_cap_conp] - second level: [pi2], [sigma2] + - [Pi2_complete], [Sigma2_complete] - see also [pi2_cap_sigma2] - [delta2p] = [ptime] with an [nptime] [oracle] - https://complexityzoo.net/Complexity_Zoo:D#delta2p diff --git a/posbool b/posbool @@ -0,0 +1,7 @@ +# PosBool + +Like [why_provenance], but imposing [absorptivity] + +Corresponds to [Boolean_formulas_positive] over the set of [provenance_tokens] seen as [variables] + +Up: [why_provenance] diff --git a/provenance b/provenance @@ -0,0 +1,42 @@ +# Provenance + +https://en.wikipedia.org/wiki/Data_lineage#Data_provenance + +foundational [academic_paper]: [green2007provenance], using [semiring], i.e., [semiring_provenance] + +Uses of provenance: +- [uncertainty] + - [pqe] +- [reasoning] +- [explanation] + +In various settings, e.g., [query_languages] and [types_of_data]: +- For [Datalog]: [provenance_datalog] +- For [reasoning]: [provenance_reasoning] +- For [description_logics]: [provenance_description_logics] +- For [logic]: [provenance_logic] +- For [games]: [provenance_games] +- For [CQs]: [provenance_optimal_joins] + - Specifically for [triangles]: [provenance_triangle] +- On [treelike_data]: [provenance_treelike_data] + +Formalisms: +- [provenance_expression] +- [provenance_circuit] + +Kinds of provenance: +- [provenance_semirings] + - [why_provenance] +- [where_provenance] + +[Computational_problems]: +- [provenance_computation] + +[Research_questions]: +- [provenance_size] + +- [provenance_practical] + +See also: [explainability], [artificial_intelligence_explainable], [pqe] + +Up: [research] diff --git a/provenance_circuit b/provenance_circuit @@ -6,3 +6,5 @@ Can use [circuit] for [provenance], e.g., - [provenance_mso]: [monadic_second_order_logic] provenance [amarilli2015provenance] Up: [provenance], [circuit] + +Aliases: provenance circuits diff --git a/provenance_datalog b/provenance_datalog @@ -0,0 +1,16 @@ +# Provenance for Datalog + +Computing [provenance] for [Datalog] [queries] + +Subcases: +- [provenance_stratified_datalog] + +[Academic_papers]: + +- [bourgaux2022revisiting] gives several different definitions +- [calautti2024below]: computing [why_provenance] + - computing [whyminimal_provenance] and [whymultiplicity_provenance] + - [calautti2023complexity]: [provenance_membership_testing] +- [convergence] for [datalog]: [abokhamis2021convergence] + +Up: [provenance], [datalog] diff --git a/provenance_optimal_joins b/provenance_optimal_joins @@ -1,5 +1,8 @@ # Provenance for optimal joins -- wang2022query, achieves [polymatroid] bound +Building [provenance_circuits] during [query_evaluation]: see [wang2022query] + - achieves [polymatroid] bound Up: [optimal_joins] with [provenance] + +See also: [PANDA] diff --git a/provenance_panda b/provenance_panda @@ -1,5 +0,0 @@ -# Provenance for PANDA - -see [wang2022query] - -Up: [provenance] for [panda] diff --git a/quantifier b/quantifier @@ -0,0 +1,12 @@ +# Quantifier + +- [existential_quantifier] +- [universal_quantifier] + +- [quantifier_rank] + +Up: [logic] + +See also: [QBF] + +Aliases: quantification diff --git a/query_recursive b/query_recursive @@ -8,3 +8,5 @@ Up: [query_language] Aliases: recursive query, recursive queries + +See also: [query_nonrecursive] diff --git a/semiring_absorptive b/semiring_absorptive @@ -0,0 +1,11 @@ +# Absorptive semiring + +A [semiring] where you have 1 + a = 1 for every a + +Implies [semiring_idempotence] + +[absorptive_semiring_notes] + +Up: [dioid] + +See also: [absorptivity] diff --git a/semiring_idempotent b/semiring_idempotent @@ -1,5 +1,9 @@ # Idempotent semiring -A [semiring] satisfying the equation a+a = a for every a +A [semiring] satisfying the equation a+a = a for every a ("additively idempotent") + +Not the case of all [semirings], e.g., not the [natural_numbers] Up: [semiring], [idempotent] + +Aliases: semiring idempotence, idempotent semiring, idempotent semirings diff --git a/semiring_list b/semiring_list @@ -0,0 +1,28 @@ +# Semiring examples + +- The [Boolean_semiring] + +- The [natural_numbers] + - useful for [bag_semantics] in [query_evaluation] + +- The [universal_semiring], and its variants + - [bool_x] losing coefficients ([sets] of [bags]) + - [semiring_absorptive]: adding [absorptivity] + - [Trio] semiring: losing exponents ([bags] of [sets]) + - [Why_provenance] losing coefficients and exponents ([sets] of [sets]) + - [PosBool] imposing [absorptivity], + - And losing exponents relative to [semiring_absorptive] + - [Which_provenance]: just a [set] + +- The [min_max_semiring]: (A, [max], [min], 0, 1) + - in particular [access_control_semiring] and [fuzzy_semiring] + +- The [Viterbi_semiring], aka the confidence semiring +- The [tropical_semiring] +- The [fuzzy_semiring] + +- Any [ring] + +- [semiring_examples_others] + +Up: [semiring] diff --git a/semiring_provenance b/semiring_provenance @@ -0,0 +1,11 @@ +# Semiring provenance + +[Provenance] of [queries] using [semirings] to cover multiple use cases + +Foundational paper: [green2007provenance] + +For [query_optimization], you need the [semiring] to be [semiring_commutative] + +Up: [provenance], [semirings] + +See also: [provenance_polynomial] diff --git a/sequence b/sequence @@ -5,6 +5,8 @@ - [Kleene_sequence] - [De_Bruijn_sequence] - [arithmetic_progression] +- [hailstone_sequence] +- [Recamans_sequence] ## Concepts diff --git a/subsequence b/subsequence @@ -16,6 +16,8 @@ - [longest_increasing_subsequence] - [p_subsequence] - [subsequence_automaton] +- [absent_subsequence] +- [subsequence_order] See also: [subword], [sequence], [subword], [supersequence] diff --git a/synchronizing_word b/synchronizing_word @@ -4,4 +4,4 @@ Up: [automata] -See also: [mortal_word], [meeting_time] +See also: [mortal_word], [meeting_time], [synchronizing_sets] diff --git a/transient_state b/transient_state @@ -0,0 +1,5 @@ +# Transient state + +terminology in [ganardi2024regular] for [states] that cannot be reached from themselves + +Up: [state] diff --git a/tree_automaton b/tree_automaton @@ -21,3 +21,5 @@ and [jumping_automata_on_graphs] jumping automata on graphs Up: [automata] on [tree] See also: [dtd], [xml] + +Aliases: tree automata diff --git a/tree_automaton_bottom_up b/tree_automaton_bottom_up @@ -0,0 +1,8 @@ +# Tree automaton bottom up + +- [initialization_function] / [initialization_relation] +- [transition_function] / [transition_relation] +- can be [automaton_deterministic] ([bDTA]) or [automaton_nondeterministic] ([bNTA]) +- can be [automaton_unambiguous] ([bUTA]) + +Up: [tree_automaton], [bottom_up] diff --git a/tropical b/tropical @@ -0,0 +1,7 @@ +# Tropical + +- [tropical_semiring] + +Named after https://en.wikipedia.org/wiki/Imre_Simon + +Up: [mathematics] diff --git a/tropical_semiring b/tropical_semiring @@ -0,0 +1,13 @@ +# Tropical semiring + +The [semiring] defined with [min] and [plus] + +Intuition: you want the derivation with least cost ([min]), and joint use of values means you pay for both ([plus]) + +Useful for [shortest_path] in [graphs] + +Up: [semiring_list] + +See also: [mpp_minimum], [tropical] + +Aliases: semiring tropical diff --git a/uc2rpq b/uc2rpq @@ -1,11 +1,11 @@ # UC2RPQ -[query_union] of [C2RPQs] +A [query] which is a [disjunction] of [C2RPQs] Studied for such [queries]: - [semantic_acyclicity] - [figueira2024semantic] - - [feier2024evaluating]: article on [treewidth] and + - [feier2024evaluating]: article on [treewidth] Up: [graph_query_languages], [c2rpq], [union_of_conjunctive_queries] diff --git a/universal_semiring b/universal_semiring @@ -1,10 +1,10 @@ # Universal semiring -N[X], [semiring] of [polynomial]s with [variable]s X +[NN][X ], [semiring] of [polynomials] with [variables] X - [universality_property] -- [commutation_under_homomorphism]s +- [commutation_under_homomorphisms] Up: [semiring_list] -See also: [power_series] +See also: [power_series], [provenance_polynomial] diff --git a/update_word b/update_word @@ -10,3 +10,7 @@ - [word_split]: related to [cut_and_paste] Up: [update] for [word] + +See also: [dynamic_word] + +Aliases: updates word diff --git a/viterbi_semiring b/viterbi_semiring @@ -0,0 +1,9 @@ +# Viterbi semiring + +The [semiring] defined as ([0, 1], [max], [multiplication], 0, 1) + +Intuitively: you want the derivation with highest confidence ([max]), and when you use several values simultaneously then confidence decreases via [multiplication] + +Up: [semiring_list] + +See also: [tropical_semiring] diff --git a/which_provenance b/which_provenance @@ -0,0 +1,5 @@ +# Which provenance + +The [set] of [provenance_tokens] that intervene in the answers ([flattens] [conjunction] and [disjunction]) + +Up: [semiring_list] diff --git a/why_provenance b/why_provenance @@ -0,0 +1,9 @@ +# Why provenance + +[Semiring_provenance] in the [semiring] of [sets] of [sets] of [provenance_tokens] + +Specialization: [PosBool] + +- [why_provenance_computation] + +Up: [provenance] diff --git a/why_provenance_computation b/why_provenance_computation @@ -0,0 +1,5 @@ +# Why provenance computation + +- [calautti2024computing] via [sat_solver] + +Up: [provenance_computation] for [why_provenance] diff --git a/word b/word @@ -5,20 +5,25 @@ Finite [sequence] of [letters] - [primitive_word] - [twin] -generalization: +Quantities: +- [length] + +Generalizations: - [data_word] +- [dynamic_word] -operation: +Operations: - [concatenation] - [primitive_root] - [mirror] -type: +Special cases: - [palindrome] - [square_word] +- [empty_word] Up: [formal_language_theory] -See also: [update_word], [empty_word], [sequence], [dynamic_word] +See also: [update_word], [sequence] -Aliases: words +Aliases: words, string, strings