Essential Context Free Expression (part 1)

EasyChair Preprint 4808

Abstract

We 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 fixed-pattern 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, Cumulative time, Pattern specification, Semantic condition, Semi syntactic, String pattern match, Stringology, complexity complete, component pattern, constrained concatenation, context-free grammar, pattern match

@booklet{EasyChair:4808,
  author    = {Charles Qiuen Yu},
  title     = {Essential Context Free Expression (part 1)},
  howpublished = {EasyChair Preprint 4808},
  year      = {EasyChair, 2020}}