@book(almeida, author = "J. Almeida", year = "1994", title = "Finite semigroups and universal algebra", publisher = "World Scientific", address = "Singapore", doi = "10.1142/2481", ) @inproceedings(almeida-survey, author = "J. Almeida", year = "2005", title = "Profinite semigroups and applications", editor = "V.B. Kudryavtsev and I.G. Rosenberg and M. Goldstein", booktitle = "Structural theory of automata, semigroups, and universal algebra", series = "NATO Science Series II: Mathematics, Physics and Chemistry", volume = "207", publisher = "Springer", pages = "1--45", doi = "10.1007/1-4020-3817-8_1", ) @inproceedings(arfi, author = "M. Arfi", year = "1987", title = "Polynomial Operations on Rational Languages", editor = "F.-J. Brandenburg and G. Vidal-Naquet and M. Wirsing", booktitle = "STACS", series = "Lecture Notes in Computer Science", volume = "247", publisher = "Springer", pages = "198--206", doi = "10.1007/BFb0039607", ) @inproceedings(broz-minimal, author = "J. Brzozowski", year = "1962", title = "Canonical regular expressions and minimal state graphs for definite events", booktitle = "Mathematical theory of Automata", series = "Symposia series", volume = "12", publisher = "Research Institute, Brooklyn", pages = "529--561", ) @inproceedings(broz-j-triv, author = "J. Brzozowski and B. Li", year = "2013", title = "Syntactic Complexity of R- and J-Trivial Regular Languages", editor = "H. J{\"u}rgensen and R. Reis", booktitle = "DCFS", series = "Lecture Notes in Computer Science", volume = "8031", publisher = "Springer", pages = "160--171", doi = "10.1007/978-3-642-39310-5_16", ) @article(pin-str, author = "L. Chaubard and J.-{\'E}. Pin and H. Straubing", year = "2006", title = "Actions, wreath products of {\it C}-varieties and concatenation product", journal = "Theor. Comput. Sci.", volume = "356", number = "1-2", pages = "73--89", doi = "10.1016/j.tcs.2006.01.039", ) @article(dot-hierarchy, author = "R. Cohen and J. Brzozowski", year = "1971", title = "Dot-Depth of Star-Free Events", journal = "J. Comput. Syst. Sci.", volume = "5", number = "1", pages = "1--16", doi = "10.1016/S0022-0000(71)80003-X", ) @article(diekert-survey, author = "V. Diekert and P. Gastin and M. Kufleitner", year = "2008", title = "A Survey on Small Fragments of First-Order Logic over Finite Words", journal = "Int. J. Found. Comput. Sci.", volume = "19", number = "3", pages = "513--548", doi = "10.1142/S0129054108005802", ) @book(eilenberg, author = "S. Eilenberg", year = "1976", title = "Automata, Languages and Machines, vol.~B.", publisher = "Academic Press", ) @article(esik-ito, author = "Z. {\'E}sik and M. Ito", year = "2003", title = "Temporal Logic with Cyclic Counting and the Degree of Aperiodicity of Finite Automata", journal = "Acta Cybern.", volume = "16", number = "1", pages = "1--28", url = "http://www.inf.u-szeged.hu/actacybernetica/edb/vol16n1/Esik_2003_ActaCybernetica.xml", ) @article(esik-ivan, author = "Z. {\'E}sik and S. Iv{\'a}n", year = "2008", title = "Some Varieties of Finite Tree Automata Related to Restricted Temporal Logics", journal = "Fundam. Inform.", volume = "82", number = "1-2", pages = "79--103", url = "http://iospress.metapress.com/content/4216mrh7r6477172/", ) @article(esik-larsen, author = "Z. {\'E}sik and K.G. Larsen", year = "2003", title = "Regular languages definable by Lindstr{\"o}m quantifiers", journal = "RAIRO - Theoretical Informatics and Applications", volume = "37", number = "3", pages = "179--241", doi = "10.1051/ita:2003017", ) @inproceedings(pin-lattices, author = "M. Gehrke and S. Grigorieff and J.-{\'E}. Pin", year = "2008", title = "Duality and Equational Theory of Regular Languages", editor = "L. Aceto and I. Damg{\r a}rd and L.A. Goldberg and M.M. Halld{\'o}rsson and A. Ing{\'o}lfsd{\'o}ttir and I. Walukiewicz", booktitle = "ICALP (2)", series = "Lecture Notes in Computer Science", volume = "5126", publisher = "Springer", pages = "246--257", doi = "10.1007/978-3-540-70583-3_21", ) @inproceedings(ncma13-holzer, author = "M. Holzer and S. Jakobi", year = "2013", title = "Minimization and characterizations for biautomata", editor = "S. Bensch and F. Drewes and R. Freund and F. Otto", booktitle = "NCMA", volume = "294", publisher = "{\"O}sterreichische Computer Gesellschaft", pages = "179--193", ) @phdthesis(kamp, author = "H. Kamp", year = "1968", title = "Tense logic and theory of linear orders", school = "University of California", ) @article(meet-automata, author = "O. Kl\'{\i }ma and L. Pol{\'a}k", year = "2008", title = "On varieties of meet automata", journal = "Theor. Comput. Sci.", volume = "407", number = "1-3", pages = "278--289", doi = "10.1016/j.tcs.2008.06.005", ) @article(biautomaty, author = "O. Kl\'{\i }ma and L. Pol{\'a}k", year = "2012", title = "On biautomata", journal = "RAIRO - Theor. Inf. and Applic.", volume = "46", number = "4", pages = "573--592", doi = "10.1051/ita/2012014", ) @inproceedings(dlt13-klima, author = "O. Kl\'{\i }ma and L. Pol{\'a}k", year = "2013", title = "Alternative Automata Characterization of Piecewise Testable Languages", editor = "M.-P. B{\'e}al and O. Carton", booktitle = "Developments in Language Theory", series = "Lecture Notes in Computer Science", volume = "7907", publisher = "Springer", pages = "289--300", doi = "10.1007/978-3-642-38771-5_26", ) @article(weil-logic, author = "M. Kufleitner and P. Weil", year = "2012", title = "On logical hierarchies within FO$^{\unhbox \voidb@x \hbox {2}}$-definable languages", journal = "Logical Methods in Computer Science", volume = "8", number = "3", doi = "10.2168/LMCS-8(3:11)2012", ) @article(michal, author = "M. Kunc", year = "2003", title = "Equational description of pseudovarieties of homomorphisms", journal = "RAIRO - Theoretical Informatics and Applications", volume = "37", number = "3", pages = "243--254", doi = "10.1051/ita:2003018", ) @inproceedings(lattice-automata, author = "O. Kupferman and Y. Lustig", year = "2007", title = "Lattice Automata", editor = "B. Cook and A. Podelski", booktitle = "VMCAI", series = "Lecture Notes in Computer Science", volume = "4349", publisher = "Springer", pages = "199--213", doi = "10.1007/978-3-540-69738-1_14", ) @inproceedings(lombardy, author = "S. Lombardy and J. Sakarovitch", year = "2008", title = "The universal automaton", editor = "J. Flum and E. Gr{\"a}del and T. Wilke", booktitle = "Logic and Automata", series = "Texts in Logic and Games", volume = "2", publisher = "Amsterdam University Press", pages = "457--504", ) @book(McNaughton, author = "R. McNaughton and S. Papert", year = "1971", title = "Counter-Free Automata", publisher = "M.I.T. Press", ) @article(pin-positive, author = "J.-{\'E}. Pin", year = "1995", title = "A Variety Theorem Without Complementation", journal = "Russian Mathematics", volume = "39", pages = "80--90", url = "http://www.liafa.jussieu.fr/~jep/publications.html", ) @inproceedings(pin-handbook, author = "J.-{\'E}. Pin", year = "1997", title = "Syntactic semigroups", editor = "G. Rozenberg and A. Salomaa", booktitle = "Handbook of Formal Languages", volume = "1", publisher = "Springer", pages = "679--746", doi = "10.1007/978-3-642-59136-5_10", url = "www.liafa.jussieu.fr/~jep/publications.html", ) @article(pin-survey, author = "J.-{\'E}. Pin", year = "2012", title = "Equational Descriptions of Languages", journal = "Int. J. Found. Comput. Sci.", volume = "23", number = "6", pages = "1227--1240", doi = "10.1142/S0129054112400497", ) @article(pin-weil, author = "J.-{\'E}. Pin and P. Weil", year = "1996", title = "A Reiterman theorem for pseudovarieties of finite first-order structures", journal = "Algebra Universalis", volume = "35", number = "4", pages = "577--595", doi = "10.1007/BF01243597", ) @article(pin-pulky, author = "J.-{\'E}. Pin and P. Weil", year = "1997", title = "Ponynominal Closure and Unambiguous Product", journal = "Theory Comput. Syst.", volume = "30", number = "4", pages = "383--422", doi = "10.1007/BF02679467", ) @article(zeitoun-separ, author = "T. Place and M. Zeitoun", year = "2014", title = "Separating Regular Languages with First-Order Logic", journal = "CoRR", volume = "abs/1402.3277", url = "http://arxiv.org/abs/1402.3277", ) @article(polak-brno, author = "L. Pol{\'a}k", year = "2004", title = "A classification of rational languages by semilattice-ordered monoids", journal = "Archivum Mathematicum", volume = "40", number = "4", pages = "395--406", url = "http://emis.muni.cz/journals/AM/04-4/index.html", ) @article(polak-universal, author = "L. Pol{\'a}k", year = "2005", title = "Minimalizations of NFA using the universal automaton", journal = "Int. J. Found. Comput. Sci.", volume = "16", number = "5", pages = "999--1010", doi = "10.1142/S0129054105003431", ) @article(reiterman, author = "J. Reiterman", year = "1982", title = "The Birkhoff theorem for finite algebras", journal = "Algebra Universalis", volume = "14", pages = "1--10", doi = "10.1007/BF02483902", ) @book(steinberg, author = "J. Rhodes and B. Steinberg", year = "2009", title = "The q-theory of Finite Semigroups", series = "Monographs in Mathematics", publisher = "Springer", doi = "10.1007/b104443", ) @article(schutz, author = "M. P. Sch{\"u}tzenberger", year = "1965", title = "On Finite Monoids Having Only Trivial Subgroups", journal = "Information and Control", volume = "8", number = "2", pages = "190--194", doi = "10.1016/S0019-9958(65)90108-7", ) @inproceedings(therien-32, author = "T. Schwentick and D. Th{\'e}rien and H. Vollmer", year = "2001", title = "Partially-Ordered Two-Way Automata: A New Characterization of DA", editor = "W. Kuich and G. Rozenberg and A. Salomaa", booktitle = "Developments in Language Theory", series = "Lecture Notes in Computer Science", volume = "2295", publisher = "Springer", pages = "239--250", doi = "10.1007/3-540-46011-X_20", ) @inproceedings(simon-pw, author = "I. Simon", year = "1975", title = "Piecewise testable events", editor = "H. Barkhage", booktitle = "Automata Theory and Formal Languages", series = "Lecture Notes in Computer Science", volume = "33", publisher = "Springer", pages = "214--222", doi = "10.1007/3-540-07407-4_23", ) @article(stern, author = "J. Stern", year = "1985", title = "Complexity of Some Problems from the Theory of Automata", journal = "Information and Control", volume = "66", number = "3", pages = "163--176", doi = "10.1016/S0019-9958(85)80058-9", ) @article(str-hierarchy, author = "H. Straubing", year = "1981", title = "A Generalization of the Sch{\"u}tzenberger Product of Finite Monoids", journal = "Theor. Comput. Sci.", volume = "13", pages = "137--150", doi = "10.1016/0304-3975(81)90036-0", ) @inproceedings(straubing, author = "H. Straubing", year = "2002", title = "On Logical Descriptions of Regular Languages", editor = "S. Rajsbaum", booktitle = "LATIN", series = "Lecture Notes in Computer Science", volume = "2286", publisher = "Springer", pages = "528--538", doi = "10.1007/3-540-45995-2_46", ) @inproceedings(str-weil, author = "H. Straubing and P. Weil", year = "2012", title = "An introduction to finite automata and their connection to logic", editor = "D. D'Souza and P. Shankar", booktitle = "Modern Applications of Automata Theory", series = "IISc Research Monographs Series", publisher = "World Scientific", doi = "10.1142/9789814271059_0001", url = "http://arxiv.org/abs/1011.6491", ) @article(therien-hierarchy, author = "D. Th{\'e}rien", year = "1981", title = "Classification of Finite Monoids: The Language Approach", journal = "Theor. Comput. Sci.", volume = "14", pages = "195--208", doi = "10.1016/0304-3975(81)90057-8", ) @article(thomas, author = "W. Thomas", year = "1982", title = "Classifying Regular Events in Symbolic Logic", journal = "J. Comput. Syst. Sci.", volume = "25", number = "3", pages = "360--376", doi = "10.1016/0022-0000(82)90016-2", ) @inproceedings(trahtman, author = "A. Trahtman", year = "2001", title = "Piecewise and Local Threshold Testability of DFA", editor = "R. Freivalds", booktitle = "FCT", series = "Lecture Notes in Computer Science", volume = "2138", publisher = "Springer", pages = "347--358", doi = "10.1007/3-540-44669-9_33", ) @inproceedings(weil-survey, author = "P. Weil", year = "2004", title = "Algebraic Recognizability of Languages", editor = "J. Fiala and V. Koubek and J. Kratochv\'{\i }l", booktitle = "MFCS", series = "Lecture Notes in Computer Science", volume = "3153", publisher = "Springer", pages = "149--175", doi = "10.1007/978-3-540-28629-5_8", url = "http://arxiv.org/abs/cs/0609110", )