wiki_research

commit 7d67624a8a282da754a7cb19d89fded77e7d398f
parent 78f7092313c7aee29c38ccc6147a4844eb970e73
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed,  7 May 2025 11:46:33 +0200

Merge branch 'master' of a3nm.net:git/wiki_research

Diffstat:
automata_problems
 | 
2
+-
automaton_emptiness
 | 
2
+-
complexity_space
 | 
3
+++
context_free_language_commutative
 | 
7
+++++++
context_free_language_complement
 | 
9
+++++++++
enumeration_constant_memory
 | 
9
+++++++++
enumeration_definition
 | 
2
++
enumeration_tasks
 | 
1
+
formal_language
 | 
1
+
language_commutative
 | 
1
+
language_complementation
 | 
2
++
language_emptiness
 | 
6
+++++-
language_universal
 | 
7
+++++++
universality_automata
 | 
7
++++---
universality_problem
 | 
9
+++++++++

15 files changed, 62 insertions(+), 6 deletions(-)
diff --git a/automata_problems b/automata_problems
@@ -2,8 +2,8 @@
 
 - [synchronizing_word]
 - [separating_automaton]
-- [automaton_emptiness]
 - [automaton_finiteness]
+- [automaton_emptiness]
 - [universality_automata]
 - [minimization_automaton]
 - [automaton_inclusion]
diff --git a/automaton_emptiness b/automaton_emptiness
@@ -4,4 +4,4 @@ It is [nl_complete] to check [automaton] emptiness
 
 Up: [automata_problems], [language_emptiness]
 
-See also: [automaton_finiteness]
+See also: [automaton_finiteness], [universality_automata]
diff --git a/complexity_space b/complexity_space
@@ -3,7 +3,10 @@
 - [savitchs_theorem]: we can simulate [nondeterministic] machine with [quadratic] blowup in space
 
 - [catalytic_space]
+- [enumeration_memory]
 
 Up: [complexity_measure]
 
 See also: [complexity_time]
+
+Aliases: space complexity
diff --git a/context_free_language_commutative b/context_free_language_commutative
@@ -0,0 +1,7 @@
+# Context free language commutative
+
+A [context_free_language] which is [language_commutative]
+
+Up: [context_free_language], [language_commutative]
+
+Aliases: commutative CFL
diff --git a/context_free_language_complement b/context_free_language_complement
@@ -0,0 +1,9 @@
+# Context free language complement
+
+A [formal_language] which is the [language_complementation] of a [CFL]
+
+[Emptiness_testing] is [undecidable] because the [universality_problem] is [undecidable] for [CFLs]
+
+Up: [language_complementation], [CFL]
+
+Aliases: CFG complement, CFL complement
diff --git a/enumeration_constant_memory b/enumeration_constant_memory
@@ -0,0 +1,9 @@
+# Enumeration constant memory
+
+An [enumeration_algorithm] where [space_complexity] remains constant throughout the [enumeration_phase]
+
+Up: [enumeration_memory]
+
+Aliases: constant memory enumeration
+
+See also: [Constant_delay], [constant_time]
diff --git a/enumeration_definition b/enumeration_definition
@@ -6,4 +6,6 @@ An [enumeration_algorithm] consists of two phases:
 
 To solve an [enumeration_problem]
 
+[enumeration_memory]
+
 Up: [enumeration]
diff --git a/enumeration_tasks b/enumeration_tasks
@@ -17,6 +17,7 @@
 - [enumeration_spanner]
 - [enumeration_graphs]
   - [enumeration_paths]
+  - [enumeration_leaves]
 - [enumeration_homomorphisms] ([christoph_berkholz])
 - [enumeration_csp] ([christoph_berkholz])
 - [enumeration_topological_sort]
diff --git a/formal_language b/formal_language
@@ -3,6 +3,7 @@
 A [set] of [words] over an [alphabet]
 
 - [empty_language]
+- [language_universal]
 - [singleton_language]
 - [finite_language]
 - [regular_language]
diff --git a/language_commutative b/language_commutative
@@ -1,6 +1,7 @@
 # Commutative language
 
 - [regular_language_commutative]
+- [context_free_language_commutative]
 
 Up: [formal_language] which is [commutative]
 
diff --git a/language_complementation b/language_complementation
@@ -2,6 +2,8 @@
 
 The [complementation] of a [formal_language]
 
+- [context_free_language_complement]
+
 Up: [complementation]
 
 Aliases: language complement
diff --git a/language_emptiness b/language_emptiness
@@ -4,4 +4,8 @@ The [computational_problem] of deciding if a [formal_language] is [empty_languag
 
 - [automaton_emptiness]
 
-Up: [formal_language], [emptiness]
+Up: [computational_problem], [formal_language]
+
+See also: [universality_problem]
+
+Aliases: emptiness testing
diff --git a/language_universal b/language_universal
@@ -0,0 +1,7 @@
+# Language universal
+
+The [formal_language] of every possible [word] over a given [alphabet]
+
+Up: [formal_language]
+
+See also: [empty_language], [universality_problem]
diff --git a/universality_automata b/universality_automata
@@ -4,11 +4,12 @@
 
 - [universality_automata_nondeterministic]: [conp_complete]
 - [universality_automata_deterministic]: [ptime]
-- [universality_automata_pushdown]
+- [universality_context_free_grammar]
+  - [universality_automata_pushdown]
 
 - [factor_universal]
 - [subword_universal]
 
-Up: [computational_problem], [automata]
+Up: [universality_problem], [automata_problems]
 
-See also: [totality], [validity], [taulology]
+See also: [totality], [validity], [taulology], [automaton_emptiness]
diff --git a/universality_problem b/universality_problem
@@ -0,0 +1,9 @@
+# Universality problem
+
+[computational_problem], given a [formal_language], of deciding whether it is [language_universal]
+
+- [universality_automata]
+
+Up: [computational_problem], [formal_language]
+
+See also: [language_emptiness]