Photo of University of Waterloo Davis Centre © Ben Babcock.
Used under Creative Commons License.
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.
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.
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.
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.
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
10:30 AM - 11:00 AM: Coffee break, DC 1301
11:00 AM - 12:30 PM: Contributed papers (automata and regular languages,
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.
Similarly, there is an archive of photos by Peter Mlynárčik (230 Megs).
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
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
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.
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.
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.
If you have access to SpringerLink, the following link should take you to the proceedings.
Financial support is being supplied by the Fields Institute.
This event is also sponsored by the International Federation for Information Processing (IFIP).