wiki_research

commit 4b4d7ecd6ecdc439847ffc878c33448d0eb0abf3
parent 0745ea20ab4130a50ff08cd27a7dac1ff507b6bb
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Mon,  5 May 2025 13:07:19 +0200

commit with codex

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

11 files changed, 47 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/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/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]