Fundamentals of Computation Theory
Proceedings of the 1977 International FCT-Conference.
- 40 stránek
- 2 hodiny čtení
This work delves into various aspects of computational theory, including methodologies for proving finite-state stochastic representability and non-representability, and explores non-deterministic recursive program schemes. It discusses relational composition, axiomatization of rational data objects, and recent findings on recognizable formal power series. The text examines canonical forms of context-free grammars, environments, labyrinths, and automata, alongside the role of stochastic algebras and automata in measurable algebraic theory, including a decomposition theorem. Key topics include algebraic semantics of type definitions, universal algebras, and tree automata, as well as vectors of coroutines over blikle nets. The work also addresses initial algebraic semantics for non-context-free languages, operations on ?-regular languages, and the relationship between graph grammars and graph L-systems. It covers syntactic monoids for rational languages, disjunctive languages, R-fuzzy languages, and algebras of partial sequences related to concurrency. Further discussions include fixed points of functors, recognizable languages in categories, free dynamics, efficient state-splitting, and embedding theorems in graph grammar algebra. The text also touches on partial recursive definitions, transformations in graph grammars, categorical grammar applications, and the complexities of various computational problems, including NP-comp



