wiki_research

commit f42898f84f04c1b41e0e37e2f2f5c5649a7b58b4
parent 0674e4a4dd2e1dc3edf5ae8410d84341afb0d0bf
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 17 Sep 2025 11:55:28 +0200

commit with codex

Diffstat:
automata_parikh
 | 
11
+++++++++++
automata_types
 | 
1
+
capture_groups
 | 
9
+++++++++
context_free_grammar
 | 
3
++-
context_free_grammar_ultralinear
 | 
9
+++++++++
parikh_image
 | 
2
+-
quantitative
 | 
3
++-

7 files changed, 35 insertions(+), 3 deletions(-)
diff --git a/automata_parikh b/automata_parikh
@@ -0,0 +1,11 @@
+# Automata parikh
+
+https://fr.wikipedia.org/wiki/Automate_de_Parikh
+
+introduced in [klaedtke2003monadic]
+
+Up: [automata_types]
+
+See also: [parikh_image]
+
+Aliases: Parikh automata
diff --git a/automata_types b/automata_types
@@ -31,5 +31,6 @@
 - [omega_automata]
 - [automata_multitape]
 - [limited_automata]
+- [automata_parikh]
 
 Up: [automata]
diff --git a/capture_groups b/capture_groups
@@ -0,0 +1,9 @@
+# Capture groups
+
+[berglund2017semantics] on the practical semantics used for [regular_expression_matching] with capture groups
+
+Up: [regular_expression_extensions]
+
+See also: [capture_variables], [backreferences], [document_spanners], [amarilli2024skyline]
+
+Aliases: capture group
diff --git a/context_free_grammar b/context_free_grammar
@@ -20,7 +20,8 @@
 - [context_free_grammar_deterministic]
 - [context_free_grammar_unambiguous]
   - [context_free_grammar_ambiguous]
-- [context_free_grammar_linear]
+- [context_free_grammar_ultralinear]
+  - [context_free_grammar_linear]
 - [context_free_grammar_bounded]
 - [context_free_grammar_polyslender]
 - [context_free_grammar_finite]
diff --git a/context_free_grammar_ultralinear b/context_free_grammar_ultralinear
@@ -0,0 +1,9 @@
+# Context free grammar ultralinear
+
+A [CFG] where there is a bound on the maximal number of [nonterminals] that can occur in any [derivation]
+
+Can be seen in terms of [PDAs] via the notion of [PDA_finite_turn], studied in [ginsburg1966finite]
+
+Special case: [linear_CFGs]
+
+Up: [context_free_grammar]
diff --git a/parikh_image b/parikh_image
@@ -11,6 +11,6 @@ The Parikh image is not always [recognizable] even for a [regular_language]
 
 Up: [formal_language_theory]
 
-See also: [language_commutative], [length]
+See also: [language_commutative], [length], [Parikh_automata]
 
 Aliases: parikh images
diff --git a/quantitative b/quantitative
@@ -1,5 +1,6 @@
 # Quantitative
 
-- [quantitative_mso]
+- [quantitative_MSO]
+  - cf [klaedtke2003monadic]
 
 Up: [logic]