A. Abouzied, D. Angluin, C. H. Papadimitriou, J. M. Hellerstein, and A. Silberschatz, Learning and verifying quantified boolean queries by example, Proceedings of the 32nd symposium on Principles of database systems, PODS '13, pp.49-60, 2013.
DOI : 10.1145/2463664.2465220

R. Angles and C. Gutiérrez, Survey of graph database models, ACM Computing Surveys, vol.40, issue.1, 2008.
DOI : 10.1145/1322432.1322433

D. Angluin, Queries and concept learning, Machine Learning, pp.319-342, 1988.
DOI : 10.1007/BF00116828

T. Antonopoulos, F. Neven, and F. Servais, Definability problems for graph query languages, Proceedings of the 16th International Conference on Database Theory, ICDT '13, pp.141-152, 2013.
DOI : 10.1145/2448496.2448514

M. Arenas and J. Pérez, Querying semantic web data with SPARQL, Proceedings of the 30th symposium on Principles of database systems of data, PODS '11, pp.305-316, 2011.
DOI : 10.1145/1989284.1989312

G. Bagan, A. Bonifati, and B. Groz, A trichotomy for regular simple path queries on graphs, Proceedings of the 32nd symposium on Principles of database systems, PODS '13, pp.261-272, 2013.
DOI : 10.1145/2463664.2467795
URL : https://hal.archives-ouvertes.fr/hal-00806448

P. Barceló, Querying graph databases, PODS, pp.175-188, 2013.

K. Belhajjame, Annotating the behavior of scientific modules using data examples: A practical approach, EDBT, pp.726-737, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01291790

G. J. Bex, W. Gelade, F. Neven, and S. Vansummeren, Learning deterministic regular expressions for the inference of schemas from XML data, TWEB, vol.4, issue.4, 2010.

P. A. Boncz, I. Fundulaki, A. Gubichev, J. Larriba-pey, and T. Neumann, The linked data benchmark council project. Datenbank-Spektrum, pp.121-129, 2013.

A. Bonifati, R. Ciucanu, and A. Lemay, Learning path queries on graph databases, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01187966

A. Bonifati, R. Ciucanu, and A. Lemay, Interactive path query specification on graph databases, EDBT, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01187975

A. Bonifati, R. Ciucanu, A. Lemay, and S. Staworko, A Paradigm for Learning Queries on Big Data, Proceedings of the First International Workshop on Bringing the Value of "Big Data" to Users (Data4U 2014), Data4U '14, pp.7-12, 2014.
DOI : 10.1145/2658840.2658842
URL : https://hal.archives-ouvertes.fr/hal-01052676

A. Bonifati, R. Ciucanu, and S. Staworko, Interactive inference of join queries, EDBT, pp.451-462, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00875680

A. Bonifati, R. Ciucanu, and S. Staworko, Interactive join query inference with JIM, Proceedings of the VLDB Endowment, vol.7, issue.13, pp.1541-1544, 2014.
DOI : 10.14778/2733004.2733025
URL : https://hal.archives-ouvertes.fr/hal-01052789

R. Ciucanu and S. Staworko, Learning schemas for unordered XML Certain and possible XPath answers, DBPL ICDT, pp.31-40, 2013.

C. De and . Higuera, Grammatical Inference: Learning Automata and Grammars, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00476128

M. J. Franklin, D. Kossmann, T. Kraska, S. Ramesh, and R. Xin, CrowdDB, Proceedings of the 2011 international conference on Management of data, SIGMOD '11, pp.61-72, 2011.
DOI : 10.1145/1989323.1989331

E. M. Gold, Complexity of automaton identification from given data, Information and Control, vol.37, issue.3, pp.302-320, 1978.
DOI : 10.1016/S0019-9958(78)90562-4

C. Heinlein, Workflow and process synchronization with interaction expressions and graphs, Proceedings 17th International Conference on Data Engineering, pp.243-252, 2001.
DOI : 10.1109/ICDE.2001.914835

J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, 1979.

T. Imielinski and W. Lipski-jr, Incomplete Information in Relational Databases, Journal of the ACM, vol.31, issue.4, pp.761-791, 1984.
DOI : 10.1145/1634.1886

H. V. Jagadish, A. Chapman, A. Elkiss, M. Jayapandian, Y. Li et al., Making database systems usable, Proceedings of the 2007 ACM SIGMOD international conference on Management of data , SIGMOD '07, pp.13-24, 2007.
DOI : 10.1145/1247480.1247483

N. Jayaram, A. Khan, C. Li, X. Yan, and R. Elmasri, Towards a Query-by-Example System for Knowledge Graphs, Proceedings of Workshop on GRAph Data management Experiences and Systems, GRADES'14, 2014.
DOI : 10.1145/2621934.2621937

M. J. Kearns and U. V. Vazirani, An introduction to computational learning theory, 1994.

A. Koschmieder and U. Leser, Regular Path Queries on Large Graphs, SSDBM, pp.177-194, 2012.
DOI : 10.1007/978-3-642-31235-9_12

D. Kozen, Lower bounds for natural proof systems, 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pp.254-266, 1977.
DOI : 10.1109/SFCS.1977.16

K. Lange and P. Rossmanith, The emptiness problem for intersections of regular languages, MFCS, pp.346-354, 1992.
DOI : 10.1007/3-540-55808-X_33

G. Laurence, A. Lemay, J. Niehren, S. Staworko, and M. Tommasi, Learning Sequential Tree-to-Word Transducers, LATA, pp.490-502, 2014.
DOI : 10.1007/978-3-319-04921-2_40
URL : https://hal.archives-ouvertes.fr/hal-00912969

J. Leskovec and C. Faloutsos, Sampling from large graphs, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '06, pp.631-636, 2006.
DOI : 10.1145/1150402.1150479

K. Losemann and W. Martens, The complexity of regular expressions and property paths in SPARQL, ACM Transactions on Database Systems, vol.38, issue.4, p.24, 2013.
DOI : 10.1145/2494529

D. Mottin, M. Lissandrini, Y. Velegrakis, and T. Palpanas, Exemplar queries, Proceedings of the VLDB Endowment, vol.7, issue.5, pp.365-376, 2014.
DOI : 10.14778/2732269.2732273

A. Nandi and H. V. Jagadish, Guided interaction: Rethinking the query-result paradigm, pp.1466-1469, 2011.

J. Oncina and P. García, Inferring regular languages in polynomial update time, Pattern Recognition and Image Analysis, pp.49-61, 1992.

P. Palaga, L. Nguyen, U. Leser, and J. Hakenberg, High-performance information extraction with AliBaba, Proceedings of the 12th International Conference on Extending Database Technology Advances in Database Technology, EDBT '09, pp.1140-1143, 2009.
DOI : 10.1145/1516360.1516498

R. Ronen and O. Shmueli, SoQL: A Language for Querying and Creating Data in Social Networks, 2009 IEEE 25th International Conference on Data Engineering, pp.1595-1602, 2009.
DOI : 10.1109/ICDE.2009.172

S. Staworko and P. Wieczorek, Learning twig and path queries, Proceedings of the 15th International Conference on Database Theory, ICDT '12, pp.140-154, 2012.
DOI : 10.1145/2274576.2274592
URL : https://hal.archives-ouvertes.fr/hal-00643097

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

B. Ten-cate, V. Dalmau, and P. G. Kolaitis, Learning schema mappings, Proceedings of the 15th International Conference on Database Theory, ICDT '12, p.28, 2013.
DOI : 10.1145/2274576.2274596

P. T. Wood, Query languages for graph databases, ACM SIGMOD Record, vol.41, issue.1, pp.50-60, 2012.
DOI : 10.1145/2206869.2206879

L. Yan, R. J. Miller, L. M. Haas, and R. Fagin, Data-driven understanding and refinement of schema mappings, SIGMOD Conference, pp.485-496, 2001.

M. M. Zloof, Query by example, AFIPS National Computer Conference, pp.431-438, 1975.