A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, 1974.

J. Almeida, J. Barto?ová, O. Klíma, and M. Kunc, On Decidability of Intermediate Levels of Concatenation Hierarchies, Developments in Language Theory (DLT, pp.58-70, 2015.
DOI : 10.1007/978-3-319-21500-6_4

Y. Bar-hillel, M. A. Perles, and E. Shamir, On formal properties of simple phrase structure grammars, pp.143-172, 1961.

P. Barceló, L. Libkin, and J. L. Reutter, Querying Regular Graph Patterns, Journal of the ACM, vol.61, issue.1, pp.1-8, 2014.
DOI : 10.1145/1498765.1498784

G. J. Bex, W. Gelade, W. Martens, and F. Neven, Simplifying XML schema, Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD '09, pp.731-744, 2009.
DOI : 10.1145/1559845.1559922

A. Bouajjani, A. Muscholl, and T. Touilim, Permutation rewriting and algorithmic verification, Information and Computation, vol.205, issue.2, pp.199-224, 2007.
DOI : 10.1016/j.ic.2005.11.007
URL : https://hal.archives-ouvertes.fr/hal-00161120

A. Brüggemann-klein and D. Wood, One-Unambiguous Regular Languages, Information and Computation, vol.142, issue.2, pp.182-206, 1998.
DOI : 10.1006/inco.1997.2695

J. A. Brzozowski and F. E. Fich, Languages of R-trivial monoids, Journal of Computer and System Sciences, vol.20, issue.1, pp.32-49, 1980.
DOI : 10.1016/0022-0000(80)90003-3
URL : http://doi.org/10.1016/0022-0000(80)90003-3

J. A. Brzozowski and R. Knast, The dot-depth hierarchy of star-free languages is infinite, Journal of Computer and System Sciences, vol.16, issue.1, pp.37-55, 1978.
DOI : 10.1016/0022-0000(78)90049-1

D. Calvanese, G. De-giacomo, M. Lenzerini, and M. Y. Vardi, Reasoning on regular path queries, ACM SIGMOD Record, vol.32, issue.4, pp.83-92, 2003.
DOI : 10.1145/959060.959076
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.486

R. S. Cohen and J. A. Brzozowski, Dot-depth of star-free events, Journal of Computer and System Sciences, vol.5, issue.1, pp.1-16, 1971.
DOI : 10.1016/S0022-0000(71)80003-X
URL : http://doi.org/10.1016/s0022-0000(71)80003-x

W. Czerwinski, C. David, K. Losemann, and W. Martens, Deciding definability by deterministic regular expressions, International Conference on Foundations of Software Science and Computation Structures (FoSSaCS, pp.289-304, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00788609

K. Ellul, B. Krawetz, J. Shallit, and M. Wang, Regular expressions: New results and open problems, Journal of Automata, Languages and Combinatorics, vol.10, issue.4, pp.407-437, 2005.

E. P. Friedman, The inclusion problem for simple languages, Theoretical Computer Science, vol.1, issue.4, pp.297-316, 1976.
DOI : 10.1016/0304-3975(76)90074-8
URL : http://doi.org/10.1016/0304-3975(76)90074-8

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

C. Glaßer and H. Schmitz, Languages of Dot-Depth 3/2, Theory of Computing Systems, vol.16, issue.2, pp.256-286, 2008.
DOI : 10.1007/978-3-540-28629-5_8

P. Hofman and W. Martens, Separability by short subsequences and subwords, International Conference on Database Theory (ICDT), 2015.

M. Holzer and M. Kutrib, Descriptional and computational complexity of finite automata???A survey, Information and Computation, vol.209, issue.3, pp.456-470, 2011.
DOI : 10.1016/j.ic.2010.11.013

I. Hunt and H. B. , On the time and tape complexity of languages I, Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, 1973.
DOI : 10.1145/800125.804030

I. Hunt, H. B. Rosenkrantz, and D. J. , Computational parallels between the regular and context-free languages, Proceedings of the sixth annual ACM symposium on Theory of computing , STOC '74, pp.99-114, 1978.
DOI : 10.1145/800119.803885

N. D. Jones, Space-bounded reducibility among combinatorial problems, Journal of Computer and System Sciences, vol.11, issue.1, pp.68-85, 1975.
DOI : 10.1016/S0022-0000(75)80050-X
URL : http://doi.org/10.1016/s0022-0000(77)80009-3

O. Klíma and L. Polák, Alternative Automata Characterization of Piecewise Testable Languages, Developments in Language Theory (DLT), pp.289-300, 2013.
DOI : 10.1007/978-3-642-38771-5_26

M. Krötzsch, T. Masopust, and M. Thomazo, On the complexity of university for partially ordered NFAs, of LIPIcs, pp.611-6114, 2016.

M. Kufleitner and A. Lauser, PARTIALLY ORDERED TWO-WAY B??CHI AUTOMATA, International Journal of Foundations of Computer Science, vol.140, issue.08, pp.1861-1876, 2011.
DOI : 10.1016/0022-0000(82)90016-2

K. Lodaya, P. K. Pandya, and S. S. Shah, Around Dot Depth Two, Developments in Language Theory (DLT, pp.303-315, 2010.
DOI : 10.1007/978-3-642-14455-4_28

W. Martens, F. Neven, and T. Schwentick, Complexity of Decision Problems for XML Schemas and Chain Regular Expressions, SIAM Journal on Computing, vol.39, issue.4, pp.1486-1530, 2009.
DOI : 10.1137/080743457

T. Masopust, Piecewise testable languages and nondeterministic automata, Mathematical Foundations of Computer Science (MFCS). LIPIcs. pp, vol.58, issue.67, pp.1-6714, 2016.

T. Masopust and M. Thomazo, On Boolean combinations forming piecewise testable languages, Theoretical Computer Science, vol.682, pp.165-179, 2017.
DOI : 10.1016/j.tcs.2017.01.017

A. R. Meyer and L. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, 13th Annual Symposium on Switching and Automata Theory (swat 1972), pp.125-129, 1972.
DOI : 10.1109/SWAT.1972.29

T. Place, Separating Regular Languages with Two Quantifiers Alternations, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pp.202-213, 2015.
DOI : 10.1109/LICS.2015.28

T. Place and M. Zeitoun, Separation and the successor relation, Symposium on Theoretical Aspects of Computer Science (STACS), 2015.

N. Rampersad, J. Shallit, and Z. Xu, The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages, Fundamenta Informatica, vol.116, pp.1-4, 2012.

H. Schmitz, The forbidden pattern approach to concatenation hierachies, 2000.

M. P. Schützenberger, Sur Le Produit De Concatenation Non Ambigu, Semigroup Forum, vol.7, issue.1, pp.47-75, 1976.
DOI : 10.1016/S0022-0000(71)80006-5

T. Schwentick, D. Thérien, and H. Vollmer, Partially-Ordered Two-Way Automata: A New Characterization of DA, Developments in Language Theory (DLT, pp.239-250, 2001.
DOI : 10.1007/3-540-46011-X_20

G. Sénizergues, The equivalence problem for deterministic pushdown automata is decidable, International Colloquium on Automata , Languages and Programming (ICALP), pp.671-681, 1997.
DOI : 10.1007/3-540-63165-8_221

I. Simon, Hierarchies of events with dot-depth one, 1972.

G. Stefanoni, B. Motik, M. Krötzsch, and S. Rudolph, The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases, Journal of Artificial Intelligence Research, vol.51, pp.645-705, 2014.

L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.1-9, 1973.
DOI : 10.1145/800125.804029
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.4618

H. Straubing, A generalization of the Sch??tzenberger product of finite monoids, Theoretical Computer Science, vol.13, issue.2, pp.137-150, 1981.
DOI : 10.1016/0304-3975(81)90036-0

H. Straubing, Finite semigroup varieties of the form V ??? D, Journal of Pure and Applied Algebra, vol.36, pp.53-94, 1985.
DOI : 10.1016/0022-4049(85)90062-3

D. Thérien, Classification of finite monoids: the language approach, Theoretical Computer Science, vol.14, issue.2, pp.195-208, 1981.
DOI : 10.1016/0304-3975(81)90057-8

K. W. Wagner, Leaf Language Classes, In: Machines, Computations, and Universality (MCU). LNCS, vol.3354, pp.60-81, 2004.
DOI : 10.1007/978-3-540-31834-7_5