The Height of Piecewise-Testable Languages with Applications in Logical Complexity

DOI10.4230/LIPIcs.CSL.2016.37zbMath1369.68221OpenAlexW2963282839MaRDI QIDQ5278426

Prateek Karandikar, Philippe Schnoebelen

Publication date: 19 July 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6577/

zbMATH Keywords

descriptive complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Descriptive complexity and finite models (68Q19)

Related Items (13)

On Boolean combinations forming piecewise testable languages ⋮ Scattered Factor-Universality of Words ⋮ Absent Subsequences in Words ⋮ Ranking and Unranking k-Subsequence Universal Words ⋮ Longest Common Subsequence with Gap Constraints ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Absent subsequences in words ⋮ Unnamed Item ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ On shuffle products, acyclic automata and piecewise-testable languages ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence ⋮ Unnamed Item ⋮ Nearly \(k\)-universal words -- investigating a part of Simon's congruence

This page was built for publication: The Height of Piecewise-Testable Languages with Applications in Logical Complexity