Fundamentals of Computation Theory

More about the book

Methodology of proving a finite-state stochastic representability and nonrepresentability.- Non deterministic recursive program schemes.- Some remarks on relational composition in computational theory and practice.- An axiomatization of the rational data objects.- Some recent results on recognizable formal power series.- Canonical forms of context-free grammars and position restricted grammar forms.- Environments, labyrinths and automata.- Automata in labyrinths.- Stochastic algebras and stochastic automata over general measurable Algebraic theory and a decomposition theorem.- Some remarks on the algebra of automaton mappings.- Algebraic semantics of type definitions and structured variables.- Universal algebras and tree automata.- Vectors of coroutines over blikle nets.- Initial algebraic semantics for non context-free languages.- Reading functions and an extension of Kleene theorem for some families of languages.- Operations on ?-regular languages.- On the relation between graph grammars and graph L-systems.- On the theory of syntactic monoids for rational languages.- The equivalence of schemata with some feedbacks.- Disjunctive languages and codes.- Families of R-fuzzy Languages.- Algebras of partial sequences - A tool to deal with concurrency.- Remarks on fixed points of functors.- Recognizable and regular languages in a category.- Free dynamics and algebraic semantics.- Efficient state-splitting.- Nets over many sorted operator domains and their semantics.- Embedding theorems in the algebraic theory of graph grammars.- Some "geometrical" categories associated with flowchart schemes.- On partial recursive definitions and programs.- Transformations of derivation sequences in graph grammars.- Applicability of a production in a categorical grammar.- On order-complete universal algebra and enriched functorial semantics.- Functorial semantics of the type free ?-?? calculus.- A more categorical model of universal algebra.- Graph grammars.- Fixed-points and algebras with infinitely long expressions, II.- Relational automata in a category and their languages.- Generalized linton algebras.- On analysis of protoschemes.- Using determinancy of games to eliminate quantifiers.- Non-generable RE sets.- Polynomial time algorithms in the theory of linear diophantine equations.- Complexity of common subsequence problems.- Complexity of sequence encodings.- Network complexity.- On computability of Kolmogorov complexity.- The equivalences problems for binary EOL-Systems are decidable.- On a theory of inductive inference.- On finite and infinite computations.- Expected behavior of graph coloring algorithms.- Two NP-complete problems related to information retrieval.- On properties of certain synchronizing tool for parallel computations.- The parallel complexity of arithmetic computation.- Maximal rectangular relations.- A Dushnik - Miller type dimension of graphs and its complexity.- Programmability and P=NP conjecture.- An algorithmic approach to set theory.- Decidability of ? - Trees with bounded sets - A survey.- Empty - storage - acceptance of ? - languages.- Degrees of circuit complexity.- Recursive ?-languages.- A generalized computability thesis.