G. .. Plans, , vol.109

. .. Experiments,

.. .. Discussion,

. .. Conclusion,

, Finite state transducers can be built and used to translate one word into another one, Pyformlang implements non-weighted finite-state transducers and operators on them: the concatenation, the union and the Kleene star, vol.3

, Je ', ' suis ', ' tout ', ' seul

, Listing 7.3: Finite State Transducer Example

, This initialisation process can be quite wordy, and in most cases, it is not necessary. However, it is close to textbooks representations and allows a better understanding of context-free grammars. Besides, it is easier to use for a computer

#. Variable, NP ") , Variable (" VP ") , Variable

, VP ") , 35 # Variable

, georges ") , Variable (" V ") , Variable (" NP ") , 37 # Variable

, georges ") , Terminal (" sees ") , 39 # Variable

, Terminal (" sees ") , 41 # Variable

, Terminal (" sees ") , 43 # Terminal

, Terminal (" sees ") , 45 # Terminal, Terminal (" gorilla ") , 46 # Variable

, Terminal (" sees ") , Jailhouse), sang ? (Jailhouse, x), which is an equivalent rewriting of the atomic query sang ?

, We can link the language L q of our context-free grammar to the equivalent rewritings by introducing a corollary of Property B, vol.1

S. Abiteboul, R. Hull, and V. Vianu, Foundations of Databases, 1995.

V. Alfred and . Aho, Indexed grammars-an extension of context-free grammars, Journal of the ACM (JACM), vol.15, issue.4, pp.647-671, 1968.

R. Alfred-v-aho, J. D. Sethi, and . Ullman, Compilers, principles, techniques, vol.7, p.9, 1986.

C. Allauzen, M. Riley, J. Schalkwyk, W. Skut, and M. Mohri, Openfst: A general and efficient weighted finite-state transducer library, International Conference on Implementation and Application of Automata, pp.11-23, 2007.

A. Barredo-arrieta, N. Díaz-rodríguez, J. D. Ser, A. Bennetot, S. Tabik et al., Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai, Information Fusion, vol.58, pp.82-115, 2020.

S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak et al., DBpedia: A nucleus for a Web of Open Data. Semantic Web, 2008.

Y. Ba-hillel, M. Prles, and E. Shamir, On formal properties of simple phrase structure grammars. z. phonetik, sprachwissen. komm. 15 (i961), Bar-Hillel, Language and Information, pp.116-150, 1965.

F. Baader, D. Calvanese, D. Mcguinness, P. Patel-schneider, and D. Nardi, The description logic handbook: Theory, implementation and applications, 2003.

C. Bader and A. Moura, A generalization of ogden's lemma, J. ACM, vol.29, issue.2, 1982.

R. Baeza, -. Yates, and A. Tiberi, Extracting semantic relations from query logs, KDD, 2007.

P. Baker and A. Potts, why do white people have thin lips?'google and the perpetuation of stereotypes via auto-complete search forms. Critical discourse studies, vol.10, pp.187-204, 2013.

R. Beigel and W. Gasarch, A proof that the intersection of a context-free language and a regular language is context-free which does not use push-down automata

M. Benedikt and J. Leblay, Generating Plans from Proofs: The Interpolation-based Approach to Query Reformulation, Synthesis Lectures on Data Management. Morgan & Claypool, 2016.

M. Benedikt, J. Leblay, and E. Tsamoura, PDQ: Proof-driven query answering over web-based data, vol.7, 2014.

M. Benedikt, J. Leblay, and E. Tsamoura, Querying with access patterns and integrity constraints, PVLDB, vol.8, issue.6, 2015.

K. Michael and . Bergman, White paper: the deep web: surfacing hidden value, Journal of electronic publishing, vol.7, issue.1, 2001.

T. and R. Cailliau, Worldwideweb: Proposal for a hypertext project, 1990.

M. Bienvenu, M. Ortiz, and M. Simkus, Regular path queries in lightweight description logics: Complexity and algorithms, JAIR, vol.53, 2015.

C. Bizer, T. Heath, K. Idehen, and T. Berners-lee, Linked data on the web (LDOW2008), WWW, 2008.

A. Bosselut, H. Rashkin, M. Sap, C. Malaviya, A. Çelikyilmaz et al., COMET: commonsense transformers for automatic knowledge graph construction, ACL, 2019.

D. Box, D. Ehnebuske, G. Kakivaya, A. Layman, N. Mendelsohn et al., , 2000.

A. Bozzon, M. Brambilla, and S. Ceri, Answering search queries with crowdsearcher, WWW, 2012.

T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan et al., , 2020.

F. Cai and M. De-rijke, A survey of query auto completion in information retrieval. Foundations and Trends in Information Retrieval, 2016.

A. Calì, D. Calvanese, and D. Martinenghi, Dynamic query optimization under access limitations and dependencies, J. UCS, 2009.

A. Calì, G. Gottlob, and M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints, Journal of Artificial Intelligence Research, vol.48, pp.115-174, 2013.

A. Calì and D. Martinenghi, Querying data under access limitations, ICDE, 2008.

A. Carlson, J. Betteridge, B. Kisiel, B. Settles, R. Estevam et al., Toward an architecture for never-ending language learning, Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010.

M. Castells, The information age, Oxford Blackwell Publishers, vol.98, 1996.

S. Ceri, A. Bozzon, and M. Brambilla, The anatomy of a multi-domain search infrastructure, ICWE, 2011.

Y. Chalier, S. Razniewski, and G. Weikum, Joint reasoning for multi-faceted commonsense knowledge, 2020.

J. Christensen, S. Soderland, and O. Etzioni, An analysis of open information extraction based on semantic role labeling, 2011.

A. Conneau and D. Kiela, Senteval: An evaluation toolkit for universal sentence representations, 2018.

J. Niall, V. L. Conroy, Y. Rubin, and . Chen, Automatic deception detection: Methods for finding fake news, Proceedings of the Association for Information Science and Technology, vol.52, pp.1-4, 2015.

B. Dalvi, N. Tandon, and P. Clark, Domain-targeted, high precision knowledge extraction, TACL, 2017.

A. Demaille, A. Duret-lutz, S. Lombardy, and J. Sakarovitch, Implementation concepts in Vaucanson 2, Proceedings of Implementation and Application of Automata, 18th International Conference (CIAA'13), vol.7982, pp.122-133, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00845816

D. Deutch and T. Milo, A quest for beauty and wealth (or, business processes for database researchers), Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp.1-12, 2011.

D. Deutch and T. Milo, Business Processes: A Database Perspective, Synthesis Lectures on Data Management. Morgan & Claypool, 2012.

A. Deutsch, B. Ludäscher, and A. Nash, Rewriting queries using views with access patterns under integrity constraints, In Theor. Comput. Sci, 2007.

J. Devlin, M. Chang, K. Lee, and K. T. Bert, Pre-training of deep bidirectional transformers for language understanding, 2018.

D. Diefenbach, V. Lopez, K. Singh, and P. Maret, Core techniques of question answering systems over knowledge bases: a survey, Knowledge and Information systems, vol.55, issue.3, pp.529-569, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01637143

S. Dieguez, Total bullshit!: au coeur de la post-vérité, 2018.

H. Q. Chris, T. Ding, W. Li, H. Peng, and . Park, Orthogonal nonnegative matrix tri-factorizations for clustering, KDD, 2006.

X. Dong, E. Gabrilovich, G. Heitz, W. Horn, N. Lao et al., Knowledge vault: A web-scale approach to probabilistic knowledge fusion, Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp.601-610, 2014.

M. Oliver, M. R. Duschka, and . Genesereth, Answering recursive queries using views, PODS, 1997.

M. Oliver, M. R. Duschka, A. Y. Genesereth, and . Levy, Recursive query plans for data integration, J. Log. Program, 2000.

C. Schoenick, Moving beyond the Turing test with the Allen AI science challenge, Communications of the ACM, 2017.

C. Manning, The Stanford CoreNLP natural language processing toolkit, ACL, 2014.

H. Cao, Context-aware query suggestion by mining click-through and session data, KDD, 2008.

L. Bentivogli, Revising the wordnet domains hierarchy: Semantics, coverage and balancing, COLING, 2004.

M. Joshi, TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension, ACL, 2017.

M. Pasca, Weakly-supervised acquisition of open-domain classes and class attributes from web documents and query logs, ACL, 2008.

N. Tandon, WebChild: harvesting and organizing commonsense knowledge from the web, WSDM, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01699891

N. Tandon, Commonsense in parts: Mining part-whole relations from the web and image tags, AAAI, 2016.

N. Tandon, Reasoning about actions and state changes by injecting commonsense knowledge, EMNLP, 2018.

C. Sreyasi-nag, VISIR: visual and semantic image label refinement, WSDM, 2018.

S. Malyshev, Getting the most out of Wikidata: Semantic technology usage in Wikipedia's knowledge graph, ISWC, 2018.

T. Young, Augmenting end-to-end dialogue systems with commonsense knowledge, AAAI, 2018.

O. Etzioni, M. Cafarella, D. Downey, S. Kok, A. Popescu et al., Web-scale information extraction in knowitall: (preliminary results), Proceedings of the 13th international conference on World Wide Web, pp.100-110, 2004.

M. Faruqui, J. Dodge, K. Sujay, C. Jauhar, E. Dyer et al., Retrofitting word vectors to semantic lexicons, 2014.

A. Edward and . Feigenbaum, Knowledge engineering, 1984.

D. Ferrucci, E. Brown, J. Chu-carroll, J. Fan, D. Gondek et al., Building watson: An overview of the deepqa project, AI magazine, vol.31, issue.3, pp.59-79, 2010.

T. Roy, R. Fielding, and . Taylor, Architectural styles and the design of network-based software architectures, vol.7, 2000.

L. Figaro, Quand christine boutin cite sans sourciller le site parodique le gorafi

D. Florescu, A. Y. Levy, I. Manolescu, and D. Suciu, Query optimization in the presence of limited access patterns, SIGMOD, 1999.
URL : https://hal.archives-ouvertes.fr/inria-00073035

G. Harry and . Frankfurt, On bullshit, 2009.

L. Galárraga, G. Heitz, K. Murphy, and F. M. Suchanek, Canonicalizing open knowledge bases, CIKM, 2014.

G. Gange, J. A. Navas, P. Schachte, H. Søndergaard, and P. Stuckey, A tool for intersecting context-free grammars and its applications, NASA Formal Methods Symposium, pp.422-428, 2015.

G. Gazdar, Applicability of indexed grammars to natural languages, Natural language parsing and linguistic theories, pp.69-94, 1988.

T. Gogacz and J. Marcinkowski, Red spider meets a rainworm: Conjunctive query finite determinacy is undecidable, SIGMOD, 2016.

L. Gorafi, Le gorafi -toute l'information selon des sources contradictoires

A. Hagberg, D. Schult, P. Swart, . Conway, C. Séguin-charbonneau et al., , 2013.

Y. Alon and . Halevy, Answering queries using views: A survey, VLDB J, 2001.

J. Hopcroft, An n log n algorithm for minimizing states in a finite automaton, Theory of machines and computations, pp.189-196, 1971.

E. John, R. Hopcroft, J. D. Motwani, and . Ullman, Introduction to automata theory, languages, and computation, vol.32, pp.60-65, 2001.

E. John, . Hopcroft, . 1942-ullman, and D. Jeffrey, Introduction to automata theory, languages, and computation, 1979.

D. Khashabi, T. Khot, A. Sabharwal, O. Tafjord, P. Clark et al., Unifiedqa: Crossing format boundaries with a single qa system, 2020.

F. Angel-lagares-lemos, B. Daniel, and . Benatallah, Web service composition: A survey of techniques and tools, ACM Comput. Surv, vol.48, issue.3, 2015.

B. Douglas and . Lenat, Cyc: A large-scale investment in knowledge infrastructure, Communications of the ACM, 1995.

O. Daniel-j-lizotte, R. Madani, and . Greiner, Budgeted learning of naive-bayes classifiers, 2012.

E. Loper and S. Bird, Nltk: the natural language toolkit, 2002.

G. Marcus, The next decade in ai: Four steps towards robust artificial intelligence, 2020.

D. L. Martin, M. Paolucci, S. A. Mcilraith, M. H. Burstein, D. V. Mcdermott et al., Bringing semantics to web services: The OWL-S approach, SWSWPC, 2004.

. Mausam, Open information extraction systems and downstream applications, IJCAI, 2016.

J. Mccarthy, Programs with common sense. RLE and MIT computation center, 1960.

C. Michel and P. Baud, La fiabilité des médias

G. A. Miller, Wordnet: A lexical database for english, Commun. ACM, 1995.

A. Nash and B. Ludäscher, Processing unions of conjunctive queries with negation under limited access patterns, EDBT, 2004.

R. Navigli, Word sense disambiguation: A survey, ACM Comput. Surv, 2009.

R. Navigli and S. P. Ponzetto, Babelnet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network, Artificial Intelligence, vol.193, pp.217-250, 2012.

A. Institute and . Ai, AI2 science questions v2

H. Pal, Demonyms and compound relational nouns in nominal open IE, AKBC, 2016.

M. Parchure, A. Sasikumar, and . Garg, Veda: an online assessment and question banking system, 2009.

M. Pasca, Open-domain fine-grained class extraction from web search queries, EMNLP, 2013.

M. Pasca, The role of query sessions in interpreting compound noun phrases, CIKM, 2015.

G. Thomas-pellissier-tanon, F. M. Weikum, and . Suchanek, Yago 4: A reason-able knowledge base, Proceedings of the Extended Semantic Web Conference (ESWC), p.2020, 2020.

N. Preda, G. Kasneci, F. M. Suchanek, T. Neumann, W. Yuan et al., Active Knowledge : Dynamically Enriching RDF Knowledge Bases by Web Services, SIGMOD, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00544356

N. Preda, F. M. Suchanek, W. Yuan, and G. Weikum, SUSIE: Search Using Services and Information Extraction, ICDE, 2013.

K. Q. Pu, Syntactic rule based approach to Web service composition, Vagelis Hristidis, and Nick Koudas, 2006.

B. Quilitz and U. Leser, Querying distributed RDF data sources with SPARQL, ESWC, 2008.

S. Rabin, Game AI pro 2: collected wisdom of game AI professionals, 2015.

A. Rajaraman, Y. Sagiv, and J. D. Ullman, Answering queries using templates with binding patterns, PODS, 1995.

J. Rao, Logic-based web services composition: From service description to process model, Peep Küngas, and Mihhail Matskin, 2004.

R. Reis and N. Moreira, Fado: tools for finite automata and regular expressions manipulation, 2002.

H. Susan, T. Rodger, and . Finley, JFLAP: an interactive formal languages and automata package, 2006.

J. Romero, Pyformlang: An Educational Library for Formal Language Manipulation, SIGCSE, p.2021

J. Romero, N. Preda, A. Amarilli, and F. Suchanek, Computing and illustrating query rewritings on path views with binding patterns, Proceedings of the 29th ACM International Conference on Information and Knowledge Management -CIKM '20, 2020.

J. Romero, N. Preda, A. Amarilli, and F. Suchanek, Equivalent rewritings on path views with binding patterns, 2020.
URL : https://hal.archives-ouvertes.fr/hal-02876611

J. Romero, N. Preda, and F. Suchanek, Query rewriting on path views without integrity constraints, 2020.

J. Romero and S. Razniewski, Inside quasimodo: Exploring construction and usage of commonsense knowledge, Proceedings of the 29th ACM International Conference on Information and Knowledge Management -CIKM '20, 2020.

J. Romero, S. Razniewski, K. Pal, J. Z. Pan, A. Sakhadeo et al., Commonsense properties from query logs and question answering forums, Proceedings of the 28th ACM International Conference on Information and Knowledge Management -CIKM '19, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02158602

S. Saha and M. , Open information extraction from conjunctive sentences, COLING, 2018.

S. Saha, H. Pal, and M. , Bootstrapping for numerical open IE, ACL, 2017.

M. Sap, R. Lebras, E. Allaway, C. Bhagavatula, N. Lourie et al., Atomic: An atlas of machine commonsense for if-then reasoning, 2018.

A. Schwarte, P. Haase, K. Hose, R. Schenkel, and M. Schmidt, Fedx: Optimization techniques for federated query processing on linked data, ISWC, 2011.

O. Shmueli, Decidability and expressiveness aspects of logic queries, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pp.237-249, 1987.

P. Singh, T. Lin, E. T. Mueller, G. Lim, T. Perkins et al., Open mind common sense: Knowledge acquisition from the general public, OTM Confederated International Conferences "On the Move to Meaningful Internet Systems, pp.1223-1237, 2002.

. Snopes, Donald trump protester speaks out: "i was paid $3,500 to protest trump's rally

R. Speer and C. Havasi, ConceptNet 5: A large semantic network for relational knowledge, Theory and Applications of Natural Language Processing, 2012.

R. Speer and C. Havasi, Representing general relational knowledge in ConceptNet 5, LREC, 2012.

S. Staab and R. Studer, Handbook on ontologies, 2010.

. Oasis and . Standard, Web services business process execution language

M. Fabian, G. Suchanek, G. Kasneci, and . Weikum, Yago: a core of semantic knowledge, Proceedings of the 16th international conference on World Wide Web, pp.697-706, 2007.

M. Fabian, J. Suchanek, A. Lajus, G. Boschin, and . Weikum, Knowledge representation and rule mining in entity-centric knowledge bases, Reasoning Web. Explainable Artificial Intelligence, pp.110-152, 2019.

F. M. Suchanek, M. Sozio, and G. Weikum, SOFIE: a selforganizing framework for information extraction, 2009.

A. Talmor, J. Herzig, N. Lourie, and J. Berant, Commonsenseqa: A question answering challenge targeting commonsense knowl, 2018.

N. Tandon, G. Gerard-de-melo, and . Weikum, WebChild 2.0: Finegrained commonsense knowledge distillation, ACL, 2017.

G. Thomas-pellissier-tanon, F. M. Weikum, and . Suchanek, Yago 4: A reason-able knowledge base. The Semantic Web, vol.12123, pp.583-596, 2020.

, Inkscape: A vector drawing tool, 2020.

, Metaweb Technologies. The freebase project

D. Vrande?i? and M. Krötzsch, Wikidata: a free collaborative knowledgebase, Communications of the ACM, 2014.

W. Ryen, M. White, W. Richardson, and . Yih, Questions vs. queries in informational search tasks, 2015.

W. Wu, H. Li, H. Wang, and K. Zhu, Probase: a probabilistic taxonomy for text understanding, SIGMOD, 2012.

F. Frank, B. Y. Xu, K. Lin, and . Zhu, Automatic extraction of commonsense locatednear knowledge, ACL, 2018.

M. Yatskar, V. Ordonez, and A. Farhadi, Stating the obvious: Extracting visual common sense knowledge, NAACL, 2016.

R. Zellers, Y. Bisk, R. Schwartz, and Y. Choi, SWAG: A largescale adversarial dataset for grounded commonsense inference, In EMNLP, 2018.

W. Zhong, D. Tang, N. Duan, M. Zhou, J. Wang et al., Improving question answering by commonsense-based pre-training, CCF International Conference on Natural Language Processing and Chinese Computing, pp.16-28, 2019.

H. Zhou, Implementation of the hopcroft's algorithm