Graph Logics with Rational Relations
We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications. Such logics use conditions on paths expressed by regular languages...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2013-07-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/664/pdf |
| _version_ | 1827322945274380288 |
|---|---|
| author | Pablo Barcelo Diego Figueira Leonid Libkin |
| author_facet | Pablo Barcelo Diego Figueira Leonid Libkin |
| author_sort | Pablo Barcelo |
| collection | DOAJ |
| description | We investigate some basic questions about the interaction of regular and
rational relations on words. The primary motivation comes from the study of
logics for querying graph topology, which have recently found numerous
applications. Such logics use conditions on paths expressed by regular
languages and relations, but they often need to be extended by rational
relations such as subword or subsequence. Evaluating formulae in such extended
graph logics boils down to checking nonemptiness of the intersection of
rational relations with regular or recognizable relations (or, more generally,
to the generalized intersection problem, asking whether some projections of a
regular relation have a nonempty intersection with a given rational relation).
We prove that for several basic and commonly used rational relations, the
intersection problem with regular relations is either undecidable (e.g., for
subword or suffix, and some generalizations), or decidable with
non-primitive-recursive complexity (e.g., for subsequence and its
generalizations). These results are used to rule out many classes of graph
logics that freely combine regular and rational relations, as well as to
provide the simplest problem related to verifying lossy channel systems that
has non-primitive-recursive complexity. We then prove a dichotomy result for
logics combining regular conditions on individual paths and rational relations
on paths, by showing that the syntactic form of formulae classifies them into
either efficiently checkable or undecidable cases. We also give examples of
rational relations for which such logics are decidable even without syntactic
restrictions. |
| first_indexed | 2024-04-25T01:36:52Z |
| format | Article |
| id | doaj.art-abea23cf62c84ff4a93b5be4e5233144 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:36:52Z |
| publishDate | 2013-07-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-abea23cf62c84ff4a93b5be4e52331442024-03-08T09:29:28ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742013-07-01Volume 9, Issue 310.2168/LMCS-9(3:1)2013664Graph Logics with Rational RelationsPablo BarceloDiego Figueirahttps://orcid.org/0000-0003-0114-2257Leonid Libkinhttps://orcid.org/0000-0002-6698-2735We investigate some basic questions about the interaction of regular and rational relations on words. The primary motivation comes from the study of logics for querying graph topology, which have recently found numerous applications. Such logics use conditions on paths expressed by regular languages and relations, but they often need to be extended by rational relations such as subword or subsequence. Evaluating formulae in such extended graph logics boils down to checking nonemptiness of the intersection of rational relations with regular or recognizable relations (or, more generally, to the generalized intersection problem, asking whether some projections of a regular relation have a nonempty intersection with a given rational relation). We prove that for several basic and commonly used rational relations, the intersection problem with regular relations is either undecidable (e.g., for subword or suffix, and some generalizations), or decidable with non-primitive-recursive complexity (e.g., for subsequence and its generalizations). These results are used to rule out many classes of graph logics that freely combine regular and rational relations, as well as to provide the simplest problem related to verifying lossy channel systems that has non-primitive-recursive complexity. We then prove a dichotomy result for logics combining regular conditions on individual paths and rational relations on paths, by showing that the syntactic form of formulae classifies them into either efficiently checkable or undecidable cases. We also give examples of rational relations for which such logics are decidable even without syntactic restrictions.https://lmcs.episciences.org/664/pdfcomputer science - formal languages and automata theory |
| spellingShingle | Pablo Barcelo Diego Figueira Leonid Libkin Graph Logics with Rational Relations Logical Methods in Computer Science computer science - formal languages and automata theory |
| title | Graph Logics with Rational Relations |
| title_full | Graph Logics with Rational Relations |
| title_fullStr | Graph Logics with Rational Relations |
| title_full_unstemmed | Graph Logics with Rational Relations |
| title_short | Graph Logics with Rational Relations |
| title_sort | graph logics with rational relations |
| topic | computer science - formal languages and automata theory |
| url | https://lmcs.episciences.org/664/pdf |
| work_keys_str_mv | AT pablobarcelo graphlogicswithrationalrelations AT diegofigueira graphlogicswithrationalrelations AT leonidlibkin graphlogicswithrationalrelations |