On the complexity of intersection non-emptiness for star-free language classes

DOI10.4230/LIPICS.FSTTCS.2021.34MaRDI QIDQ6187048zbMATH OpenFDO

Authors Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Oliveira Mateus de Oliveira, Petra Wolf

Publication date 5 February 2024

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

zbMATH Keywords

commutative languagescomplexitydot-depth hierarchyintersection non-emptiness problemstar-free languagesStraubing-Thérien hierarchy

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• On the complexity of intersecting regular, context-free, and tree languages
• scientific article; zbMATH DE number 2086619
• Hardness results for intersection non-emptiness
• The emptiness problem for intersections of regular languages
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection

Cited in

(4)

• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• Subset mapping problems in solvable automata
• Incremental algorithms for solving regular expression intersection non-emptiness
• Membership problems in finite groups

This page was built for publication: On the complexity of intersection non-emptiness for star-free language classes

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