Loughborough University
Leicestershire, UK
LE11 3TU
+44 (0)1509 263171

# Publications for Manfred Kufleitner

From (year): To (year):

## Journal Articles

Almeida, J, Shahzamanian, MH, Kufleitner, M (2019) Nilpotency and strong nilpotency for finite semigroups, Quarterly Journal of Mathematics, 70(2), pp.619-648, ISSN: 0033-5606. DOI: 10.1093/qmath/hay059.

Fleischer, L and Kufleitner, M (2018) The complexity of weakly recognizing morphisms, RAIRO: Theoretical Informatics and Applications, 53(1-2), pp.1-17, ISSN: 0399-0540. DOI: 10.1051/ita/2018006.

Fleischer, L and Kufleitner, M (2018) Green’s relations in deterministic finite automata, Theory of Computing Systems, 63(4), ISSN: 1432-4350. DOI: 10.1007/s00224-018-9847-4.

Kufleitner, M and Walter, T (2017) Level Two of the quantifier alternation hierarchy over infinite words, Theory of Computing Systems, 62(3), ISSN: 1432-4350. DOI: 10.1007/s00224-017-9801-x.

Kufleitner, M and Wachter, JP (2017) The word problem for omega-terms over the Trotter-Weil hierarchy, Theory of Computing Systems, 62(3), pp.1-57, ISSN: 1432-4350. DOI: 10.1007/s00224-017-9763-z.

Fleischer, L, Kufleitner, M, Lauser, A (2017) The half-levels of the FO2 alternation hierarchy, Theory of Computing Systems, 61(2), pp.352-370, ISSN: 1432-4350. DOI: 10.1007/s00224-016-9712-2.

Diekert, V, Kufleitner, M, Reinhardt, K, Walter, T (2015) Regular languages are Church-Rosser congruential, Journal of the ACM, 62(5), ISSN: 0004-5411. DOI: 10.1145/2808227.

Kufleitner, M and Walter, T (2015) One quantifier alternation in first-order logic with modular predicates, RAIRO - Theoretical Informatics and Applications, 49(1), pp.1-22, ISSN: 0988-3754. DOI: 10.1051/ita/2014024.

Karandikar, P, Kufleitner, M, Schnoebelen, P (2015) On the index of Simon's congruence for piecewise testability, Information Processing Letters, 115(4), pp.515-519, ISSN: 0020-0190. DOI: 10.1016/j.ipl.2014.11.008.

Diekert, V and Kufleitner, M (2015) Omega-rational expressions with bounded synchronization delay, Theory of Computing Systems, 56(4), pp.686-696, ISSN: 1432-4350. DOI: 10.1007/s00224-013-9526-4.

Diekert, V and Kufleitner, M (2014) A survey on the local divisor technique, Theoretical Computer Science, pp.13-23, ISSN: 0304-3975. DOI: 10.1016/j.tcs.2015.07.008.

Diekert, V, Kufleitner, M, Weil, P (2012) Star-free languages are Church–Rosser congruential, Theoretical Computer Science, 454, pp.129-135, ISSN: 0304-3975. DOI: 10.1016/j.tcs.2012.01.028.

KUFLEITNER, M and LAUSER, A (2012) AROUND DOT-DEPTH ONE, International Journal of Foundations of Computer Science, 23(06), pp.1323-1339, ISSN: 0129-0541. DOI: 10.1142/s0129054112400552.

Kufleitner, M and Weil, P (2012) On logical hierarchies withinFOÂ²-definable languages, Logical Methods in Computer Science, 8(3), DOI: 10.2168/lmcs-8(3:11)2012.

Kufleitner, M and Lauser, A (2012) The join of the varieties of R-trivial and L-trivial monoids via combinatorics on words, Discrete Mathematics and Theoretical Computer Science, 14(1), pp.141-146, ISSN: 1462-7264.

Diekert, V, Kufleitner, M, Steinberg, B (2012) The Krohn-Rhodes theorem and local divisors, Fundamenta Informaticae, 116(1-4), pp.65-77, ISSN: 0169-2968. DOI: 10.3233/FI-2012-669.

KUFLEITNER, M and LAUSER, A (2011) PARTIALLY ORDERED TWO-WAY BÜCHI AUTOMATA, International Journal of Foundations of Computer Science, 22(08), pp.1861-1876, ISSN: 0129-0541. DOI: 10.1142/s0129054111009082.

Fouz, M, Kufleitner, M, Manthey, B, Zeini Jahromi, N (2011) On Smoothed Analysis of Quicksort and Hoare's Find, Algorithmica (New York), pp.1-27, ISSN: 0178-4617. DOI: 10.1007/s00453-011-9490-9.

Kufleitner, M and Weil, P (2010) On the lattice of sub-pseudovarieties of DA, Semigroup Forum, 81(2), pp.243-254, ISSN: 0037-1912. DOI: 10.1007/s00233-010-9258-6.

Diekert, V, Horsch, M, Kufleitner, M (2007) On first-order fragments for Mazurkiewicz traces, Fundamenta Informaticae, 80(1-3), pp.1-29, ISSN: 0169-2968.

## Conferences

Kufleitner, M (Accepted for publication) The Height of Factorization Forests. In , pp.443-454, ISBN: 9783540852377. DOI: 10.1007/978-3-540-85238-4_36.

Fleischer, L and Kufleitner, M (2018) The intersection problem for finite monoids. In ,ISBN: 9783959770620. DOI: 10.4230/LIPIcs.STACS.2018.30.

Fleischer, L and Kufleitner, M (2018) Testing Simon’s congruence. In , Liverpool, UK,ISBN: 9783959770866. DOI: 10.4230/LIPIcs.MFCS.2018.62.

Fleischer, L and Kufleitner, M (2017) Green’s relations in finite transformation semigroups. In , Kazan, Russia, pp.112-125, ISBN: 9783319587462. DOI: 10.1007/978-3-319-58747-9_12.

Kufleitner, M and Wachter, JP (2016) The word problem for omega-terms over the Trotter-Weil hierarchy [extended abstract]. In , St. Petersburg, Russia, pp.237-250, ISBN: 9783319341705. DOI: 10.1007/978-3-319-34171-2_17.

Kufleitner, M and Walter, T (2016) Level two of the quantifier alternation hierarchy over infinite words. In , pp.223-236, ISBN: 9783319341705. DOI: 10.1007/978-3-319-34171-2_16.

Diekert, V, Jez, A, Kufleitner, M (2016) Solutions of word equations over partially commutative structures. In , Rome, Italy,ISBN: 9783959770132. DOI: 10.4230/LIPIcs.ICALP.2016.127.

Fleischer, L and Kufleitner, M (2016) Operations on weakly recognizing morphisms. In , pp.126-137, ISBN: 9783319411132. DOI: 10.1007/978-3-319-41114-9_10.

Fleischer, L and Kufleitner, M (2015) Efficient algorithms for morphisms over omega-regular languages. In , pp.112-124, ISBN: 9783939897972. DOI: 10.4230/LIPIcs.FSTTCS.2015.112.

Kufleitner, M (2014) Star-free languages and local divisors. In , pp.23-28, ISBN: 9783319097039. DOI: 10.1007/978-3-319-09704-6_3.

Fleischer, L, Kufleitner, M, Lauser, A (2014) Block products and nesting negations in FO2. In , pp.176-189, ISBN: 9783319066851. DOI: 10.1007/978-3-319-06686-8_14.

Huschenbett, M and Kufleitner, M (2014) Ehrenfeucht-Fraisse games on omega-terms. In , pp.374-385, ISBN: 9783939897651. DOI: 10.4230/LIPIcs.STACS.2014.374.

Kufleitner, M and Lauser, A (2013) Quantifier alternation in two-variable first-order logic with successor is decidable. In , Leibniz International Proceedings in Informatics, LIPIcs, pp.305-316, ISBN: 9783939897507. DOI: 10.4230/LIPIcs.STACS.2013.305.

Diekert, V, Kufleitner, M, Reinhardt, K, Walter, T (2012) Regular languages are Church-Rosser congruential. In International Colloquium on Automata, Languages, and Programming, ICALP 2012, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Warwick, UK, pp.177-188, ISBN: 9783642315848. DOI: 10.1007/978-3-642-31585-5_19.

Kufleitner, M and Weil, P (2012) The FO2 alternation hierarchy is decidable. In , Leibniz International Proceedings in Informatics, LIPIcs, pp.426-439, ISBN: 9783939897422. DOI: 10.4230/LIPIcs.CSL.2012.426.

Kufleitner, M and Lauser, A (2012) The Join Levels of the Trotter-Weil Hierarchy Are Decidable. In , pp.603-614, ISBN: 9783642325885. DOI: 10.1007/978-3-642-32589-2_53.

Kufleitner, M and Lauser, A (2012) Lattices of Logical Fragments over Words. In , pp.275-286, ISBN: 9783642315848. DOI: 10.1007/978-3-642-31585-5_27.

Kufleitner, M and Lauser, A (2012) Lattices of logical fragments over words (extended abstract). In , Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pp.275-286, ISBN: 9783642315848. DOI: 10.1007/978-3-642-31585-5-27.

Jahn, F, Kufleitner, M, Lauser, A (2012) Regular Ideal Languages and Their Boolean Combinations. In , pp.205-216, ISBN: 9783642316050. DOI: 10.1007/978-3-642-31606-7_18.

Diekert, V and Kufleitner, M (2012) Bounded Synchronization Delay in Omega-Rational Expressions. In , pp.89-98, ISBN: 9783642306419. DOI: 10.1007/978-3-642-30642-6_10.

Kallas, J, Kufleitner, M, Lauser, A (2011) First-order fragments with successor over infinite words. In , Leibniz International Proceedings in Informatics, LIPIcs, pp.356-367, ISBN: 9783939897255. DOI: 10.4230/LIPIcs.STACS.2011.356.

Kufleitner, M and Lauser, A (2011) Languages of Dot-Depth One over Infinite Words. In 2011 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011), 2011 IEEE 26th Annual Symposium on Logic in Computer Science,ISBN: 9781457704512. DOI: 10.1109/lics.2011.24.

Diekert, V and Kufleitner, M (2011) Fragments of First-Order Logic over Infinite Words. In , Theory of Computing Systems, pp.486-516, DOI: 10.1007/s00224-010-9266-7.

Kufleitner, M and Lauser, A (2011) Partially Ordered Two-Way Büchi Automata. In , pp.181-190, ISBN: 9783642180972. DOI: 10.1007/978-3-642-18098-9_20.

Dartois, L, Kufleitner, M, Lauser, A (2010) Rankers over Infinite Words (Extended Abstract). In , DEVELOPMENTS IN LANGUAGE THEORY, pp.148-+, ISBN: 978-3-642-14454-7.

Dartois, L, Kufleitner, M, Lauser, A (2010) Rankers over Infinite Words. In , pp.148-159, ISBN: 9783642144547. DOI: 10.1007/978-3-642-14455-4_15.

Kufleitner, M (2009) On bijective variants of the Burrows-Wheeler transform. In , Proceedings of the Prague Stringology Conference 2009, pp.65-79, ISBN: 9788001044032.

Diekert, V and Kufleitner, M (2009) Fragments of first-order logic over infinite words. In , Leibniz International Proceedings in Informatics, LIPIcs, pp.325-336, ISBN: 9783939897095.

Binder, E and Kufleitner, M (2009) Classification tree Sources. In 2009 IEEE Information Theory Workshop,ISBN: 9781424449828. DOI: 10.1109/itw.2009.5351448.

Kufleitner, M and Weil, P (2009) On FO2 Quantifier Alternation over Words. In , MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009, pp.513-+, ISBN: 978-3-642-03815-0.

Fouz, M, Kufleitner, M, Manthey, B, Jahromi, NZ (2009) On Smoothed Analysis of Quicksort and Hoare’s Find. In , pp.158-167, ISBN: 9783642028816. DOI: 10.1007/978-3-642-02882-3_17.

Kufleitner, M and Weil, P (2009) On FO 2 Quantifier Alternation over Words. In , pp.513-524, ISBN: 9783642038150. DOI: 10.1007/978-3-642-03816-7_44.

DIEKERT, V, GASTIN, P, KUFLEITNER, M (2008) A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS. In , International Journal of Foundations of Computer Science, pp.513-548, DOI: 10.1142/s0129054108005802.

Diekert, V and Kufleitner, M (2007) On first-order fragments for words and Mazurkiewicz traces: a survey. In International Conference on Developments in Language Theory, DLT 2007, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Turku, Finland, pp.1-19, ISBN: 3540732071. DOI: 10.1007/978-3-540-73208-2_1.

Kufleitner, M (2007) Polynomials, fragments of temporal logic and the variety DA over traces. In , Theoretical Computer Science, pp.89-100, DOI: 10.1016/j.tcs.2007.01.014.

Kufleitner, M (2006) Polynomials, Fragments of Temporal Logic and the Variety DA over Traces. In , pp.37-48, ISBN: 9783540354284. DOI: 10.1007/11779148_5.

Diekert, V and Kufleitner, M (2003) A Remark about Quadratic Trace Equations. In , pp.59-66, ISBN: 9783540404316. DOI: 10.1007/3-540-45005-x_5.

## Internet Publications

Kufleitner, M and Wächter, JP (Accepted for publication) Two-Variable Ehrenfeucht-Fraisse Games over Omega-Terms.

## Other

Kufleitner, M and Weil, P (Accepted for publication) The FO^2 alternation hierarchy is decidable, We consider the two-variable fragment FO^2[<] of first-order logic over finite words. Numerous characterizations of this class are known. Th\'erien and Wilke have shown that it is decidable whether a given regular language is definable in FO^2[<]. From a practical point of view, as shown by Weis, FO^2[<] is interesting since its satisfiability problem is in NP. Restricting the number of quantifier alternations yields an infinite hierarchy inside the class of FO^2[<]-definable languages. We show that each level of this hierarchy is decidable. For this purpose, we relate each level of the hierarchy with a decidable variety of finite monoids. Our result implies that there are many different ways of climbing up the FO^2[<]-quantifier alternation hierarchy: deterministic and co-deterministic products, Mal'cev products with definite and reverse definite semigroups, iterated block products with J-trivial monoids, and some inductively defined omega-term identities. A combinatorial tool in the process of ascension is that of condensed rankers, a refinement of the rankers of Weis and Immerman and the turtle programs of Schwentick, Th\'erien, and Vollmer. DOI: 10.4230/LIPIcs.CSL.2012.426.

Kufleitner, M (Accepted for publication) A Proof of the Factorization Forest Theorem, We show that for every homomorphism $\Gamma^+ \to S$ where $S$ is a finite semigroup there exists a factorization forest of height $\leq 3 \abs{S}$. The proof is based on Green's relations..

### Getting in touch

Research Office
Loughborough University
Loughborough
Leicestershire
LE11 3TU
researchpolicy@lboro.ac.uk
+44 (0)1509 222453

Research Repository
University Library
Loughborough University
Loughborough
LE11 3TU
repository@lboro.ac.uk
+44 (0)1509 222338 / 222414