The covering problem

DOI10.23638/LMCS-14(3:1)2018zbMATH Open1448.03026arXiv1707.03370MaRDI QIDQ4580330FDOQ4580330

Authors: Thomas Place, Marc Zeitoun 

Publication date: 15 August 2018

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

Recommendations

• scientific article; zbMATH DE number 6851910
• Deciding classes of regular languages: the covering approach
• Covering and separation for logical fragments with modular predicates
• scientific article; zbMATH DE number 2040900
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words

zbMATH Keywords

first-order logicregular languagesmembership problemcovering problemseparation problemdecidable characterization

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05)

Cites Work

• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Characterizations of locally testable events
• Green's relations and their use in automata theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial closure and unambiguous product
• Separating regular languages with first-order logic
• On separation by locally testable and locally threshold testable languages
• Title not available (Why is that?)
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Efficient separability of regular languages by subsequences and suffixes
• Definability equals recognizability for graphs of bounded treewidth
• First-order definable languages
• Graph congruences and wreath products
• Locally testable languages
• Algebraic decision procedures for local testability
• Separating regular languages with first-order logic
• Separation for dot-depth two
• Title not available (Why is that?)
• Title not available (Why is that?)
• Separating regular languages by piecewise testable and unambiguous languages
• Separation and the successor relation
• The dot-depth hierarchy, 45 years later
• Separating regular languages with two quantifiers alternations
• Regular languages of words over countable linear orderings
• Title not available (Why is that?)
• Theme and variations on the concatenation product

Cited In (29)

• Pointlike sets and separation: a personal perspective
• All about unambiguous polynomial closure
• Covering graphs: The covering problem solved
• A Best Covering Problem.
• On conditional covering problem
• Separating regular languages with two quantifier alternations
• Covering and separation for logical fragments with modular predicates
• The ordered covering problem
• On All Things Star-Free
• Generic results for concatenation hierarchies
• First-order separation over countable ordinals
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Lebesgue universal covering problem
• Title not available (Why is that?)
• The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
• Covering Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Maximal Conditional Covering Problem
• The amazing mixed polynomial closure and its applications to two-variable first-order logic
• The complexity of coverage
• Deciding classes of regular languages: the covering approach
• The Ferry Cover Problem
• Algorithms and Data Structures
• Conelikes and ranker comparisons
• A rectangular cover problem
• Covering Problems
• The covering Canadian traveller problem

This page was built for publication: The covering problem

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