Fundamentals of Computation Theory: Proceedings of the 1981 International FCT-Conference, Szeged, Hungary August 24–28, 1981

Observability and Nerode equivalence in concrete categories....Pages 1-15
Some universal algebraic and model theoretic results in computer science....Pages 16-23
Probabilistic analysis of the performance of greedy strategies over different classes of combinatorial problems....Pages 24-33
Moderately exponential bound for graph isomorphism....Pages 34-50
An algebraic definition of attributed transformations....Pages 51-60
Analogies of PAL and COPY....Pages 61-70
Quasi-equational logic for partial algeras....Pages 71-80
Homogeneity and completeness....Pages 81-89
On the error correcting power of pluralism in inductive inference....Pages 90-99
Equality languages and language families....Pages 100-109
Extremal combinatorial problems in relational data base....Pages 110-119
Specifying algebraic data types by domain equations....Pages 120-129
An axiomatization of regular forests in the language of algebraic theories with iteration....Pages 130-136
Fast recognition of rings and lattices....Pages 137-145
A definition of the P = NP-problem in categories....Pages 146-153
Generating graph languages using hypergraph grammars....Pages 154-164
Lower bounds for problems defined by polynomial inequalities....Pages 165-172
What is computable for abstract data types ?....Pages 173-181
On strongly cube-free ω-words generated by binary morphisms....Pages 182-189
On the role of selectors in selective substitution grammars....Pages 190-198
Classes of functions over binary trees....Pages 199-204
Mathematical structures underlying greedy algorithms....Pages 205-209
Some properties of language families generated by commutative languages....Pages 210-217
Isomorphism completeness for some algebraic structures....Pages 218-225
Reducing algebraic tree grammars....Pages 226-233
Rational cone and substitution....Pages 234-243
On the regularity problem of SF-languages generated by minimal linear grammars....Pages 244-249
Co-algebras as machines for the interpretations of flow diagrams....Pages 250-258
Random access machines and straight-line programs....Pages 259-264
On the LBA problem....Pages 265-280
Dynamic algebras of programs....Pages 281-290
The equivalence problem for LL- and LR-regular grammars....Pages 291-300
Context-free languages of infinite words as least fixpoints....Pages 301-310
Remarks on the notion of concurrency relation in the case of systems....Pages 311-320
On the size of conjunctive representations of n-ary relations....Pages 321-327
On subwords of formal languages....Pages 328-333
First order dynamic logic with decidable proofs and workable model theory....Pages 334-340
Elimination of second-order quantifiers for well-founded trees in stationary logic and finitely determinate structures....Pages 341-349
Processes in Petri nets....Pages 350-359
Some algebraic aspects of recognizability and rationality....Pages 360-372
Pebbling and bandwidth....Pages 373-383
On cellular graph-automata and second-order definable graph-properties....Pages 384-393
Extensions of symmetric hom-functors to the Kleisli category....Pages 394-399
A new operation between languages....Pages 400-409
Logical description of computation processes....Pages 410-424
An algorithm to identify slices, with applications to vector replacement systems....Pages 425-432
One pebble does not suffice to search plane labyrinths....Pages 433-444
About the by codings of environments induced posets [ µ z , ≤] and [ℒ z , ≤]....Pages 445-452
The complexity of automata and subtheories of monadic second order arithmetics....Pages 453-466
Tape complexity of word problems....Pages 467-471