Regular realizability problems and context-free languages
The 21st International Conference on Developments in Language Theory (DLT 2017) was organized by the Department of Mathematics of the University of Liège, Belgium, during August 7–11, 2017.
The DLT conference series is one of the major international conference series in language theory and related areas. The DLT conference was established by G. Rozenberg and A. Salomaa in 1993. Since then, the DLT conferences have been held on every odd year: Magdeburg, Germany (1995), Thessaloniki, Greece (1997), Aachen, Germany (1999), and Vienna, Austria (2001). Since 2001, a DLT conference has been taking place in Europe on every odd year and outside Europe on every even year. The locations of DLT conferences since 2002 were: Kyoto, Japan (2002), Szeged, Hungary (2003), Auckland, New Zealand (2004), Palermo, Italy (2005), Santa Barbara, California, USA (2006), Turku, Finland (2007), Kyoto, Japan (2008), Stuttgart, Ger- many (2009), London, Ontario, Canada (2010), Milan, Italy (2011), Taipei, Taiwan (2012), Marne-la-Vallée, France (2013), Ekaterinburg, Russia (2014), Liverpool, UK (2015), and Montréal, Canada (2016). This 21st edition was thus the first time that the conference was organized in Belgium.
The series of International Conferences on Developments in Language Theory provides a forum for presenting current developments in formal languages and auto- mata. Its scope is very general and includes, among others, the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphs, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and anal- ysis; polyominoes and bidimensional patterns; cryptography; concurrency; cellular automata; bio-inspired computing; quantum computing.
The papers submitted to DLT 2017 were from 19 countries including Belgium, Canada, Czech Republic, France, Germany, Hungary, India, Italy, Japan, The Netherlands, Poland, Portugal, Republic of Korea, Russia, Slovakia, South Africa, Thailand, and USA.
This volume of Lecture Notes in Computer Science contains the papers that were presented at DLT 2017. There were 47 qualified submissions. Each submission was handled by three Program Committee members and received at least three reviews. The committee decided to accept 24 papers. The volume also includes the abstracts or full papers of the invited speakers:
– Véronique Bruyère (University of Mons): “Computer-Aided Synthesis: A Game-Theoretic Approach”
– Sergei Kitaev (University of Strathclyde): “A Comprehensive Introduction to the Theory of Word-Representable Graphs”
– Robert Mercaş (Loughborough University): “On the Number of Factors with Maximal-Exponent in Words”
– Balasubramanian Ravikumar (Sonoma State University): “Language Approxima- tion: Asymptotic and Non-asymptotic Results”
– Eric Rowland (Hofstra University): “Binomial Coefficients, Valuations, and Words”
– Michał‚ Skrzypczak (University of Warsaw): “Connecting Decidability and Com- plexity for MSO Logic”
We warmly thank all the invited speakers and all the authors of the submitted papers. We also would like to thank all the members of the Program Committee and all the external reviewers (listed in the proceedings) for their excellent work in evaluating the papers. We finally thank all the members of the Organizing Committee at the University of Liège.
The organization of the conference benefited from the support of the F.R.S.-FNRS, the Faculty of Sciences of the University of Liège and the Research Unit in Mathe- matics of the University of Liège. The reviewing process was organized using the EasyChair conference system created by Andrei Voronkov. We would like to acknowledge that this system greatly helped to improve the efficiency of the committee work. Finally, we wish to thank the editors of the Lecture Notes in Computer Science series and Springer.
Émilie Charlier Julien Leroy Michel Rigo
Рассматриваются задачи регулярной реализуемости, которые состоят в проверке непустоты пересечения регулярного языка на входе задачи и фиксированного языка (фильтра), который явля- ется параметром задачи. В данной работе изучается алгоритмиче- ская сложность задач регулярной реализуемости для контекстно- свободных фильтров. Эта характеристика согласована с отноше- нием рационального доминирования на КС-языках. Однако, как доказано в работе, она более грубая. В работе также приводятся примеры как P-полных, так и NL-полных задач регулярной реа- лизуемости для КС-фильтров. Также приведен пример подкласса КС-языков, для фильтров из которого задачи регулярной реали- зуемости могут иметь промежуточную сложность. Это языки с полиномиально ограниченным рациональным индексом.