Download PDFOpen PDF in browserEssential Context Free Expression (part 1)EasyChair Preprint no. 480814 pages•Date: December 25, 2020AbstractWe introduce a system of string pattern specification, notation $ECFX$ for Essential Context Free Expression, as an extension of $CFX$, notation for Context Free Grammar. The approach of $ECFX$ is seen in three methodological principles: using $CFX$ rules for syntax kernel, allowing arbitrary means of semantic condition for extra control, subject only to a complexity limit, applying the proper complexity of $CFX$ as uniform constraint to all semantic conditions. The rule format of $ECFX$ is $X\rightarrow x [\bfc]$ where $X\rightarrow x$ is a usual $CFX$ rule, and $\bfc$ is an optional semantic condition on the strings that would match $x$. Let $CFTIME$ stands for the time complexity of $CFX$ for fixed pattern. A pattern $X$ is in $ECFX$ if $X$ is equivalent to a finite set of $ECFX$ rules where all semantic conditions involved are in $CFTIME$. For characteristics of $ECFX$: \begin{description} \item[] $ECFX$ imposes $CFX$ structure on all its member patterns; \item[] $ECFX$ is \emph{complexity complete} in the sense that for any pattern $X$, $X$ is in $ECFX$ if and only if the fixed pattern decision problem for $X$ is in $CFTIME$; \item[] $ECFX$ as language class is a full trio as it is closed on all full trio required operations \cite{hopcroft1979}; \item[] $ECFX$ is in $O(n^3)$ for fixedpattern complexity; \item[] $ECFX$ is closed on the following operations: a. \hyperref[dfn:constrained_concatenation]{constrained concatenation} as a generalization of back referencing with a \hyperref[dfn:sequentiality]{restriction}, b. \hyperref[dfn:constrained_iteration]{constrained iteration} for an extension of Kleene star with arbitrary number of iterations synchronized and crossed, and c. \hyperref[dfn:pattern_permutation]{permutation} for casting any $ECFX$ pattern as a permutation pattern of base patterns. Keyphrases: Back referencing, complexity complete, component pattern, constrained concatenation, contextfree grammar, Cumulative time, pattern match, Pattern specification, Semantic condition, Semi syntactic, String pattern match, Stringology
