Organized by: Research Group on Mathematical Linguistics (GRLMC) from Rovira i Virgili University.

Formal Languages and Applications (FSFLA 2011)

(formerly International PhD School in Formal Languages and Applications)

News- Call
- ClassSchedule
- CourseDescription
- Registration
- Accommodation
- TravelInformation
- Venue
- Students
- Slides
- Contact

**Tarragona, Spain, October 31 - November 4, 2011 **

Franz Baader (Technische Dresden), intermediate, 6 hours

Description Logics (DLs) are a successful family of logic-based knowledge representation formalisms, which can be used to represent the conceptual knowledge of an application domain in a structured and formally well-understood way. They are employed in various application domains, such as natural language processing, configuration, and databases, but their most notable success so far is the adoption of the DL-based language OWL as standard ontology language for the semantic web.

This tutorial concentrates on designing and analyzing reasoning procedures for DLs. After a short introduction and a brief overview of the research of the last 20 years, it will on the one hand present approaches for reasoning in expressive DLs, which are the foundation for reasoning in OWL DL. On the other hand, it will consider tractable reasoning in the more light-weight DL EL, which is employed in bio-medical ontologies, and which is the foundation for the OWL 2 profile OWL 2 EL.

References:

- Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, editors,
*The Description Logic Handbook: Theory, Implementation, and Applications*. Cambridge University Press, 2003. - Franz Baader.
*Description Logics*. In Reasoning Web: Semantic Technologies for Information Systems, 5th International Summer School 2009, volume 5689 of Lecture Notes in Computer Science, pages 1-39. Springer–Verlag, 2009. - Franz Baader, Carsten Lutz, and Anni-Yasmin Turhan.
*Small is again Beautiful in Description Logics*. KI – Künstliche Intelligenz, 24(1): 25–33, April 2010.

Manfred Droste (Leipzig), introductory/advanced, 8 hours

A weighted automaton is a classical nondeterministic automaton in which each transition carries a weight describing e.g. the resources used for its execution, the length of time needed, or its reliability. We will first describe basic results from the theory of such quantitative automata. In the second part, we develop syntax and semantics of a weighted logic; the semantics counts 'how often' a formula is true. Then we show that the behaviors of weighted automata are precisely the functions definable by sentences of our weighted logic. This extends Büchi's classical result relating (unweighted) finite automata and monadic second order logic to a quantitative setting.

References:

- M. Droste and P. Gastin:
*Weighted automata and weighted logics*, in Handbook of Weighted Automata (M. Droste, W. Kuich, H. Vogler, eds.), chapter 5, Springer, 2009. - J. Sakarovitch:
*Rational and recognisable power series*, in Handbook of Weighted Automata (M. Droste, W. Kuich, H. Vogler, eds.), chapter 4, Springer, 2009.

Venkatesan Guruswami (Carnegie Mellon), intermediate, 6 hours

Constraint satisfaction is a versatile paradigm for specifying problems in various areas of computer science. An instance of a constraint satisfaction problem (CSP) consists of a finite set of variables, a domain over which the variables are to be assigned values, and a finite collection of constraints which place local restrictions on the values the variables may take in relation to the others. CSPs capture several fundamental problems like SAT, graph and hypergraph coloring, etc. The optimization problem corresponding to a CSP consists of finding an assignment that satisfies as many constraints of the CSP instance as possible.

For most CSPs, including many for which satisfiability can be decided in polynomial time, the associated optimization problem is NP-hard. To cope with this intractability, the approximate solvability of CSPs by polynomial time algorithms and limits on the performance guarantees ofsuch algorithms have been extensively studied. For many problems we now have good approximation algorithms as well as strong (or even tight) complementary hardness results. This series of lectures is an advanced introduction to this subject. Its aim will be to discuss a few central algorithmic and hardness results concerning approximability of CSPs, and provide a peek into some its exciting research frontiers.

On the algorithmic side, linear and semidefinite programming relaxations have been the most successful tool for designing good approximation algorithms for CSPs. We will discuss how to write canonical LP and SDP relaxations for CSPs, and see some examples of algorithms based on them and the non-trivial approximation ratios they are able to guarantee.

On the hardness side, we will review the PCP theorem and state some strong (sometimes even optimal) non-approximability results obtained by reductions from a CSP called Label Cover. We will discuss the notion of Dictatorship testing and its utility in the context of proving non-approximability results via reductions from a special form of Label Cover called Unique Games. For illustration, we will discuss a tight hardness result for the Boolean CSP consisting of 3-variable linear equations.

We will then touch upon recent progress based on the "Unique Games conjecture" which is able to identify the approximation threshold of every CSP as the integrality gap of a natural semidefinite programming relaxation, using the simplest binary CSP, MaxCut, for illustration. Time permitting, we may draw a parallel with the algebraic dichotomy conjecture in the world of CSP dichotomy, and comment how --- under the Unique Games conjecture --- the approximability of a CSP is precisely governed by the existence of non-trivial approximate polymorphisms.

No formal prerequisites beyond undergraduate algorithms, complexity, and probability is required, but the material will be challenging and fast paced, so mathematical maturity will be of significant help.

References: (some of the material is based on recent research, and no textbook covers all the topics to be discussed. See two references below, though we won't follow either one of them in the lectures. During the lectures at the school, some slides or notes may be made available to the students)

- Vijay Vazirani,
*Approximation Algorithms*Springer, 2001 (is a great text covering all the classic algorithms, as well as some of the basic PCP-based hardness results). - Subhash Khot,
*A survey on "Inapproximability results via Long Code based PCPs"*, ACM SIGACT News, 36(2), June 2005, http://portal.acm.org/citation.cfm?id=1067318.

Tao Jiang (California Riverside), intermediate, 6 hours

A string x is said to be incompressible if the shortest algorithmic description of x (which is also called the Kolmogorov complexity of x) has length at least |x|. Strings that are incompressible are patternless since a pattern could be used to reduce the description length. The incompressibility method is an elementary yet powerful proof technique based on the fact that most strings are incompressible. It has been used successfully in many areas including lower bounds for computational models, formal language and automata theory, combinatorics, and average-case analysis of algorithms.

In this short course, we first give a brief exposition of Kolmogorov complexity and the incompressibility method, and then focus on some representative applications of the method in average-case analysis and proving lower bounds. The examples considered here include some well-known sorting algorithms such as Heapsort and Shellsort as well as string matching automata, and the proofs presented are so elementary that they can be easily understood by anyone with basic knowledge of data structures and algorithms.

References:

- M. Li and P. Vitanyi.
*An Introduction to Kolmogorov Complexity and its Applications.*Springer-Verlag, New York, 2nd Edition, 1997. - T. Jiang and M. Li.
*On the approximation of shortest common supersequences and longest common subsequences.*SIAM Journal on Computing, 24(5): 1122-1139, 1995. - T. Jiang and M. Li.
*k one-way heads cannot do string-matching.*Journal of Computer and System Sciences, 53(3): 513-524, 1996. - T. Jiang, J.I. Seiferas and P. Vitanyi.
*Two heads are better than two tapes.*Journal of the ACM, 44(2): 237-256, 1997. - T. Jiang, M. Li, and P. Vitanyi.
*New applications of the incompressibility method.*Computer Journal, 42(4): 287-293, 1999. - T. Jiang, M. Li and P. Vitanyi.
*A lower bound on the average-case complexity of Shellsort.*Journal of the ACM, 47(5): 905-911, 2000. - H. Buhrman, T. Jiang, M. Li, and P. Vitanyi.
*New applications of the incompressibility method: Part II.*Theoretical Computer Science, 235(1): 59-70, 2000. - T. Jiang, M. Li and P. Vitanyi.
*Average-case analysis of algorithms using Kolmogorov complexity.*Journal of Computer Science and Technology, 15(5): 402-408, 2000. - T. Jiang, M. Li and P. Vitanyi.
*The average-case area of Heilbronn-type triangles.*Random Structures and Algorithms, 20(2): 206-219, 2002. - B. Lucier, T. Jiang and M. Li.
*Average-case analysis of Quicksort and Binary Insertion Tree height using incompressibility.*Information Processing Letters, 103(2): 45-51, 2007.

Helmut Seidl (Technische München), intermediate, 6 hours

This course gives a gentle introduction to various classes of macro tree transducers. It illustrates how these can be used as a formal model for XML transformations. We show how basic constructions for tree transducers allow to derive practical algorithms for type checking tree transformations. Here, a type is given by a regular set of admissible terms. Type checking then verifies that a given transformation will always produce legal outputs whenever it is applied to legal inputs.

If there is time, then in a second part we will discuss unique normal-forms for particular simple classes of deterministic tree transducers. These normal forms can be considered as generalizations of minimal automata as wellknown for deterministic finite automata on strings or trees to tree transducers. Such normal forms may be considered as the first step of developing algorithms to automatically learn transductions from examples.

References:

- Sebastian Maneth, Alexandru Berlea, Thomas Perst, Helmut Seidl,
*XML type checking with macro tree transducers*. In Chen Li (Ed.): Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, 2005: 283-294. - Sebastian Maneth, Thomas Perst, Helmut Seidl,
*Exact XML Type Checking in Polynomial Time*. In Thomas Schwentick, Dan Suciu (Eds.): Database Theory - ICDT 2007, 11th International Conference, LNCS 4353. Springer, 2007: 254-268. - Joost Engelfriet, Sebastian Maneth, Helmut Seidl,
*Deciding equivalence of top-down XML transformations in polynomial time*. Journal of Computer and System Sciences 75(5): 271-286 (2009). - Sylvia Friese, Helmut Seidl, Sebastian Maneth,
*Minimization of Deterministic Bottom-Up Tree Transducers*. In Yuan Gao, Hanlin Lu, Shinnosuke Seki, Sheng Yu (Eds.): Developments in Language Theory, 14th International Conference, DLT 2010, LNCS 6224. Springer, 2010: 185-196.

Alan Selman (Buffalo), intermediate, 10 hours

In this course we study the benefits of adding randomness to computations. We treat randomness as a resource. Probabilistic algorithms allow computations to depend on the outcomes of an ideal random generator (i.e. on unbiased coin tosses). They can be classified by classifying the languages they are defined to accept. Important computational problems that seem to be infeasible by ordinary deterministic computations have efficient solutions using probabilistic algorithms. Such algorithms can be easily implemented, and fast and reliable solutions to otherwise difficult problems are then possible. There is a cost to this added efficiency, however, in that probabilistic algorithms do sometimes make errors.

References:

- S. Homer and A. Selman.
*Computability and Complexity Theory*. Texts in Computer Science. Springer, New York, 2001. - J. Gill.
*Computational complexity of probabilistic Turing machines*. SIAM Journal on Computing, 6(4): 675-695, Dec. 1977. - L. Adleman and K. Manders.
*Reducibility, randomness, and intractability*. In Proceedings of the Ninth Annual ACM Symposium on Theory of Computing: 151-163, 1977. - J. Carter and M. Wegman.
*Universal classes of hash functions*. Journal of Computer and System Sciences, 18: 143-154, 1979. - M. Sipser.
*A complexity theoretic approach to randomness*. In Proceedings of the Fifteenth ACM Symposium on Theory of Computing: 330-335, 1983. - U. Schoening.
*A low and a high hierarchy within NP*. Journal of Computer and System Sciences, 27: 14-28, 1983. - U. Schoening.
*Graph isomorphism is in the low hierarchy*. Journal of Computer and System Sciences, 37(3): 312-323, 1988. - C. Lautemann.
*BPP and the polynomial hierarchy*. Information Processing Letters, 17: 215-217, November 1983.

Jeffrey Shallit (Waterloo), intermediate, 6 hours

A sequence (*a*_{n})_{{n ≥ 0}} is said to be *k*-automatic if it can be generated by a finite automaton with output mapping *f* as follows: the automaton accepts as input the base-*k* expansion of *n*, in processing the input it ends up in a state *p*, and *f*(*p*) = *a*_{n}. The class of automatic sequences includes such important examples as the Thue-Morse and Rudin-Shapiro sequences.

Many interesting questions about such sequences are mechanically decidable. This includes, for example, whether the sequence contains repetitions of order *r* ("*r*^{th} powers"), whether the sequence is recurrent (every factor occurs infinitely often), etc. Furthermore, we can also mechanically enumerate related sequences, such as the number of distinct factors of length *n*.

In this short course, this material will be covered. No previous experience with automatic sequences will be assumed.

References:

- Jean-Paul Allouche and Jeffrey Shallit,
*Automatic Sequences*, Cambridge University Press, 2003. - Jean-Paul Allouche, Narad Rampersad, and Jeffrey Shallit,
*Periodicity, repetitions, and orbits of an automatic sequence*, Theoretical Computer Science 410 (2009), 2795-2803. - Emilie Charlier, Narad Rampersad, and Jeffrey Shallit,
*Enumeration and decidable properties of automatic sequences*, to appear, DLT 2011. Available at http://arxiv.org/abs/1102.3698. - Jeffrey Shallit,
*The critical exponent is computable for automatic sequences*, to appear, WORDS 2011. Available at http://arxiv.org/abs/1104.2303.