Efficient Separability of Regular Languages by Subsequences and Suffixes

DOI10.1007/978-3-642-39212-2_16zbMath1334.68115arXiv1303.0966OpenAlexW1849255017MaRDI QIDQ5327430

Wojciech Czerwiński, Tomáš Masopust, Wim Martens

Publication date: 7 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

Certifying DFA bounds for recognition and separation ⋮ On Upper and Lower Bounds on the Length of Alternating Towers ⋮ Unnamed Item ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Unnamed Item ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Unnamed Item ⋮ Certifying inexpressibility ⋮ On the height of towers of subsequences and prefixes ⋮ On the index of Simon's congruence for piecewise testability ⋮ Unnamed Item ⋮ Quantifier Alternation for Infinite Words ⋮ Unnamed Item ⋮ Separating regular languages with two quantifier alternations ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ Learning algorithms ⋮ Unnamed Item ⋮ Weak Separation Problem for Tree Languages

Uses Software

• nSPARQL

This page was built for publication: Efficient Separability of Regular Languages by Subsequences and Suffixes