Hasil Pencarian  ::  Simpan CSV :: Kembali

"An overview of current developments in research on feasible computations; and a consideration of this area of research in relation to provable properties of complexity of computations. The author begins by defining and discussing efficient reductions between problems and considers the families and corresponding complete languages of NL, DCSL, CSL, P, NP, PTAPE, EXPTIME, and EXPTAPE. Definitions and results are uniformly extended to computationally simpler natural families of languages such as NL, P, and CSL by using Log n-tape bounded reductions. The problem of determining what can and cannot be formally proven about running times of algorithms is discussed and related to the problem of establishing sharp time bounds for one-tape Turing machine computations, and the inability to formally prove running times for algorithms is then related to the presence of gaps in the hierarchy of complexity classes."

"This book constitutes the refereed proceedings of the 6th International Conference on Language and Automata Theory and Applications, LATA 2012, held in A Coruña, Spain in March 2012. The 41 revised full papers presented together with 3 invited talks and 2 invited tutorials were carefully reviewed and selected from 114 initial submissions. The volume features contributions from both classical theory fields and application areas; e.g. innformatics, systems biology, language technology, artificial intelligence, etc. Among the topics covered are algebraic language theory, automata and logic, systems analysis, systems verifications, computational complexity, decidability, unification, graph transformations, language-based cryptography, and applications in data mining, computational learning, and pattern recognition."

"Algebraic Theory of Automata Networks investigates automata networks as algebraic structures and develops their theory in line with other algebraic theories, such as those of semigroups, groups, rings, and fields. The authors also investigate automata networks as products of automata, that is, as compositions of automata obtained by cascading without feedback or with feedback of various restricted types or, most generally, with the feedback dependencies controlled by an arbitrary directed graph. This self-contained book surveys and extends the fundamental results in regard to automata networks, including the main decomposition theorems of Letichevsky, of Krohn and Rhodes, and of others."