Adding Successor

DOI10.1145/3356339MaRDI QIDQ4972173zbMATH OpenOpenAlexFDO

Authors Thomas Place, Marc Zeitoun

Publication date 22 November 2019

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.10052

zbMATH Keywords

covering problemdecidable characterizationfirst-order logicmembership problemregular languagesseparation problem

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Abstract: Given a class C of word languages, the C-separation problem asks for an algorithm that, given as input two regular languages, decides whether there exists a third language in C containing the first language, while being disjoint from the second. Separation is usually investigated as a means to obtain a deep understanding of the class C. In the paper, we are mainly interested in classes defined by logical formalisms. Such classes are often built on top of each other: given some logic, one builds a stronger one by adding new predicates to its signature. A natural construction is to enrich a logic with the successor relation. In this paper, we present a transfer result applying to this construction: we show that for suitable logically defined classes, separation for the logic enriched with the successor relation reduces to separation for the original logic. Our theorem also applies to a problem that is stronger than separation: covering. Moreover, we actually present two reductions: one for languages of finite words and the other for languages of infinite words.

Recommendations

• scientific article; zbMATH DE number 3990341
• scientific article; zbMATH DE number 1066342
• Additive completion and disjoint translations
• Addendum to ``Structure theorem for multiple addition
• scientific article; zbMATH DE number 851546
• A Generalization of the Handle Addition Theorem
• Additivity numbers of covering properties
• Transfering saturation, the finite cover property, and stability
• Addition theorems and representations of topological semigroups
• ADDITIVE COVERS AND THE CANONICAL BASE PROPERTY

Cited in

(13)

• Varieties
• Generic results for concatenation hierarchies
• Separation and the successor relation
• Transfering saturation, the finite cover property, and stability
• The Complexity of Separation for Levels in Concatenation Hierarchies
• Separation for dot-depth two
• Covering and separation for logical fragments with modular predicates
• Living without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• All about unambiguous polynomial closure
• The amazing mixed polynomial closure and its applications to two-variable first-order logic
• Deterministic and game separability for regular languages of infinite trees
• Pointlike sets and separation: a personal perspective

This page was built for publication: Adding Successor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972173)