DCFS 2015 - Waterloo, Ontario, Canada - June 25-27 2015

Descriptional Complexity of Formal Systems

Photo of University of Waterloo Davis Centre © Ben Babcock.
Used under Creative Commons License.
DCFS 2015 will be held in Waterloo, Ontario, Canada on June 25-27 2015. It will be preceded by a 1-day conference in honour of the 80th birthday of Janusz (John) Brzozowski, June 24 2015.

The workshop is organized by the University of Waterloo, in Waterloo, Ontario, Canada. It is the 17th workshop in a series running annually since 1999.

You can submit a paper here. The papers are limited to 12 pages and should be prepared using the LNCS style.

Program Committee

Plenary Invited Speakers

Thomas Colcombet, LIAFA, Université Denis Diderot - Paris 7, "Non-ambiguity in automata theory"
Abstract: Determinism of devices is a key aspect throughout all of computer science, simply for considerations of efficiency of the implementation. One possible way (among others) to relax this notion is to consider unambiguous machines: nondeterministic machines that have at most one accepting input on each entry.

In this talk, we will investigate the nature of non-ambiguity in automata theory, surveying the cases of standard finite words up to infinite trees, as well as data-words. The goal of this talk will be to show how this notion of unambiguity is so far not well understood, yielding to difficult open questions. In the last part, I will present recent results with Gabriele Puppis and Michal Skrypczak that provide a deep insight in the data-word case.

Rajeev Alur, University of Pennsylvania, "Regular Functions".
Abstract: When should a function mapping strings to strings, or strings to numerical costs, or more generally, strings/trees/infinite-strings to a set of output values with a given set of operations, be considered regular? We have proposed a new machine model of cost register automata, a class of write-only programs, to define such a notion of regularity. The class of regular functions has appealing theoretical properties analogous to regular languages: it is closed under a variety of function transformations, analysis questions such as equivalence and type checking are decidable, and has exact logical and algebraic characterizations. In this talk, I will give an overview of theoretical results as well as emerging applications to program verification and quantitative analysis.

Important Dates

Schedule

Wednesday, June 24 2015

Wednesday will be devoted to a 1-day conference entitled "The Role of Theory in Computer Science", to celebrate the 80th birthday of Janusz (John) Brzozowski.

5 PM - 8 PM: Dinner will be served in the "Fishbowl", DC 1301, held simultaneously with DCFS 2015 registration. Come and meet your fellow conference attendees, as well as students and colleagues of John Brzozowski.

All DCFS talks will be in DC 1304. Invited talks are 45 minutes with 5 minutes for questions. Conributed talks are 25 minutes with 5 minutes for questions. An asterisk denotes that the marked person presented the paper.

Thursday, June 25 2015

8 AM - 9 AM: DCFS 2015 registration. Continental breakfast.
9:00 AM: Welcome, logistics.

9:10 AM: Invited talk by Rajeev Alur, "Regular functions"

10:00 AM: Coffee break in DC 1301

10:30 AM - 12:00 Noon: Contributed papers (state complexity, session 1)
10:30 AM: Nelma Moreira, Giovanni Pighizzini, and Rogério Reis*, "Universal disjunctive concatenation and star"
11:00 AM: Krístina Čevorová, "Square on ideal, closed and free languages"
11:30 AM: Janusz Brzozowski and Marek Szykuła*, "Upper bound on syntactic complexity of suffix-free languages"

12:00 Noon - 2:00 PM: lunch on your own in University plaza

2:00 PM - 3:00 PM: Contributed papers (automata and regular languages, session 1)
2:00 PM: Cezar Campeanu* and Kai Salomaa, "Nondeterministic tree width of regular languages"
2:30 PM: Jacques Duparc* and Kevin Fournier, "A tentative approach for the Wadge-Wagner hierarchy of regular tree languages of index [0,2]"

3:00 PM - 3:30 PM: coffee break in DC 1301

3:30 PM - 5 PM: Contributed papers (automata and regular languages, session 2)
3:30 PM: Kent Kwee* and Friedrich Otto, "On some decision problems for stateless deterministic ordered restarting automata"
4:00 PM: Joey Eremondi, Oscar Ibarra, and Ian McQuillan*, "On the complexity and decidability of some problems involving shuffle"
4:30 PM: Lila Kari, Stavros Konstantinidis, and Steffen Kopecki*, "Transducer descriptions of DNA code properties and undecidability of antimorphic problems"

5:00 PM: Talk on the rules of baseball, for those unfamiliar with the game.

5:30 PM: Conference photo in front of Davis Centre

 

6:50 PM: Buses leave from in front of the Davis Centre for outing to baseball game.

10:30 PM (approx): Buses leave from baseball game to return to Davis Centre and local hotels.

Friday, June 26 2015

9:10 AM: Invited talk by Thomas Colcombet, "Unambiguity in Automata Theory"

10:00 AM - 10:30 AM: Coffee break in DC 1301.

10:30 AM - 12:00 Noon: Contributed papers (state complexity, session 2)
10:30 AM: Matúš Palmovský and Juraj Šebej*, "Star-complement-star on prefix-free languages"
11:00 AM: Alexandros Palioudakis, Da-Jung Cho*, Daniel Goc, Yo-Sub Han, Sang-Ki Ko, and Kai Salomaa, "The state complexity of permutations on finite languages over binary alphabets"
11:30 AM: Peter Mlynárčik, "Complement on free and ideal languages"

12:00 Noon - 2:00 PM: Lunch on your own in University plaza

2:00 PM - 3:30 PM: Contributed papers (quantum and other models)
2:00 PM: Taisia Mischenko-Slatenkova, Alina Vasilieva, Iļja Kucevalovs*, and Rūsiņs Freivalds, "Quantum queries on permutations"
2:30 PM: Marcos Villagra and Tomoyuki Yamakami*, "Quantum state complexity of formal languages"
3:00 PM: Juris Čerņenoks, Jānis Iraids*, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, "Integer complexity: experimental and analytical results II"

3:30 PM: Presentation about DCFS 2016 in Bucharest by Cezar Campeanu

3:45 PM - 4:15 PM: Coffee break in DC 1301

4:15 PM - 5:45 PM: Contributed papers (grammars and groups)
4:15 PM: Sebastian Eberhard and Stefan Hetzl*, "Compressibility of finite languages by grammars"
4:45 PM: Alexander Rubtsov* and Mikhail Vyalyi, "Regular realizability problems and context-free languages"
5:15 PM: Gabriela Asli Rino Nesin* and Rick Thomas, "Groups whose word problem is a Petri net language"

5:45 PM: Open Problem Session

Saturday, June 27 2015

9:00 AM - 10:30 AM: Contributed papers (automata and regular languages, session 3)
9:00 AM: Timothy Ng*, David Rappaport, and Kai Salomaa, "Quasi-distances and weighted finite automata"
9:30 AM: Martin Kutrib and Matthias Wendlandt*, "On simulation costs of unary limited automata"
10:00 AM: Markus Holzer and Sebastian Jakobi*, "On the computational complexity of problems related to distinguishability sets"

10:30 AM - 11:00 AM: Coffee break, DC 1301

11:00 AM - 12:30 PM: Contributed papers (automata and regular languages, session 4)
11:00 AM: Jozef Stefan Jirásek* and Juraj Šebej, "Prefix-free subsets of regular languages and descriptional complexity"
11:30 AM: Hellis Tamm, "Generalization of the double-reversal method of finding a canonical residual finite state automaton"
12:00 Noon: Sabine Broda, António Machiavelo, Nelma Moreira*, and Rogério Reis, "Partial derivative automaton for regular expressions with shuffle"

12:30 PM: Business meeting

1:00 PM: Conference over.

Speaker photos

Rogerio Reis took many photos of the speakers and you can download a tar file by clicking on the link (5 Megs).

Similarly, there is an archive of photos by Peter Mlynárčik (230 Megs).

Registration

To register, go here.

Registration Fees:
Early Bird Registration Fee (Until Friday May 15, 2015) - CDN $200
Regular Registration Fee (Saturday, May 16 to Sunday, June 21, 2015) - CDN $225
On-Site Registration Fee - CDN $250

Housing

Please make your own housing arrangements. If you choose to stay on campus (which is the most inexpensive and convenient choice) you can register through the link above. Otherwise please visit here for other housing suggestions.

Getting Here

Waterloo, Ontario is served by air, rail, bus, and road. Be sure to tell the travel agent you are going to Waterloo, Ontario, Canada and not Waterloo, Iowa, USA!

Air: Region of Waterloo International Airport is a small airport with service from Chicago and Calgary, and is about 20 minutes from the University. Most travelers will fly instead to Pearson International Airport in Toronto.

Airport Transportation - Airways Transit

Airways Transit connects Toronto Pearson airport with the Waterloo area providing 24 hour door-to-door shared ride service. For Toronto Pearson airport transfers we have obtained a reduced conference fare of $79.00 per person, one way, tax included. To receive the reduced fare you must book in advance and your travel dates must correspond to the event dates.
Book online at: http://conferences.airwaystransit.com
Enter booking code: DCFS2015 (enter exactly as shown).
Or by phone 24 hrs: +1 (519) 886 2121 – Identify yourself as an DCFS delegate.

Other possibilities for air travel include John C. Munro International Airport in Hamilton, Ontario (about 1 hour from campus), with flights from Calgary, Orlando, and Miami; Billy Bishop Toronto City Airport in downtown Toronto, with flights from Newark, Chicago, Boston, Washington DC, and many Canadian cities; and Buffalo-Niagara International Airport in Buffalo, NY. If you choose the last option, remember that Canadian residents cannot rent a car in the US and drive into Canada with it!

Train: Both Go Transit and Via Rail offer infrequent service between Toronto and Kitchener. From the Kitchener train station one can take a taxi to the University or to local hotels.

Bus: Greyhound offers about 15 buses a day between Toronto and Kitchener-Waterloo.

Parking

If you are using a car to get to the conference, there is free parking in Lot "N". You will need to print out and display a parking permit on your dashboard, which you can download here. There are four files, one for each day.

A parking map shows you the location of Lot "N". Look for the green "N" on the map. The conference takes place in the Davis Centre, marked "DC" in red on the map. It is a short walk from the parking to the conference building.

Getting Around

While you are in the Kitchener-Waterloo area, you can take local buses (Grand River Transit) to get around. The "7" and "iExpress (200)" buses leave from directly in front of the Davis Centre and go to both downtown Waterloo and downtown Kitchener. Bus tickets can be purchased from the registration desk. At the desk, there are also some bus schedules and bus map you can consult.

Taxis are also another way to get around. Waterloo Taxi (519) 888-7777, United Taxi (519) 888-9999, and City Cabs (519) 747-7777, all serve the Kitchener-Waterloo area.

Local Arrangements Committee

Local Attractions

Excursion

Weather permitting, on Thursday evening, June 25, 2015, there will be an excursion to see the Kitchener Panthers baseball team play a game at 7:30 PM. Typical North American sports food (hot dogs, beer, popcorn, and so forth) will be available at the game. The game will be preceded by a brief lecture -- suitable for those unfamiliar with the game -- explaining the rules of the game.

Proceedings

As in previous years, the proceedings is published by Springer in their Lecture Notes in Computer Science series, Volume 9118.

If you have access to SpringerLink, the following link should take you to the proceedings.

Contact

For more information, send e-mail to dcfs2015@cs.uwaterloo.ca.

Support

 

Financial support is being supplied by the Fields Institute.

This event is also sponsored by the International Federation for Information Processing (IFIP).

DCFS 2016

DCFS 2016 will be held in Bucharest!