I. Boneva, R. Ciucanu, and S. Staworko, Schemas for Unordered XML on a DIME, Theory of Computing Systems, vol.16, issue.3, pp.337-376, 2015.
DOI : 10.1007/s00224-014-9593-1
URL : https://hal.archives-ouvertes.fr/hal-01076329

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, International Conference on Extending Database Technology (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, International Conference on Extending Database Technology (EDBT), 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, International Symposium on Database Programming Languages (DBPL), 2013.
URL : https://hal.archives-ouvertes.fr/hal-00846809

M. Giraud and S. Staworko, Modeling Musical Structure with Parametric Grammars, Mathematics and Computation in Music (MCM), pp.88-96, 2015.
DOI : 10.1007/978-3-319-20603-5_8
URL : https://hal.archives-ouvertes.fr/hal-01205422

J. E. Gayo, E. Prud-'hommeaux, I. Boneva, S. Staworko, H. R. Solbrig et al., Towards an RDF validation language based on regular expression derivatives, EDBT/ICDT Workshops (GraphQ & LWDM), pp.197-204, 2015.

G. Laurence, A. Lemay, J. Niehren, S. Staworko, and M. Tommasi, Normalization of Sequential Top-Down Tree-to-Word Transducers, Language and Automata Theory and Applications (LATA), pp.352-363, 2011.
DOI : 10.1007/978-3-642-21254-3_28
URL : https://hal.archives-ouvertes.fr/inria-00566291

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

J. Michaliszyn, A. Muscholl, S. Staworko, P. Wieczorek, and Z. Wu, On injective embeddings of tree patterns, 1204.

S. Staworko, I. Boneva, J. E. Gayo, S. Hym, E. G. Prud-'hommeaux et al., Complexity and expressiveness of ShEx for RDF, International Conference on Database Theory (ICDT), pp.195-211, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01218552

S. Staworko, G. Laurence, A. Lemay, and J. Niehren, Equivalence of Deterministic Nested Word to Word Transducers, International Symposium on Fundamentals of Computation Theory (FCT), pp.310-322, 2009.
DOI : 10.1007/978-3-642-03409-1_28
URL : https://hal.archives-ouvertes.fr/inria-00423961

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

S. Staworko and P. Wieczorek, Characterizing XML twig queries with examples Learning and verifying quantified boolean queries by example, International Conference on Database Theory (ICDT) ACM Symposium on Principles of Database Systems (PODS), pp.144-160, 2013.

M. Anthony, G. Brightwell, D. Cohen, and J. Shawe-taylor, On exact specification by examples, Proceedings of the fifth annual workshop on Computational learning theory , COLT '92, pp.311-318, 1992.
DOI : 10.1145/130385.130420

P. [. Abiteboul, V. Bourhis, and . Vianu, Highly expressive query languages for unordered data trees, International Conference on Database Theory (ICDT), pp.46-60, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00765558

C. [. Arenas, J. Gutierrez, and . Pérez, Foundations of RDF Databases, Reasoning Web, International Summer School on Semantic Technologies for Information Systems, pp.158-204, 2009.
DOI : 10.1016/0022-0000(84)90080-1

J. [. Abouzied, A. Hellerstein, and . Silberschatz, Playful query specification with DataPlay, Proceedings of the VLDB Endowment (PVLDB), pp.1938-1941, 2012.
DOI : 10.14778/2367502.2367542

L. [. Arenas and . Libkin, XML data exchange: Consistency and query answering, ACM Symposium on Principles of Database Systems (PODS), pp.13-24, 2005.

]. D. Ang79 and . Angluin, Finding patterns common to a set of strings, ACM Symposium on Theory of Computing (STOC), pp.130-141, 1979.

]. D. Ang80 and . Angluin, Inductive inference of formal languages from positive data, Information and Control, vol.45, issue.2, pp.117-135, 1980.

]. D. Ang87 and . Angluin, Learning regular sets from queries and counterexamples, Information and Computation, vol.75, pp.87-106, 1987.

]. D. Ang88 and . Angluin, Queries and concept learning, Machine Learning, pp.319-342, 1988.

J. M. Arenas, J. Pérez, C. Reutter, J. Riveros, and . Sequeda, Data exchange in the relational and RDF worlds, International Workshop on Semantic Web Information Management (SWIM), 2011.

G. [. Androutsopoulos, P. Ritchie, and . Thanisch, Natural language interfaces to databases ??? an introduction, Natural Language Engineering, vol.14, issue.01, pp.29-81, 1995.
DOI : 10.1145/319983.319986

]. B. Atckt11a, B. Alexe, P. G. Ten-cate, W. C. Kolaitis, and . Tan, Designing and refining schema mappings via data examples, ACM SIGMOD International Conference on Management of Data, pp.133-144, 2011.

]. B. Atckt11b, B. Alexe, P. G. Ten-cate, W. C. Kolaitis, and . Tan, EIRENE: Interactive design and refinement of schema mappings via data examples, Proceedings of the VLDB Endowment (PVLDB), pp.1414-1417, 2011.

S. [. Amer-yahia, L. V. Cho, D. Lakshmanan, and . Srivastava, Tree pattern query minimization, The VLDB Journal The International Journal on Very Large Data Bases, vol.11, issue.4, pp.315-331, 2002.
DOI : 10.1007/s00778-002-0076-7

]. C. Bab64 and . Babbage, Passages from the Life of a Philosopher, 1864.

]. F. Ban78 and . Bancilhon, On the completeness of query languages for relational data bases, Mathematical Foundations of Computer Science (MFCS), pp.112-123, 1978.

R. [. Bonifati, A. Ciucanu, and . Lemay, Learning path queries on graph databases, International Conference on Extending Database Technology (EDBT), pp.109-120, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01187966

M. Benedikt, W. Fan, and F. Geerts, XPath satisfiability in the presence of DTDs, Journal of the ACM, vol.55, issue.2, 2008.

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

S. [. Bolleman, N. Gehant, and . Redaschi, Catching inconsistencies with the semantic web: A biocuration case study, International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS), 2012.

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

T. [. Beeri and . Milo, Schemas for Integration and Translation of Structured and Semi-structured Data, International Conference on Database Theory (ICDT), pp.296-313, 1999.
DOI : 10.1007/3-540-49257-7_19

F. [. Bex, T. Neven, K. Schwentick, and . Tuyls, Inference of concise DTDs from XML data, International Conference on Very Large Data Bases (VLDB), pp.115-126, 2006.

F. [. Bex, T. Neven, S. Schwentick, and . Vansummeren, Inference of concise regular expressions and DTDs, ACM Transactions on Database Systems, vol.35, issue.2, p.2010
DOI : 10.1145/1735886.1735890

F. [. Bex, S. Neven, and . Vansummeren, Inferring XML schema definitions from XML data, International Conference on Very Large Data Bases (VLDB), pp.998-1009, 2007.

]. G. Bnvdb04, F. Bex, J. Neven, and . Van-den-bussche, DTDs versus XML Schema: A practical study, WebDB, pp.79-84, 2004.

M. [. Carme, M. Ceresna, and . Goebel, Query-Based Learning of XPath Expressions, International Colloquium on Grammatical Inference (ICGI), pp.342-343, 2006.
DOI : 10.1007/11872436_29

H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard et al., Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata Interactive learning of node selecting tree transducers, Machine Learning, pp.33-67, 2007.

F. [. Cebiric, I. Goasdoué, and . Manolescu, Query-oriented summarization of RDF graphs, British International Conference on Databases (BICOD), pp.87-91, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01179484

G. [. Colazzo, C. Ghelli, and . Sartiani, Efficient inclusion for a class of XML types with interleaving and counting, Information Systems, vol.34, issue.7, pp.643-656, 2009.
DOI : 10.1016/j.is.2008.10.001
URL : https://hal.archives-ouvertes.fr/inria-00535983

]. C. Cho03 and . Choffrut, Minimizing subsequential transducers: a survey, Theoretical Computer Science (TCS), vol.292, issue.1, pp.131-143, 2003.

Y. [. Cohen and . Weiss, Certain and possible XPath answers, Proceedings of the 16th International Conference on Database Theory, ICDT '13, 2013.
DOI : 10.1145/2448496.2448525

Y. [. Cohen and . Weiss, Learning tree patterns from example graphs, International Conference on Database Theory (ICDT), pp.127-143, 2015.

]. V. Dal00 and . Dalmau, Computational Complexity of Problems over Generalized Formulas, 2000.

C. De-la-higuera-[-dp92-]-r, J. Dechter, . J. Pearl, S. Engelfriet, H. Maneth et al., A bibliographical study of grammatical inference Structure identification in relational data The technology paradox: Efficiency versus creativity Deciding equivalence of top-down XML transformations in polynomial time Some open questions and recent results on tree transducers and tree languages Formal language theory; perspectives and open problems Managing semi-structured data, Machine Learning Freydenberger and T. Kötzing. Fast learning of restricted regular expressions and DTDs International Conference on Database Theory (ICDT), pp.125-1381332, 1980.

W. Fan, J. Li, X. Wang, Y. Wu, . Frr-+-10-]-e et al., Query preserving graph compression Properties of visibly pushdown transducers Minimization of deterministic bottom-up tree transducers, ACM SIGMOD International Conference on Management of Data Developments in Language Theory (DLT)Gau85] A. Gaur. A history of writing. British Library Celsi, and H. J. Schau. It don't come easy: Overcoming obstacles to technology use within a resistant consumer group. The Journal of Consumer Affairs, pp.157-168, 1985.

M. N. Garofalakis, A. Gionis, R. Rastogi, S. Seshadri, K. A. Shim-[-gk95-]-s et al., XTRACT: Learning document type descriptors from XML document collections Semigroups, presburger formulas, and languages On the complexity of teaching The quality of the XML web Language identification in the limit Complexity of automaton identification from given data, International Conference on Information and Knowledge Management (CIKM). Schapire. Learning binary relations and total orders. SIAM Journal on Computing, pp.23-56285, 1966.

G. Gottlob and P. Senellart, Schema mapping discovery from data instances, Journal of the ACM, vol.57, issue.2, p.2010
DOI : 10.1145/1667053.1667055
URL : https://hal.archives-ouvertes.fr/hal-00567015

]. J. Gvdb09, J. Gillis, and . Van-den-bussche, Induction of relational algebra expressions, Inductive Logic Programming (ILP), pp.25-33, 2009.

R. [. Hopcroft, J. D. Motwani, and . Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.

F. [. Hegewald, M. Naumann, and . Weis, XStruct: Efficient Schema Extraction from Multiple and Large XML Documents, 22nd International Conference on Data Engineering Workshops (ICDEW'06), pp.81-81, 2006.
DOI : 10.1109/ICDEW.2006.166

B. [. Jiang and . Ravikumar, Minimal NFA Problems are Hard, SIAM Journal on Computing, vol.22, issue.6, pp.1117-1141, 1993.
DOI : 10.1137/0222067

M. [. Khatchadourian and . Consens, ExpLOD: Summary-based exploration of interlinking and RDF usage in the linked open data cloud. The Semantic Web: Research and Applications, pp.272-287, 2010.

A. [. Kopczynski and . To, Parikh Images of Grammars: Complexity and Applications, 2010 25th Annual IEEE Symposium on Logic in Computer Science, pp.80-89, 2010.
DOI : 10.1109/LICS.2010.21

. Kushilevitz, Communication complexity Advances in Computers, pp.331-360, 1997.

K. [. Lidwell, J. Holden, and . Butler, Universal Principles of Design, Revised and Updated: 125 Ways to Enhance Usability, Influence Perception, Increase Appeal, Make Better Design Decisions, 2010.

]. W. Lip79, . Jr, and . Lipski, On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), vol.4, issue.3, pp.262-296, 1979.

H. [. Li and . Jagadish, Constructing an interactive natural language interface for relational databases, Proceedings of the VLDB Endowment (PVLDB), pp.73-84, 2014.
DOI : 10.14778/2735461.2735468

S. [. Lemay, J. Maneth, and . Niehren, A learning algorithm for top-down XML transformations, Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data, PODS '10, pp.285-296, 2010.
DOI : 10.1145/1807085.1807122
URL : https://hal.archives-ouvertes.fr/inria-00460489

K. [. Maduko, A. P. Anyanwu, P. Sheth, and . Schliekelman, Graph Summaries for Subgraph Frequency Estimation, European Semantic Web Conference, pp.508-523, 2008.
DOI : 10.1007/978-3-540-68234-9_38

]. C. Mck97 and . Mckinstry, Minimum intelligent signal test: an objective Turing Test, Canadian Artificial Intelligence, pp.17-18, 1997.

H. [. Morishima, A. Kitagawa, and . Matsumoto, A machine learning approach to rapid development of XML mapping queries, Proceedings. 20th International Conference on Data Engineering, 2004.
DOI : 10.1109/ICDE.2004.1320004

F. [. Martens, M. Neven, and . Gyssens, Typechecking top-down XML transformations: Fixed input or output schemas, Information and Computation, vol.206, issue.7, pp.806-827, 2008.
DOI : 10.1016/j.ic.2008.01.002

F. [. Martens, T. Neven, and . 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

G. Miklau and D. Suciu, Containment and equivalence for a fragment of XPath, Journal of the ACM, vol.51, issue.1, pp.2-45, 2004.
DOI : 10.1145/962446.962448

T. [. Neven and . Schwentick, XML schemas without order, 1999.

T. [. Neven and . Schwentick, On the complexity of XPath containment in the presence of disjunction, DTDs, and variables, Logical Methods in Computer Science, vol.2, issue.3, 2006.
DOI : 10.2168/LMCS-2(3:1)2006

P. [. Oncina and . Gracia, Inferring regular languages in polynomial update time, Pattern Recognition and Image Analysis, 1991.

]. W. Ong86 and . Ong, Writing is a technology that restructures thought, pp.23-50, 1986.
DOI : 10.1075/tsl.21.22ong

]. W. Ong02 and . Ong, Orality and Literacy. New Accents, 2002.

]. R. Par66 and . Parikh, On context-free languages, Journal of Computer and System SciencesPar78] J. Paredaens. On the expressive power of the relational algebra. Information Processing Letters, pp.323-332570, 1966.

]. R. Pea85 and . Pea, Beyond amplification: Using the computer to reorganize mental functioning, Educational psychologist, vol.20, issue.4, pp.167-182, 1985.

M. [. Qian, H. V. Cafarella, and . Jagadish, Sample-driven schema mapping, Proceedings of the 2012 international conference on Management of Data, SIGMOD '12, pp.73-84, 2012.
DOI : 10.1145/2213836.2213846

]. S. Rbvdb08, M. Raeymaekers, J. Bruynooghe, and . Van-den-bussche, Learning (k, l)-contextual tree languages for information extraction from web pages, Machine Learning, pp.2-3155, 2008.

J. [. Ramakrishnan and . Gehrke, Database Management Systems, 2000.

A. [. Ryman, S. Hors, and . Speicher, OSLC Resource Shape: A language for defining constraints on linked data, WWW Workshop on Linked Data on the Web (LDOW), 2013.

P. [. Russell and . Norvig, Artificial Intelligence ? A Modern Approach, 2010.

M. [. Reutenauer and . Schützenberger, Minimization of Rational Word Functions, SIAM Journal on Computing, vol.20, issue.4, pp.669-685, 1991.
DOI : 10.1137/0220042

S. [. Shinohara and . Arikawa, Pattern inference, Algorithmic Learning for Knowledge-Based Systems, pp.259-291, 1995.
DOI : 10.1007/3-540-60217-8_13

A. [. Salzberg, D. G. Delcher, S. Heath, . Kasifshi82-]-t, and . Shinohara, Learning with a helpful teacher Polynomial time inference of extended regular pattern languages, International Conference on Artificial Intelligence (AAAI) RIMS Symposium on Software Science and Engineering, pp.705-711, 1982.

]. E. Sir10 and . Sirin, Data validation with OWL integrity constraints, International Conference on Web Reasoning and Rule Systems (RR), pp.18-22, 2010.

A. Shinohara and S. Miyano, Teachability in computational learning, New Generation Computing, vol.27, issue.No. 11, pp.337-347, 1991.
DOI : 10.1007/BF03037091

A. [. Sarma, H. Parameswaran, J. Garcia-molina, and . Widom, Synthesizing view definitions from data, International Conference on Database Theory (ICDT), pp.89-103, 2010.

J. [. Servais and . Raskin, Visibly pushdown transducers, International Colloquium on Automata, Languages and Programming (ICALP), 2008.
URL : https://hal.archives-ouvertes.fr/inria-00492241

]. R. Tay68 and . Taylor, Question-negotiation and information seeking in libraries, College & Research Libraries, vol.29, issue.3, pp.178-194, 1968.

]. B. Ten-cate, V. Dalmau, and P. G. Kolaitis, Learning schema mappings Database constraints and homomorphism dualities, Principles and Practice of Constraint Programming (CP), pp.475-490, 2010.

C. [. Tran, S. Chan, and . Parthasarathy, Query by output, Proceedings of the 35th SIGMOD international conference on Management of data, SIGMOD '09, pp.535-548, 2009.
DOI : 10.1145/1559845.1559902

G. [. Tran, S. Ladwig, and . Rudolph, Managing Structured and Semistructured RDF Data Using Structure Indexes, IEEE Transactions on Knowledge and Data Engineering, vol.25, issue.9, pp.2076-2089, 2013.
DOI : 10.1109/TKDE.2012.134

E. [. Tao, J. Sirin, D. L. Bao, and . Mcguinness, Integrity constraints in OWL, International Conference on Artificial Intelligence (AAAI), 2010.

]. A. Tur50 and . Turing, Computing machinery and intelligence, Mind, LIX, issue.236, pp.433-460, 1950.

]. L. Val84 and . Valiant, A theory of the learnable, Communications of the ACM, vol.27, pp.1134-1142, 1984.

]. W3c07a and . W3c, XML path language (XPath) 2.0, 2007.

]. W3c13a and . W3c, RDF validation workshop report: Practical assurances for quality RDF data, 2012.

]. W3c13b and . W3c, Shape expressions schemas, 2013.

H. [. Whitworth and . Ryu, A comparison of human and computer information processing, Encyclopaedia of Multimedia technology and Networking, pp.230-239, 2009.

]. K. Wri89 and . Wright, Identification of unions of languages drawn from an identifiable class, Workshop on Computational Learning Theory (COLT), pp.328-333, 1989.

H. [. Warwick and . Shah, Can machines think? A report on Turing test experiments at the Royal Society, Journal of Experimental & Theoretical Artificial Intelligence, vol.27, issue.6, pp.1-19, 2015.
DOI : 10.1007/s11023-013-9301-y

H. Zhang, Y. Duan, X. Yuan, and Y. Zhang, ASSG: adaptive structural summary for RDF graph data, International Semantic Web Conference (ISWC), pp.233-236, 2014.

H. [. Zhang, C. M. Elmeleegy, D. Procopiuc, and . Srivastava, Reverse engineering complex join queries, Proceedings of the 2013 international conference on Management of data, SIGMOD '13, pp.809-820, 2013.
DOI : 10.1145/2463676.2465320