
Fundamentals of Computation Theory
Proceedings of the 1981 International FCT-Conference, Szeged, Hungaria, August 24-28, 1981
F. Gecseg(Editor)
Springer (Publisher)
Published on 1. August 1981
Book
Paperback/Softback
XI, 471 pages
978-3-540-10854-2 (ISBN)
Description
Observability and Nerode equivalence in concrete categories.- Some universal algebraic and model theoretic results in computer science.- Probabilistic analysis of the performance of greedy strategies over different classes of combinatorial problems.- Moderately exponential bound for graph isomorphism.- An algebraic definition of attributed transformations.- Analogies of PAL and COPY.- Quasi-equational logic for partial algeras.- Homogeneity and completeness.- On the error correcting power of pluralism in inductive inference.- Equality languages and language families.- Extremal combinatorial problems in relational data base.- Specifying algebraic data types by domain equations.- An axiomatization of regular forests in the language of algebraic theories with iteration.- Fast recognition of rings and lattices.- A definition of the P = NP-problem in categories.- Generating graph languages using hypergraph grammars.- Lower bounds for problems defined by polynomial inequalities.- What is computable for abstract data types ?.- On strongly cube-free ?-words generated by binary morphisms.- On the role of selectors in selective substitution grammars.- Classes of functions over binary trees.- Mathematical structures underlying greedy algorithms.- Some properties of language families generated by commutative languages.- Isomorphism completeness for some algebraic structures.- Reducing algebraic tree grammars.- Rational cone and substitution.- On the regularity problem of SF-languages generated by minimal linear grammars.- Co-algebras as machines for the interpretations of flow diagrams.- Random access machines and straight-line programs.- On the LBA problem.- Dynamic algebras of programs.- The equivalence problem for LL- and LR-regular grammars.- Context-free languages of infinitewords as least fixpoints.- Remarks on the notion of concurrency relation in the case of systems.- On the size of conjunctive representations of n-ary relations.- On subwords of formal languages.- First order dynamic logic with decidable proofs and workable model theory.- Elimination of second-order quantifiers for well-founded trees in stationary logic and finitely determinate structures.- Processes in Petri nets.- Some algebraic aspects of recognizability and rationality.- Pebbling and bandwidth.- On cellular graph-automata and second-order definable graph-properties.- Extensions of symmetric hom-functors to the Kleisli category.- A new operation between languages.- Logical description of computation processes.- An algorithm to identify slices, with applications to vector replacement systems.- One pebble does not suffice to search plane labyrinths.- About the by codings of environments induced posets [µ z, ?] and [?z, ?].- The complexity of automata and subtheories of monadic second order arithmetics.- Tape complexity of word problems.
More details
Series
Edition
1981 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XI, 471 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 27 mm
Weight
733 gr
ISBN-13
978-3-540-10854-2 (9783540108542)
DOI
10.1007/3-540-10854-8
Schweitzer Classification
Content
Observability and Nerode equivalence in concrete categories.- Some universal algebraic and model theoretic results in computer science.- Probabilistic analysis of the performance of greedy strategies over different classes of combinatorial problems.- Moderately exponential bound for graph isomorphism.- An algebraic definition of attributed transformations.- Analogies of PAL and COPY.- Quasi-equational logic for partial algeras.- Homogeneity and completeness.- On the error correcting power of pluralism in inductive inference.- Equality languages and language families.- Extremal combinatorial problems in relational data base.- Specifying algebraic data types by domain equations.- An axiomatization of regular forests in the language of algebraic theories with iteration.- Fast recognition of rings and lattices.- A definition of the P = NP-problem in categories.- Generating graph languages using hypergraph grammars.- Lower bounds for problems defined by polynomial inequalities.- What is computable for abstract data types ?.- On strongly cube-free ?-words generated by binary morphisms.- On the role of selectors in selective substitution grammars.- Classes of functions over binary trees.- Mathematical structures underlying greedy algorithms.- Some properties of language families generated by commutative languages.- Isomorphism completeness for some algebraic structures.- Reducing algebraic tree grammars.- Rational cone and substitution.- On the regularity problem of SF-languages generated by minimal linear grammars.- Co-algebras as machines for the interpretations of flow diagrams.- Random access machines and straight-line programs.- On the LBA problem.- Dynamic algebras of programs.- The equivalence problem for LL- and LR-regular grammars.- Context-free languages of infinitewords as least fixpoints.- Remarks on the notion of concurrency relation in the case of systems.- On the size of conjunctive representations of n-ary relations.- On subwords of formal languages.- First order dynamic logic with decidable proofs and workable model theory.- Elimination of second-order quantifiers for well-founded trees in stationary logic and finitely determinate structures.- Processes in Petri nets.- Some algebraic aspects of recognizability and rationality.- Pebbling and bandwidth.- On cellular graph-automata and second-order definable graph-properties.- Extensions of symmetric hom-functors to the Kleisli category.- A new operation between languages.- Logical description of computation processes.- An algorithm to identify slices, with applications to vector replacement systems.- One pebble does not suffice to search plane labyrinths.- About the by codings of environments induced posets [µ z, ?] and [?z, ?].- The complexity of automata and subtheories of monadic second order arithmetics.- Tape complexity of word problems.