Fundamentals of Computation Theory: Proceedings of the 1977 International FCT-Conference, Poznan-Kórnik, Poland September 19–23, 1977

Front Matter....Pages I-XI
Front Matter....Pages 1-1
Methodology of Proving a Finite-State Stochastic Representability and Nonrepresentability....Pages 3-11
Non Deterministic Recursive Program Schemes....Pages 12-21
Some Remarks on Relational Composition in Computational Theory and Practice....Pages 22-32
An Axiomatization of the Rational Data Objects....Pages 33-38
Some Recent Results on Recognizable Formal Power Series....Pages 39-48
Canonical Forms of Context-Free Grammars and Position Restricted Grammar Forms....Pages 49-53
Environments, Labyrinths and Automata....Pages 54-64
Automata in Labyrinths....Pages 65-71
Stochastic Algebras and Stochastic Automata over General Measurable Spaces: Algebraic Theory and a Decomposition Theorem....Pages 72-77
Some Remarks on the Algebra of Automaton Mappings....Pages 78-83
Algebraic Semantics of Type Definitions and Structured Variables....Pages 84-97
Universal Algebras and Tree Automata....Pages 98-112
Vectors of Coroutines over Blikle Nets....Pages 113-119
Initial Algebraic Semantics for Non Context-Free Languages....Pages 120-126
Reading Functions and an Extension of Kleene Theorem for Some Families of Languages....Pages 127-134
Operations on ω-Regular Languages....Pages 135-141
On the Relation between Graph Grammars and Graph L-Systems....Pages 142-151
On the Theory of Syntactic Monoids for Rational Languages....Pages 152-165
The equivalence of schemata with some feedbacks....Pages 166-170
Disjunctive Languages and Codes....Pages 171-176
Front Matter....Pages 1-1
Families of R-Fuzzy Languages....Pages 177-186
Algebras of Partial Sequences — A Tool to Deal with Concurrency....Pages 187-196
Front Matter....Pages 197-197
Remarks on Fixed Points of Functors....Pages 199-205
Recognizable and Regular Languages in a Category....Pages 206-211
Free Dynamics and Algebraic Semantics....Pages 212-227
Efficient State-Splitting....Pages 228-239
Nets over Many Sorted Operator Domains and Their Semantics....Pages 240-244
Embedding Theorems in the Algebraic Theory of Graph Grammars....Pages 245-255
Some “Geometrical” Categories Associated with Flowchart Schemes....Pages 256-259
On Partial Recursive Definitions and Programs....Pages 260-274
Transformations of Derivation Sequences in Graph Grammars....Pages 275-286
Applicability of a Production in a Categorical Grammar....Pages 287-293
On Order-Complete Universal Algebra and Enriched Functorial Semantics....Pages 294-301
Functorial Semantics of the Type Free λ-βη Calculus....Pages 302-307
A More Categorical Model of Universal Algebra....Pages 308-313
Graph Grammars....Pages 314-331
Fixed-Points and Algebras with Infinitely Long Expressions, II....Pages 332-339
Relational Automata in a Category and Their Languages....Pages 340-355
Generalized Linton Algebras....Pages 356-358
Front Matter....Pages 359-359
On Analysis of Protoschemes....Pages 361-366
Front Matter....Pages 359-359
Using Determinancy of Games to Eliminate Quantifiers....Pages 367-378
Non-Generable RE Sets....Pages 379-385
Polynomial Time Algorithms in the Theory of Linear Diophantine Equations....Pages 386-392
Complexity of Common Subsequence Problems....Pages 393-398
Complexity of Sequence Encodings....Pages 399-404
Network Complexity....Pages 405-420
On Computability of Kolmogorov Complexity....Pages 421-422
The Equivalences Problems for Binary EOL-Systems are Decidable....Pages 423-434
On a Theory of Inductive Inference....Pages 435-440
On Finite and Infinite Computations....Pages 441-446
Expected Behavior of Graph Coloring Algorithms....Pages 447-451
Two NP-Complete Problems Related to Information Retrieval....Pages 452-458
On Properties of Certain Synchronizing Tool for Parallel Computations....Pages 459-465
The Parallel Complexity of Arithmetic Computation....Pages 466-475
Maximal Rectangular Relations....Pages 476-481
A Dushnik — Miller Type Dimension of Graphs and its Complexity....Pages 482-493
Programmability and P=NP Conjecture....Pages 494-498
An Algorithmic Approach to Set Theory....Pages 499-510
Decidability of ω — Trees with Bounded Sets — A Survey....Pages 511-515
Empty — Storage — Acceptance of ω — Languages....Pages 516-521
Front Matter....Pages 359-359
Degrees of Circuit Complexity....Pages 522-531
Recursive ω -Languages....Pages 532-537
A Generalized Computability Thesis....Pages 538-542