Open AccessThe execution complexity of logical formulas with restricted quantifiers based on CF-grammars
Author(s) -
Ksenia Korovina,
I Sh Rudova
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/2131/2/022131
Subject(s) - formal grammar , rule based machine translation , context free grammar , programming language , computer science , sort , syntax , hierarchy , context sensitive grammar , extended affix grammar , polynomial hierarchy , tree adjoining grammar , definite clause grammar , context (archaeology) , theoretical computer science , algebra over a field , mathematics , time complexity , algorithm , natural language processing , pure mathematics , paleontology , biology , economics , market economy , information retrieval
The polynomial realized formulas are introduced with quantifiers acting on hierarchy lists described by CF-grammars. Upper estimates of execution complexity are obtained depending from the sort of grammar. These formulas have been applied for formal definition of context-dependent syntax of programming languages and describing dynamic discrete system.