Regular Expressions for Data Words
| العنوان: | Regular Expressions for Data Words |
|---|---|
| المؤلفون: | Leonid Libkin, Domagoj Vrgoč |
| المصدر: | Logic for Programming, Artificial Intelligence, and Reasoning ISBN: 9783642287169 LPAR |
| بيانات النشر: | Springer Berlin Heidelberg, 2012. |
| سنة النشر: | 2012 |
| مصطلحات موضوعية: | Register (sociolinguistics), Graph database, Theoretical computer science, Regular language, Computer science, Regular expression, Decision problem, computer.software_genre, Rotation formalisms in three dimensions, computer, Computer Science::Formal Languages and Automata Theory, Data modeling, Automaton |
| الوصف: | In data words, each position carries not only a letter form a finite alphabet, as the usual words do, but also a data value coming from an infinite domain. There has been a renewed interest in them due to applications in querying and reasoning about data models with complex structural properties, notably XML, and more recently, graph databases. Logical formalisms designed for querying such data often require concise and easily understandable presentations of regular languages over data words. Our goal, therefore, is to define and study regular expressions for data words. As the automaton model, we take register automata, which are a natural analog of NFAs for data words. We first equip standard regular expressions with limited memory, and show that they capture the class of data words defined by register automata. The complexity of the main decision problems for these expressions (nonemptiness, membership) also turns out to be the same as for register automata. We then look at a subclass of these regular expressions that can define many properties of interest in applications of data words, and show that the main decision problems can be solved efficiently for it. |
| ردمك: | 978-3-642-28716-9 |
| الوصول الحر: | https://explore.openaire.eu/search/publication?articleId=doi_________::c30de3f844e6af7fddc44da01eeeeeefTest https://doi.org/10.1007/978-3-642-28717-6_22Test |
| حقوق: | OPEN |
| رقم الانضمام: | edsair.doi...........c30de3f844e6af7fddc44da01eeeeeef |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783642287169 |
|---|