Two new papers that I have co-authored are available on Arxiv:
"Detecting Unary Patterns" (SPIRE 2017, new title: Detecting One-Variable Patterns), written together with Dmitry Kosolobov and Dirk Nowotka, proposes an efficient algorithm that locates in a text all the instances of a pattern that includes strings of letters and one-repeated variable (that can be replaced, uniformly, by any string of letters); the repeated variable can appear also reveresed.
This paper was started last year, when Dmitry visited us in Kiel, and put on Arxiv a while ago. However, since then it went through many changes and reached the current (nicer) form. It improves some of the algorithms presented in the papers from STACS 2014 (written together with Pawel Gawrychowski and Dirk Nowotka) and STACS 2015 (written together with Markus Schmid, Robert Mercas, and Henning Fernau).
"The Hardness of Solving Simple Word Equations" (MFCS 2017), written together with Joel Day and Dirk Nowotka, shows that the satisfiability of some very simple word equations is NP-complete. In word equations, we equate two strings (called sides) that contain variables and strings of letters. We want to check whether there is a way to assign (uniformly) strings of letters to the variables, such that the two sides become equal. In our simple case, each variable occurs at most once in each side and the order of the variables occurring in both sides is the preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the shortest solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. Finally, we also show that a related class of simple word equations, that generalises one-variable equations, is in P.
This paper was the result of the work Joel and I started recently on word equations and closes some of the open problems left in the paper from DLT 2016, written together with Markus Schmid and Dirk Nowotka. The paper published on Arxiv is a "cleaner" version of the paper we submitted, with some type-o-s and imprecisions fixed.
Both these papers are part of my current DFG-research project, on algorithms and combinatorics of words.
Still Kiel
In 2011 I started working in Kiel, as a researcher in the Dependable Systems Group lead by Dirk Nowotka. In 2012 I decided to stay in the same group, while working on my own DFG-funded project. Recently, my research (on algorithms and combinatorics on words) was funded for another two years by the DFG, so I will continue working in the Kiel University at least until October 31st, 2018.
Computability in Europe - Chair of the Steering Committee
Starting 2013 I've been a member of the Computability in Europe conference series Steering Committee. This year, I was asked and I agreed to run to become Chair of this Committee. Consequently, at CiE 2016, I was elected and officially named on this position.
This is a big responsibility and I hope I will be able to continue in the same line the impressive work of my predecessors, Benedikt Löwe and Arnold Beckmann. Luckily, I am quite confident that the first two conferences during my term will be successful: CiE 2017 in Turku, and CiE 2018 in Kiel.
As CiE-SC Chair I also became member of the Executive Committee of the Association CiE and the representative of CiE in the board of the European Association for Computer Science Logic - EACSL.
This is a big responsibility and I hope I will be able to continue in the same line the impressive work of my predecessors, Benedikt Löwe and Arnold Beckmann. Luckily, I am quite confident that the first two conferences during my term will be successful: CiE 2017 in Turku, and CiE 2018 in Kiel.
As CiE-SC Chair I also became member of the Executive Committee of the Association CiE and the representative of CiE in the board of the European Association for Computer Science Logic - EACSL.
Conferences 2016 and 2017
Here is a short update on a series of events I was or currently am involved in.
In the period October 4-10, 2016, our group is organising the Theory Days of the Automata and Formal Languages and, respectively, the Logic Group of the German Informatics Society. All the information can be found here. A major highlight of our program is the common workshop of the two groups, with five very interesting invited talks.
I served in the Program Committee of the 23rd edition of the International Symposium on String Processing and Information Retrieval SPIRE 2016. The conference will take place in Beppu, Japan, October 18-20, 2016. The lists of invited speakers and accepted papers look really good, and the conference is accompanied by several very interesting satellite events. Please consider participating to SPIRE 2016.
I will also be part of the Program Committee of the 34th International Symposium on Theoretical Aspects of Computer Science STACS 2017, one of the major theoretical computer science conferences in Europe. The conference takes place in Hannover, in Germany, in March 2017. The deadline is only weeks away, on September 25. Please submit your best papers to STACS!
Finally, I will also serve in the Program Committee of the 13th Computability in Europe conference, CiE 2017. The conference will take place in Turku, Finland, in June 2017. More details on this will come soon.
In the period October 4-10, 2016, our group is organising the Theory Days of the Automata and Formal Languages and, respectively, the Logic Group of the German Informatics Society. All the information can be found here. A major highlight of our program is the common workshop of the two groups, with five very interesting invited talks.
I served in the Program Committee of the 23rd edition of the International Symposium on String Processing and Information Retrieval SPIRE 2016. The conference will take place in Beppu, Japan, October 18-20, 2016. The lists of invited speakers and accepted papers look really good, and the conference is accompanied by several very interesting satellite events. Please consider participating to SPIRE 2016.
I will also be part of the Program Committee of the 34th International Symposium on Theoretical Aspects of Computer Science STACS 2017, one of the major theoretical computer science conferences in Europe. The conference takes place in Hannover, in Germany, in March 2017. The deadline is only weeks away, on September 25. Please submit your best papers to STACS!
Finally, I will also serve in the Program Committee of the 13th Computability in Europe conference, CiE 2017. The conference will take place in Turku, Finland, in June 2017. More details on this will come soon.
WORDS 2015 in Kiel - Call for Participation
10th International Conference on WORDS 2015 (the main conference dedicated to the study of combinatorics on words) takes place in Kiel from September 14 to September 17, 2015. We invite everyone who is interested in the topics and program of WORDS 2015 to register for the conference. More details are given below.
IMPORTANT DATES:
Starting Date of the Conference: September 14, 2pm.
Ending Date of the Conference: September 17, 5pm
IMPORTANT INFORMATION is to be found at the following links:
Registration Web-site, Information for Participants, Local Info.
SCHEDULE:
Invited Speakers:
Jörg Endrullis (Amsterdam), Markus Lohrey (Siegen), Jean Néraud (Rouen), Dominique Perrin (Paris), Michaël Rao (Lyon), Thomas Stoll (Nancy).
See also the list of contributed talks as well as the tentative schedule (a more detailed schedule will be published soon).
In the first day of the conference, an Open Problems (in Combinatorics on Words and Stringology) session will also be organized.
SOCIAL PROGRAM:
The social program of the conference includes an excursion and the conference dinner (supported by the organizers), as well as a couple of informal dinners.
About WORDS:
WORDS is a biannual international conference covering the mathematical theory of words (sequences of symbols) from all points of view: combinatorial, algebraic, algorithmic, as well as its applications to biology, linguistics, physics, and others. The previous WORDS conferences have taken place in Rouen (1997, 1999), Palermo (2001), Turku (2003, 2013), Montreal (2005), Marseille (2007), Salerno (2009), Prague (2011). This year we celebrate the 10th edition of WORDS.
A refereed proceedings volume, including extended abstracts of the invited talks as well as original contributions, that fulfil the high quality standards required by a formal publication in computer science, will be published in Springer's Lecture Notes in Computer Science series. In addition, a local proceedings volume will be published, including, in the spirit of mathematics conferences, a series of less formal contributions informing on current research and work in progress.
The PROGRAM COMMITTEE, that selected the talks to be presented at the conference, consists of: Maxime Crochemore (London), Juhani Karhumäki (Turku), Dirk Nowotka (Kiel - chair), Stepan Holub (Prague), Antonio Restivo (Palermo), Manfred Kufleitner (Stuttgart), Gad Landau (Haifa), Michel Rigo (Liege), James Currie (Winnipeg), Mikhail V. Volkov (Ekaterinburg), Wojciech Plandowski (Warsaw), Luca Zamboni (Lyon).
QUESTIONS regarding the conference can be addressed to the organizers (Dirk Nowotka, Florin Manea) via E-mail:
info[at]words2015[dot]uni-kiel[dot]de
IMPORTANT DATES:
Ending Date of the Conference: September 17, 5pm
IMPORTANT INFORMATION is to be found at the following links:
Registration Web-site, Information for Participants, Local Info.
SCHEDULE:
Invited Speakers:
Jörg Endrullis (Amsterdam), Markus Lohrey (Siegen), Jean Néraud (Rouen), Dominique Perrin (Paris), Michaël Rao (Lyon), Thomas Stoll (Nancy).
See also the list of contributed talks as well as the tentative schedule (a more detailed schedule will be published soon).
In the first day of the conference, an Open Problems (in Combinatorics on Words and Stringology) session will also be organized.
SOCIAL PROGRAM:
The social program of the conference includes an excursion and the conference dinner (supported by the organizers), as well as a couple of informal dinners.
About WORDS:
WORDS is a biannual international conference covering the mathematical theory of words (sequences of symbols) from all points of view: combinatorial, algebraic, algorithmic, as well as its applications to biology, linguistics, physics, and others. The previous WORDS conferences have taken place in Rouen (1997, 1999), Palermo (2001), Turku (2003, 2013), Montreal (2005), Marseille (2007), Salerno (2009), Prague (2011). This year we celebrate the 10th edition of WORDS.
A refereed proceedings volume, including extended abstracts of the invited talks as well as original contributions, that fulfil the high quality standards required by a formal publication in computer science, will be published in Springer's Lecture Notes in Computer Science series. In addition, a local proceedings volume will be published, including, in the spirit of mathematics conferences, a series of less formal contributions informing on current research and work in progress.
The PROGRAM COMMITTEE, that selected the talks to be presented at the conference, consists of: Maxime Crochemore (London), Juhani Karhumäki (Turku), Dirk Nowotka (Kiel - chair), Stepan Holub (Prague), Antonio Restivo (Palermo), Manfred Kufleitner (Stuttgart), Gad Landau (Haifa), Michel Rigo (Liege), James Currie (Winnipeg), Mikhail V. Volkov (Ekaterinburg), Wojciech Plandowski (Warsaw), Luca Zamboni (Lyon).
QUESTIONS regarding the conference can be addressed to the organizers (Dirk Nowotka, Florin Manea) via E-mail:
info[at]words2015[dot]uni-kiel[dot]de
Subscribe to:
Posts (Atom)