@inproceedings{10.1145/3531130.3533371,
    Abstract = {The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary Σ2 formula defines a regular language with a neutral letter, then there is an equivalent Σ2 formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for Σ2 over languages with a neutral letter, the first progress on the Conjecture in more than 20 years. To show the characterization, lower bounds against polynomial-size depth-3 Boolean circuits with constant top fan-in are developed. The heart of the combinatorial argument resides in studying how positions within a language are determined from one another, a technique of independent interest.},
    Address = {New York, NY, USA},
    Author = {Barloy, Corentin and Cadilhac, Michael and Paperman, Charles and Zeume, Thomas},
    BookTitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science},
    File = {The Regular Languages of First-Order Logic with One Alternation - 3531130.3533371.pdf},
    ISBN = {9781450393515},
    Keywords = {descriptive complexity, first-order logic, circuit complexity., automata theory},
    Location = {Haifa, Israel},
    Publisher = {Association for Computing Machinery},
    Series = {LICS '22},
    Title = {The Regular Languages of First-Order Logic with One Alternation},
    URL = {https://doi.org/10.1145/3531130.3533371},
    Year = {2022},
    articleno = {58},
    bdsk-url-1 = {https://doi.org/10.1145/3531130.3533371},
    date-added = {2022-08-29 14:27:27 +0200},
    date-modified = {2022-08-29 14:27:27 +0200},
    numpages = {11},
    doi = {10.1145/3531130.3533371}
}

@inproceedings{10.1145/3531130.3533371, Abstract = {The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary Σ2 formula defines a regular language with a neutral letter, then there is an equivalent Σ2 formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for Σ2 over languages with a neutral letter, the first progress on the Conjecture in more than 20 years. To show the characterization, lower bounds against polynomial-size depth-3 Boolean circuits with constant top fan-in are developed. The heart of the combinatorial argument resides in studying how positions within a language are determined from one another, a technique of independent interest.}, Address = {New York, NY, USA}, Author = {Barloy, Corentin and Cadilhac, Michael and Paperman, Charles and Zeume, Thomas}, BookTitle = {Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science}, File = {The Regular Languages of First-Order Logic with One Alternation - 3531130.3533371.pdf}, ISBN = {9781450393515}, Keywords = {descriptive complexity, first-order logic, circuit complexity., automata theory}, Location = {Haifa, Israel}, Publisher = {Association for Computing Machinery}, Series = {LICS '22}, Title = {The Regular Languages of First-Order Logic with One Alternation}, URL = {https://doi.org/10.1145/3531130.3533371}, Year = {2022}, articleno = {58}, bdsk-url-1 = {https://doi.org/10.1145/3531130.3533371}, date-added = {2022-08-29 14:27:27 +0200}, date-modified = {2022-08-29 14:27:27 +0200}, numpages = {11}, doi = {10.1145/3531130.3533371} }