On an interesting hypothesis of the theory of formal languages
- سال انتشار: 1403
- محل انتشار: مجله ریاضیات گسسته و کاربردهای آن، دوره: 9، شماره: 2
- کد COI اختصاصی: JR_JDMA-9-2_001
- زبان مقاله: انگلیسی
- تعداد مشاهده: 133
نویسندگان
Shenzhen MSU-BIT University
چکیده
The formulation of a hypothesis for any pair of nonempty finite languages is considered. The hypothesis consists in the formulation of the necessary conditions for the equality of infinite iterations of these languages, the paper provides some equivalent versions of this hypothesis. When fulfilling this hypothesis, we show the possibility of verifying the equality of infinite iterations of these languages in polynomial time. On the other hand, we present a plan for reducing the verification of the same equality to checking the completeness of the language of a specially constructed nondeterministic finite automaton, and such a check cannot be carried out in polynomial time. In this regard, the possibility of reducing the equality P=NP to the special hypothesis of the theory of formal languages is formulated.کلیدواژه ها
formal languages, iterations of languages, binary relations, morphisms, inverse morphismsاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.