Complexity of ∑A and its Connection with Logic
Manju1, Rajesh Kumar2
1Ms. Manju, Assistant Professor, Department of Computer Science & Applications, CRM Jat College, Hisar (Haryana), India.
2Mr. Rajesh Kumar, Assistant Professor, Department of Computer Science & Applications, CRM Jat College, Hisar (Haryana), India.
Manuscript received on June 20, 2017. | Revised Manuscript received on June 28, 2017. | Manuscript published on July 05, 2017. | PP: 34-36 | Volume-7 Issue-3, July 2017. | Retrieval Number: C3030077317/2017©BEIESP
Open Access | Ethics and Policies | Cite | Mendeley
©The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We investigate the connection of logic with complexity of basic operations. Upper and lower bounds for the finite-state complexity of arbitrary strings, and for strings of particular types, are given and incompressible strings are studied. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.
Keywords: Finate Automat, Formal Languages, Logic, State Complexity.