Juhani Karhumäki

Alexander Okhotin

Helmut Jürgensen

This book constitutes the refereed proceedings of the 16th International Conference on Descriptional Complexity of Formal Systems, DCFS 2014, held in Turku, Finland, in August 2014. The 27 full papers presented were carefully reviewed and selected from 35 submissions. The conference dealt with the following topics: Automata, grammars, languages and other formal systems; various modes of operation and complexity measures; trade-offs between computational models and modes of operation; succinctness of description of objects, state explosion-like phenomena; circuit complexity of Boolean functions and related measures; resource-bounded or structure-bounded environments; frontiers between decidability and undecidability; universality and reversibility; structural complexity; formal systems for applications (e.g., software reliability, software and hardware testing, modeling of natural languages); nature-motivated (bio-inspired) architectures and unconventional models of computing; complexity aspects of combinatorics on words; Kolmogorov complexity.

16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014, Proceedings

Descriptional Complexity of Formal Systems

Gerard Lallement

Hanns J. Weinert

Contents: B.P. Alimpic, D.N. Krgovic: Some Congruences on Regular Semigroups.- J. Almeida: On Pseudovarieties of Monoids.- K. Culik II, J. Karhumäki: Systems of Equations over a Finitely Generated Free Monoid Having an Effectively Findable Equivalent Finite Subsystem.- M. Demlová, V. Koubek: Minimal Congruences and Coextensions in Semigroups.- V. Fleischer, U. Knauer: Endomorphisms Monoids of Acts are Wreath Products of Monoids With Small Categories.- J. Fountain: Free Right H-Adequate Semigroups.- G.A. Freiman, B.M. Schein: Group and Semigroup Theoretic Considerations Inspired by Inverse Problems of the Additive Number Theory.- S.M. Goberstein: Correspondences of Semigroups.- P. Goralcik, V. Koubek: On Universality of Extensions.- U. Hebisch, L.C.A. van Leeuwen: On Additively and Multiplicatively Idempotent Semirings and Partial Orders.- P.R. Jones: Congruence Semimodular Varieties of Semigroups.- M. Katsura, H.J. Shyr: Decomposition of Languages into Disjunctive Outfix Codes.- G. Lallement: Some Algorithms for Semigroups and Monoids Presented by a Single Relation.- W. Lex: Remarks on Acts and the Lattice of Their Torsion Theories.- D.Lippert, W. Thomas: Relativized Star-Free Expresssions, First-order Logic, and a Concatenation Game.- E.S. Ljapin: Semigroup Extensions of Partial Groupoids.- K. Madlener, F. Otto: On Groups Having Finite Monadic Church-Rosser Presentations.- R.B. McFadden: Automated Theorem Proving Applied to the Theory of Semigroups.- A. Nagy: Subdirectly Irreducible WE-2 Semigroups with Globally Idempotent Core.- J. Okninski: Commutative Monoid Rings with Krull Dimension.- M. Petrich, G. Thierrin: Languages Induced by Certain Homomorphisms of a Free Monoid.- G. Pollák: Infima in the Power Set of Free Semigroups.- N.R. Reilly: Update on the Problems in 'Inverse Semigroups' by M. Petrich.- K.D. Schmidt: Minimal Clans: a Class of Ordered Partial Semigroups Including Boolean Rings and Lattice-ordered Groups.- J.-C. Spehner: Les systèmes entiers d'équations sur un alphabet de 3 variables.- M.B. Szendrei: A New Interpretation of Free Orthodox and Generalized Inverse *-semigroups.- P.G. Trotter: Varieties of Completely Regular Semigroups: Their Injectives.- H.J. Weinert: Generalized Semialgebras Over Semirings.

Helmut Jürgensen

About

Books

Join the club