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
Timed automata and timed finite state machins (TFSMs) have been proposed to represent more accurately the behaviour of systems in continuous time. Recently, we introduced a model of TFSMs that extends the expressive power of FSMs by introducing a single clock, timed guards which restrict when the input/output transitions may happen, and timeouts on the transitions. We derived an abstraction procedure to convert a TFSM into an equivalent untimed FSM. Here, we extend the model with output timeouts and derive a minimal form for deterministic TFSMs that reduces the number of states, the number of transitions and the timeout values at each state.
M. Rabin's principle asserts that the depth of any algebraic decision tree, recognizing a closed orthant in scRn, is no less than n. Using the techniques of Newton polyhedra, we give the shortest possible proof of this fact, extending it to arbitrary collections of open or closed orthants, and apply it to trees distinguishing real polynomials having at least l real roots.
We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse measure of context-free languages com- plexity. This characteristic is compatible with rational dominance. We present examples of P-complete RR problems as well as examples of RR problems in the class NL. Also we discuss RR problems with context- free filters that might have intermediate complexity. Possible candidates are the languages with polynomially bounded rational indices.
We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), presented by Li and Vit ́anyi in 1995 and corrected by Glier in 2003. The structural lemma allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.
We consider the coloring problem for hereditary graph classes, i.e. classes of simple unlabeled graphs closed under deletion of vertices. For the family of the hereditary classes of graphs defined by forbidden induced subgraphs with at most four vertices, there are three classes with an open complexity of the problem. For the problem and the open three cases, we present approximation polynomial-time algorithms with performance guarantees.