Preface of Special Issue on Theoretical Aspects of Computer Science
- PDF / 187,430 Bytes
- 3 Pages / 439.37 x 666.142 pts Page_size
- 5 Downloads / 263 Views
Preface of Special Issue on Theoretical Aspects of Computer Science Christoph Dürr · Thomas Schwentick
Published online: 21 April 2013 © Springer Science+Business Media New York 2013
This special issue contains nine articles which are based on extended abstracts that were presented at the 28th Symposium on Theoretical Aspects of Computer Science (STACS), which was held at Technische Universität Dortmund, Germany, March 10– 12, 2011. These extended abstracts were among the top papers of those that were chosen for presentation at STACS 2011 in a highly competitive peer-review process (after which only 54 papers out of 271 submission were accepted). Compared with the original extended abstracts the articles have been strongly revised and extended by full proofs and additional results. They underwent a further rigorous reviewing process, following the TOCS standard, completely independent from the selection process of STACS 2011. Three articles are about formal languages. The first two investigate size issues for automata and (extended) regular expressions, respectively, while the third one investigates the syntactic monoids of regular languages over infinite alphabets. The article Series Parallel Digraphs with Loops by Stefan Gulan studies the question which kinds of finite automata can be translated into regular expressions of linear size. It gives a very comprehensive answer to this question by showing that such linear translations are possible from automata with a certain underlying graph structure, series parallel loop graphs, into regular expressions and vice versa. Furthermore it characterizes this graph class (within the class of hammocks, i.e., all graphs with dis-
C. Dürr CNRS, Université Pierre et Marie Curie, LIP6, équipe Recherche Opérationnelle, case 169, 4 place Jussieu, 75252 Paris Cedex 05, France e-mail: [email protected] T. Schwentick () TU Dortmund University, Computer Science 1, 44221 Dortmund, Germany e-mail: [email protected]
124
Theory Comput Syst (2013) 53:123–125
tinguished source and sink graphs, in which all nodes are on a path from source to sink) in terms of a number of forbidden minors. In Extended Regular Expressions: Succinctness and Decidability, Dominik D. Freydenberger studies an extension of regular expressions by variables (or: backreferences) that is widely used in practical contexts, e.g., in PERL and Python. The article shows the surprising fact that the extension has a dramatic effect on the size of regular expressions: there is no computable function that bounds the minimal size of a classical regular expressions in terms of the size of the smallest extended regular expressions. This holds even if only one variable is used and bound only once in the expression. The article further shows that many static analysis tasks, for example, deciding whether an expression denotes the set of all strings, are undecidable. The article Nominal Monoids by Mikołaj Boja´nzyk connects two fields of language theory. Regular languages can be represented by their syntactic monoi
Data Loading...
