commit 11f8c098a8b3fbe08a260489b80a7c692f94e097 parent 080dbcfffa0aab9f6d52fe49064b7ba5993ae41b Author: Antoine Amarilli <a3nm@a3nm.net> Date: Wed, 15 Jan 2025 16:02:08 +0100 commit with codex Diffstat:
42 files changed, 320 insertions(+), 35 deletions(-)
diff --git a/alphabet b/alphabet @@ -0,0 +1,7 @@ +# Alphabet + +A finite [set] of [letters] + +Special case: [alphabet_unary] + +Up: [formal_language] diff --git a/arboricity b/arboricity @@ -1,13 +1,13 @@ # Arboricity -Connection between [arboricity] and [dynamic_data] in lu2021towards +Connection between [arboricity] and [dynamic_data] in [lu2021towards] -- chiba1985arboricity -- danisch2018listing +- [chiba1985arboricity] +- [danisch2018listing] - https://papers-gamma.link/paper/32 - https://github.com/maxdan94/kmotif -- ortmann2014triangle algorithm for triangle_listing +- [ortmann2014triangle] algorithm for [triangle_listing] -bressan2022complexity: optimality of the esults of chiba for [graph_pattern_counting] +[bressan2022complexity]: optimality of the results of chiba for [graph_pattern_counting] Up: [width_measure] diff --git a/automata_classes b/automata_classes @@ -0,0 +1,15 @@ +# Automata classes + +- [counter_free_automata] +- [automaton_homogeneous] +- [automata_local] +- [wheeler_nfa] + - [automaton_p_sortable] +- [automata_unary] for [alphabet_unary] +- [automata_acyclic] + - [automata_weakly_acyclic] +- [automata_self_verifying] + +- [DFAs] + +Up: [automata] diff --git a/automata_determinization b/automata_determinization @@ -0,0 +1,12 @@ +# Automata determinization + +[Conversion] of [NFA] into [DFA] + +Usual construction: [powerset_automata] + +Bounds for specific [automata_classes]: +- [unary_ufa] + +Up: [automata_constructions] + +Aliases: automata determinized diff --git a/automata_nondeterministic b/automata_nondeterministic @@ -1,6 +1,10 @@ # Automata nondeterministic (NFA) -There are known upper bounds on the size of the smallest [automata_deterministic] corresponding to an NFA +An [automaton] which is [nondeterministic] + +There are known upper bounds on the size of the smallest [DFA] corresponding to an NFA + +Special case: [automata_nondeterministic_dense] Up: [nondeterministic], [automata_types] diff --git a/automata_two_way b/automata_two_way @@ -1,14 +1,15 @@ # Automata two way -automata that can read the input in both directions +[Automata] that can read the input [word] in both directions -It is [open_problem] if two-way automata can be determinized in [ptime] and related to open problems in [complexity_theory], cf [kapoutsis2013two]: -[sakoda_sipser_conjecture] +It is an [open_problem] if two-way automata can be [automata_determinized] in [PTIME]. This is related to open problems in [complexity_theory], cf [kapoutsis2013two]: [sakoda_sipser_conjecture] Can be converted back to [automata_one_way]. - Elementary construction to get an [automata_nondeterministic] for the complement language in [vardi1989note] with exp(n) blowup - Elementary construction to get an [automata_deterministic] for the language in [shepherdson1959reduction] with exp(n^2) blowup +Generalization: [Two_way_nondeterministic_pushdown_automaton] + Up: [automata] See also: [2rpq] diff --git a/automata_unary b/automata_unary @@ -0,0 +1,13 @@ +# Automata unary + +[Automata] on [alphabet_unary] + +- for [DFAs]: [ultimately_periodic] +- for [UFAs]: [automata_unary_ufa] +- for [NFAs]: + - [chrobak_normal_form] + - [nfa_unary_lengths] + +Up: [automata_classes] + +See also: [tortoise_and_hare_algorithm], [language_unary] diff --git a/bringmann2024nfa b/bringmann2024nfa @@ -0,0 +1,16 @@ +# bringmann2024nfa + +[hardness_hypothesis] for [NFA_acceptance] on [dense_NFA]: [NFA_acceptance_hypothesis] +- Implies hardness for any asymptotic regime of the number of transitions + +Talks about: +- [context_free_language_reachability] +- [word_break_problem] + +Their hardness hypothesis implies the [OMv_hypothesis] + +The question of whether a better algorithm can be found than the known ones was posed in [potechin2020lengths] + +Up: [academic_paper] + +See also: [Karl_bringmann] diff --git a/capture_variable b/capture_variable @@ -0,0 +1,9 @@ +# Capture variable + +can be used for [backreferences], or to define [regex_formulas] + +- [capture_group] in [regular_expression] + +Up: [regular_expression] + +Aliases: capture variables diff --git a/complexity_class b/complexity_class @@ -45,3 +45,5 @@ - P is different from SPACE(n) Up: [computational_complexity] + +Aliases: complexity classes diff --git a/computational_problem b/computational_problem @@ -6,6 +6,7 @@ - [optimization_problem] - [approximation_problem] - [counting_problem] +- [function_problem] ## Terminology diff --git a/context_free_grammar b/context_free_grammar @@ -38,3 +38,5 @@ See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series] Up: [formal_language_theory] + +Aliases: CFG, CFGs, context free grammars, context-free grammars diff --git a/counter_free_automata b/counter_free_automata @@ -0,0 +1,9 @@ +# Counter free automata + +[Automata] without [automata_counters] + +Such automata recognize the [aperiodic_languages] + +Up: [automata_classes] + +Aliases: automata counter-free, automata counter free diff --git a/database_repairs b/database_repairs @@ -1,15 +0,0 @@ -# Database repairs - -[amezianelkhalfioui2022consistent]: [consistent_query_answering] plus [counting] - -[marconi2024consistent] - -with [preferences]: [pardal2024computational] - -- [repair_counting] - -Up: [database_theory] - -See also: [language_repair], [graph_modification] - -Aliases: database repair diff --git a/database_theory_concepts b/database_theory_concepts @@ -3,7 +3,7 @@ - [relational_signature] - [database_relation] - [arity] -- [instance] +- [relational_database] / [instance] - [set_semantics] vs [bag_semantics] - [query] - [query_evaluation] diff --git a/degeneracy b/degeneracy @@ -0,0 +1,16 @@ +# Degeneracy + +https://en.wikipedia.org/wiki/Degeneracy_(graph_theory) + +An [undirected_graph] is k-degenerate if every [subgraph] has at least one [vertex] of [degree] at most k +- it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs], cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples + +Special case: [2_degenerate_graphs] + +Some [enumeration] and [counting] problems on graphs have been studied based on degeneracy and arboricity, see [danisch2018listing] for example + +Generalization to [relational_databases]: [partition_constraints] introduced in [deeds2025partition] + +Up: [width_measure] + +See also: [arboricity] diff --git a/enumeration_graphs b/enumeration_graphs @@ -3,5 +3,6 @@ - [subgraph_enumeration] - [triangle_enumeration] - [clique_enumeration] +- [enumeration_paths] Up: [enumeration] on [graph] diff --git a/epsilon_transition b/epsilon_transition @@ -0,0 +1,7 @@ +# Epsilon transition + +A [transition] labeled with the [empty_word]. It can be traversed by a [run] without consuming any [letter] from the input [word] + +Up: [transition] + +Aliases: epsilon transitions diff --git a/formal_language b/formal_language @@ -1,6 +1,6 @@ # Formal language -[set] of [word] over an [alphabet] +A [set] of [words] over an [alphabet] - [regular_language] - [weighted_language] diff --git a/glushkov_automaton b/glushkov_automaton @@ -0,0 +1,19 @@ +# Glushkov automaton + +https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm + +The *Glushkov automaton* is an [NFA] constructed from a [regular_expression] which recognizes the same language + +It is a [homogeneous_automaton] + +It has O(m^2) transitions with m the [regular_expression], according to [allauzen2006unified] or [nicaud2009average] + +Unlike [thompson_automaton], it does not contain [epsilon_transitions] + +Connections to [local_languages] + +Up: [conversion_automata] + +See also: [thompson_automaton] + +Aliases: position automaton diff --git a/graph_2_degenerate b/graph_2_degenerate @@ -0,0 +1,9 @@ +# 2-degenerate graphs + +[Undirected_graphs] where every [subgraph] has a [vertex] of [degree] at most 2 + +See also: [neuen2024homomorphism], [degeneracy] + +Up: [graph_family] + +Aliases: 2 degenerate graphs, 2 degenerate graph diff --git a/graph_database b/graph_database @@ -0,0 +1,18 @@ +# Graph database + +A [database_instance] on a [relational_signature] where each [database_relation] has [arity] two + +[Queries]: + +- [basic_graph_pattern]: a graph pattern with variables and constants + - [regular_path_query] + +Course notes: [figueira2023foundations] + +Practice: [graph_database_practical] + +Up: [databases] for [graph] + +See also: [property_graph], [sparql] + +Aliases: graph databases diff --git a/graph_sparse b/graph_sparse @@ -7,3 +7,5 @@ An [undirected_graph] where the number of [edges] is o(n^2), for n the number of Up: [graph_family] Aliases: sparse graph, sparse graphs + +See also: [dense_graph] diff --git a/integrity_constraint b/integrity_constraint @@ -5,6 +5,7 @@ - [functional_dependency] - [tuple_generating_dependency] - [inclusion_dependency] +- [denial_constraint] See also: [logic] diff --git a/letter b/letter @@ -0,0 +1,7 @@ +# Letter + +[Elements] of the [alphabet] + +Up: [alphabet] + +Aliases: letters diff --git a/maximal_common_subsequence b/maximal_common_subsequence @@ -1,10 +1,13 @@ # Maximal common subsequence (MCS) -[maximal_common_subsequence] (MCS): common subsequence cannot be extended (inclusion in terms of [substring]) +[maximal_common_subsequence] (MCS): common subsequence cannot be extended (inclusion in terms of [substrings]) - formally: it is a common sequence and no supersequence is a common sequence - [longest_common_subsequence] is MCS but not necessarily vice-versa - [PTIME] to compute MCS for an unbounded number of multiple input strings: [hirota2023fast] +[enumeration] in [conte2019polynomial] +- but there is also a hardness result, Maximal Common Subsequence Enumeration is Hard #todo + - warning! you can compute greedily a common sequence between 2 strings by extending it to the right - but it is not necessarily an MCS, it may still be possible to extend it by an insertion diff --git a/query b/query @@ -4,6 +4,7 @@ - [conjunctive_query] - [query_full] - [query_boolean] + - [query_non_boolean] ## Problems diff --git a/query_boolean b/query_boolean @@ -2,10 +2,10 @@ A [query] whose [query_answer] is a [Boolean]: either the query holds or it does not. -For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by insantianing these [variables] to [constant] +For [queries] with [free_variables] that are [first_order], the [computational_complexity] of computing [query_answers] is often [PTIME]-equivalent to the Boolean queries obtained by considering each of the polynomially many possible answers and creating a Boolean query by insantianing these [variables] to [constants] Up: [query] Aliases: boolean query -See also: [free_variable] +See also: [free_variable], [query_non_boolean] diff --git a/query_non_boolean b/query_non_boolean @@ -0,0 +1,9 @@ +# Query non boolean + +A [query] which returns a [query_answer], i.e., which has [free_variables] + +Up: [query] + +Aliases: non Boolean query, non-Boolean query, non Boolean queries, non-Boolean queries + +See also: [Boolean_query] diff --git a/regex b/regex @@ -1,6 +1,6 @@ # Regex -[regular_expression] with [back_reference]s +[regular_expression] with [back_references] [membership_problem] for Regex is [np_complete] - already for [patterns_with_variables] diff --git a/regex_formula b/regex_formula @@ -0,0 +1,9 @@ +# Regex formula + +A *regex formula* is like a [regular_expression] but with [capture_variables] of the form x{alpha} where x is a [variable] and alpha is a [regular_expression] + +It recognizes a [subset] of the [spanners] that can be expressed with of [vset_automata] + +Up: [spanner] + +Aliases: regex formulas, regex formulae diff --git a/regular_expression b/regular_expression @@ -0,0 +1,33 @@ +# Regular expression + +Operators: [regular_expression_operators] + +Constructions: [conversion_automata] + +[computational_problems]: + +- [regular_expression_matching] + - [sparse_regular_expression_matching] +- [regular_expression_equivalence] +- [regular_expression_inclusion] + +Logical problems: + +- [regular_expression_axiomatization] + +Subclasses: + +- [regular_expression_deterministic] +- [simple_transitive_expressions] + +Practice: + +- [regular_expression_practice] + +[Computational_complexity]: + +- [regular_expression_complexity] + +See also: [compression_research], [rpq], [regular_language] + +Aliases: regular expressions diff --git a/regular_expression_extensions b/regular_expression_extensions @@ -0,0 +1,14 @@ +# Regular expression extensions + +- [regular_expression_conjunction] +- [regular_expression_negation] +- [capture_variables] +- [regex], with [back_references] + - see [freydenberger2019deterministic] +- [lookaround]: + - positive/negative [lookahead] / [lookbehind] +- regular expression with memory, in [graph_databases] +- [regular_expression_repetition] + - "bounded repetition" aka counting "x{n,m}" + +Up: [regular_expression] diff --git a/regular_expression_operators b/regular_expression_operators @@ -0,0 +1,11 @@ +# Regular expression operators + +- [letters] +- [empty_word] +- [empty_set] +- [concatenation] +- [disjunction] +- [kleene_star] +- extensions: [regular_expression_extensions] + +Up: [regular_expression] diff --git a/regular_path_query b/regular_path_query @@ -2,13 +2,11 @@ [query] on [graph_database] defined by [regular_expression] -- [rpq_query_evaluation] -- [rpq_captures] - ## Extensions - [2rpq] - [uc2rpq] +- [rpq_captures] ## Special cases @@ -20,6 +18,7 @@ ## Problems +- [rpq_query_evaluation] - [pqe_rpq] Up: [graph_query_languages] diff --git a/rpq_query_evaluation b/rpq_query_evaluation @@ -2,7 +2,8 @@ survey: [barcelo2013querying] -naive algorithm: [product_graph] +- naive algorithm: [product_graph] +- more efficient algorithm in [abokhamis2024output] - [rpq_fine_grained] - [rpq_trichotomies] diff --git a/simple_transitive_expressions b/simple_transitive_expressions @@ -0,0 +1,9 @@ +# Simple transitive expressions (STE) + +Restricted case of [regular_expressions] covering [regular_expression_practice] + +Introduced in [martens2018evaluation] + +Up: [regular_expression] + +Aliases: simple transitive expression, STE diff --git a/spanner b/spanner @@ -44,9 +44,13 @@ - [spanner_parallelizability] - [spanner_frequent_sequence_mining] +## Extensions + +- [spanners_incomplete] + ## References -- [peterfreund2019complexityb], [phd_thesis] of [liat] +- [peterfreund2019complexityb], [phd_thesis] of [Liat_Peterfreund] Up: [formal_language_theory], [database_theory] diff --git a/state b/state @@ -6,3 +6,5 @@ An [automaton] consists of a set of states, which is generally finite. - [final_state] Up: [automata_concepts] + +Aliases: states diff --git a/substring_complexity b/substring_complexity @@ -0,0 +1,9 @@ +# Substring complexity + +The *substring complexity* of a [word] s for an integer k is its number of distinct [infixes] of length k + +[Algorithm] for [computation] in [bernardini2023substring] + +Up: [compression_string] + +See also: [Simons_congruence] diff --git a/two_way_nondeterministic_pushdown_automaton b/two_way_nondeterministic_pushdown_automaton @@ -0,0 +1,9 @@ +# Two way nondeterministic pushdown automaton + +mentioned in [bringmann2024nfa] + +- [computational_problem]: [2NPDA_acceptance] + +Up: [automata_two_way], [pushdown_automaton] + +Aliases: 2NPDA diff --git a/variable_set_automaton b/variable_set_automaton @@ -0,0 +1,16 @@ +# Variable set automaton + +Like an [automaton] but with [capture_variables], specifically, [transitions] labeled with [variable_markers] to indicate that a variable is opened or closed. + +We only consider the [runs] where the markers are assigned correctly: +- every [variable] is opened exactly once and then closed exactly once + +However, but we do not require markers to be [well_nested], unlike [regex_formulas] where this is required. + +[spanners_incomplete] + +Up: [spanner] + +See also: [capture_variable], [transducer] + +Aliases: spanner automaton, spanner automata, VA, vset automaton, vset automata