commit 5fae146d5b850d55afea187ad1014f47c21b7b0c
parent 57cbd458ea7f5eeb2d975c293d855f6e0798426c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 9 Oct 2025 21:53:11 +0200
Merge branch 'master' of a3nm.net:git/wiki_research
Diffstat:
18 files changed, 67 insertions(+), 24 deletions(-)
diff --git a/automata_types b/automata_types
@@ -32,5 +32,6 @@
- [automata_multitape]
- [limited_automata]
- [automata_parikh]
+- [common_guess_automata]
Up: [automata]
diff --git a/context_free_grammar_linear b/context_free_grammar_linear
@@ -7,6 +7,8 @@ https://en.wikipedia.org/wiki/Linear_grammar
- [linear_CFG_equivalence]
- Testing [language_emptiness] of [intersection] is already [undecidable] by reduction from [post_correspondence_problem]
+By [Greibach's_theorem], it is undecidable whether an input [CFG] recognizes a [linear_CFL]
+
Up: [context_free_grammar]
Aliases: linear grammar, linear grammars, linear context-free grammar, linear context-free grammars, linear CFG, linear CFGs
diff --git a/context_free_language_linear b/context_free_language_linear
@@ -6,6 +6,8 @@ Special cases:
- [unambiguous_linear_CFL]
- [deterministic_linear_CFL]
+By [Greibach's_theorem], it is undecidable whether an input [CFG] recognizes a [linear_CFL]
+
Up: [context_free_language]
Aliases: linear context-free language, linear context-free languages, linear CFL, linear CFLs
diff --git a/crpq b/crpq
@@ -4,6 +4,7 @@
- [RPQ]
- [CQ]
- [Boolean_CRPQ]
+- [CRPQ_acyclic]
[Generalizations]:
- [C2RPQ]
diff --git a/ehrenfeucht_fraisse_game b/ehrenfeucht_fraisse_game
@@ -1,18 +0,0 @@
-# EF-game
-
-Spoiler plays in [structure] A by marking a [vertex], Duplicator answers in [structure] B
-
-The structures induced by the [pebbles] must be [isomorphic]
-
-- Number of rounds necessary to distinguish both [structures]
- - connections to types nombre de rounds nécessaires pour distinguer les deux structures ([quantifier_rank])
-- Number of [pebbles] needed
- - connection to [FOk]
-
-[MSO] EF-game: the players can pebble sets
-
-Up: [logic], [games]
-
-See also: [bisimulation], [homomorphic_equivalence], [prover_verifier_game]
-
-Aliases: EF game, EF games
diff --git a/fagin1983degrees b/fagin1983degrees
@@ -4,7 +4,6 @@
- [beta_acyclic]
- [lanzinger2021tractability]
- [gamma_acyclic]
- - cf [delpia2018multilinear]
- [berge_acyclic]
Up: [academic_paper] about [hypergraph_acyclicity]
diff --git a/first_order_positive b/first_order_positive
@@ -0,0 +1,11 @@
+# Positive first order
+
+[FO] without [negation] but with [universal_quantification]
+
+Should be distinguished from [existential_positive_FO] which also disallows [universal_quantification]
+
+Discussed in [berkholz2019compiling] and in [bova2014complexity]
+
+Up: [first_order_logic]
+
+Aliases: positive FO, positive first order
diff --git a/fok b/fok
@@ -2,6 +2,8 @@
[first_order_logic] with k variables, or [first_order_logic_width] k
+Also called "finite variable logics" in the [survey] [grohe1998finite]
+
## Fragments
- [fo2]
@@ -14,12 +16,14 @@
- [satisfiability] of FO^2 etc., cf "kings" [gradel1997decision]
-- [first_order_model_checking_fok]
+- [model_checking]: [first_order_model_checking_fok]
- special case: [first_order_model_checking_fo2]
- connections to [yannakakis_algorithm]
- finding the best k: [fok_rewriting]
+
+- [fok_quantifier_rank]
Up: [first_order_logic]
-See also: [two_variables]
+See also: [two_variables], [pebble_game]
diff --git a/gamma_acyclic b/gamma_acyclic
@@ -0,0 +1,6 @@
+# Gamma acyclic
+
+- cf [delpia2018multilinear]
+- cf [atserias2025gamma]
+
+Up: [fagin1983degrees]
diff --git a/k_ambiguous_cfg b/k_ambiguous_cfg
@@ -5,9 +5,16 @@ A *k-ambiguous CFG* is a [CFG] where every [word] has at most k [parse_trees]
Special cases:
- k=1: [uCFGs]
- k=2: [2_ambiguous_CFGs]
+- they exist for each value of k, cf [naji1998grad] p9
It is an [open_problem] whether every k-ambiguous CFG can be written as a [language_union] of k [uCFGs], but within [bounded_CFGs] this is known to be true, cf [wich2005ambiguity] p181 point (iv).
+[Computational_problems]:
+- [CFG_inclusion]: [undecidable], in fact already [undecidable] for [linear_uCFGs]
+- [CFG_equivalence]: [open_problem] whether it is [decidable], in fact already open for [UCFGs]
+- [CFG_universality]: [undecidable], because testing if there is a word in the [intersection] of two [linear_UCFGs] is [undecidable] (by coding [Turing_machines] using [baker1974reversal])
+- counting the number of words in the [k_slice]: this is [sharpP1_hard] by [bertoni1991complexity]
+
Up: [k_ambiguous], [CFG]
See also: [infinitely_ambiguous_CFG], [Degree_of_ambiguity_cfg]
diff --git a/level_ancestor b/level_ancestor
@@ -1,5 +1,7 @@
# Level ancestor
+https://en.wikipedia.org/wiki/Level_ancestor_problem
+
Do [preprocessing] on a [tree] and compute a [data_structure] such that given a [node] and integer d you can find the [ancestor] of the [node] at distance d from it (or, equivalently, at specified [depth])
Can be done with linear preprocessing of the tree and constant query time
@@ -8,4 +10,12 @@ Can be done with linear preprocessing of the tree and constant query time
- [bender2003level]: simplified version of the problem
- decompose into [microtrees]
-Up: [data_structure]
+Less efficient solutions:
+- [jump_pointers]: store logarithmically many pointers to go up by powers of two
+- [long_path_decomposition]
+
+Up: [data_structure], [ancestor]
+
+Aliases: level ancestor problem
+
+See also: [skip_list]
diff --git a/limited_automata b/limited_automata
@@ -4,6 +4,8 @@
Used in [guillon2025polynomial]
+Special case: [1_limited_automata]
+
Up: [automata_types]
Aliases: automaton limited, automata limited, limited automaton
diff --git a/probabilistic_databases b/probabilistic_databases
@@ -25,6 +25,10 @@
- [pqe_applications]
- [probabilistic_databases_practice]
+techniques:
+- [probabilistic_databases_ranking]
+- [karp_luby_algorithm]
+
See also: [relational_algebra], [relational_calculus], [probabilistic_databases_book]
Up: [database_theory]
diff --git a/quantifier b/quantifier
@@ -7,6 +7,6 @@
Up: [logic]
-See also: [QBF]
+See also: [QBF], [prenex_normal_form]
Aliases: quantification, quantifiers
diff --git a/rpq_output_sensitive b/rpq_output_sensitive
@@ -2,4 +2,6 @@
[abokhamis2024output]: improves on [product_graph] by doing an [output_sensitive_algorithm]
+Generalizations to [CPRQ_output_sensitive] for [acyclic_CRPQs] in [abokhamis2025output]
+
Up: [rpq_query_evaluation]
diff --git a/shapley_value b/shapley_value
@@ -10,6 +10,7 @@ Results:
- connections with [model_counting] and [pqe]
- [bienvenu2023when]
- [kara2023from]
+- [standke2025tractability] pour [CQ_aggregates], when is is tractable depending on the [aggregation_function] and the [CQ] shape ([hierarchical_queries], [q_hierarchical_queries])
- [shapley_value_omqa]
diff --git a/slice b/slice
@@ -0,0 +1,9 @@
+# Slice
+
+The n-th *slice* of a [formal_language] L is the number of [words] of L having length n
+
+See also: [density_function]
+
+Up: [formal_language_theory]
+
+Aliases: n slice, k slice
diff --git a/supersequence b/supersequence
@@ -6,4 +6,4 @@ See also: [subsequence]
Up: [formal_language_theory], [stringology]
-Aliases: supersequences
+Aliases: supersequences, scattered superstring, scattered superstrings, scattered superword, scattered superwords
