Mia Minnes

My main research interests lie in mathematical logic. Currently, I am focussing on automata and automatic structures. Automata theory has been used to study groups (e.g. Thurston's work on the word problem), has applications in model checking and verification questions (e.g. in databases), and has been used in solving engineering problems such as (near) optimal control of hybrid systems and alternate algorithms for linear programming.

Questions about automatic structures may be grouped into two themes: developing structural characterisations and studying the algorithmic consequences of such characterisations. I have worked in both of these areas, including proving both positive and negative results about the existence of such characterizations. I am interested in answering these guiding questions in the context of less understood classes of structures (e.g. Thurston automatic groups, sequences from symbolic dynamics and combinatorics).

Another line of work seeks to answer "effective algebra" questions in the context of automatic structures. Much work has been done in understanding how the standard results of model theory change when restricted to the framework of computable or polynomial-time objects. Answering analogous questions about automatic structures both gives a better sense of the descriptive power of automata and of the relations between these different models of computation. For example, preliminary work has shown that, like polynomial-time structures (and unlike computable structures), automatic structures have a strong sensitivity to domain representation.

• Publications in refereed journals

  1. Model Theoretic Complexity of Automatic Structures (with B. Khoussainov)
     Paper accepted for publication in Annals of Pure and Applied Logic.
  2. Unary Automatic Locally Finite Graphs:An Algorithmic Perspective (with B. Khoussainov and J. Liu)
     Paper in Mathematical Structures in Computer Science, Volume 19, Special Issue 01, February 2009, pp 133-152; doi:10.1017/S0960129508007342.

• Publications in refereed conference proceedings

  1. Analysing complexity in classes of automatic structures (with J. Liu)
     Extended abstract in Proceedings of LATA '09.
  2. Three Lectures on Automatic Structures (with B. Khoussainov)
     Invited paper in Proceedings of Logic Colloquium '07. F. Delon et al (Eds) Lecture Notes in Logic, 35, pp 132-176.
  3. Model Theoretic Complexity of Automatic Structures (with B. Khoussainov)
     Extended Abstract in M. Agrawal et al (Eds.) TAMC 2008 LNCS 4978 pp 514-525.
  4. Unary Automatic Locally Finite Graphs:An Algorithmic Perspective (with B. Khoussainov and J. Liu)
     Extended Abstract in M. Agrawal et al (Eds.) TAMC 2008 LNCS 4978 pp 548-559.

• Work in progress

  1. Automatic Decision Procedures in Additive Structures

• Unpublished manuscripts

  1. Computability and Complexity Properties of Automatic Structures and their Applications PhD thesis, Cornell University, August 2008. Advisor: Anil Nerode.
  2. Mixed and Integer Linear Programming using Automata Techniques Unpublished manuscript on automata based decision procedures.

• NSF DMS Grant

  DMS-0901005, 2009-2012

• Battig Prize

  Cornell math department award for excellence and promise in mathematics research, 2006.

• NSERC PGS (A, D)

  Canadian graduate research award, 2003-2008.

• Cornell Fellowship

  Cornell entry fellowship for graduate studies, 2003-2004.

• Invited Conference Talks

  • WIMIN'09: Women in Math in New England, plenary speaker 09/2009
    Provisional title: What would Hilbert do? Undecidability and decidabilty in mathematics
  • ASL annual meeting, invited speaker in Computability special session 05/2009
    Automatic Model Theory of Linear Orders
  • MAMLS@Harvard: Mid-Atlantic Mathematical Logic Symposium, invited speaker 05/2009
    Christol's theorem: surprising connections between automaticity, algebraicity, and morphic sequences
  • CMS Annual Meeting: invited speaker in Algorithmic Mathematics special session 12/2008
    Applying automata algorithms to decide graph properties
  • AMS Northeastern Sectional: invited speaker in Computability Theory and Effective Algebra session 10/2008
    Decision procedures for the isomorphism problem in unary automatic structures
  • Algorithmic-Logical Theory of Infinite Structures Dagstuhl Workshop: invited participant 10/2008
    Heights of automatic well-founded relations

• Colloquia and Seminars

  • University of Ottawa Logic Seminar: 7/2009
    Effective algebra: computable and automatic mathematics
  • Connecticut Logic Seminar: 4/2009
    A finite automaton perspective on linear orders
  • MIT Logic Seminar: 4/2009
    A finite automaton perspective on linear orders
  • Notre Dame Logic Seminar: 3/2009
    Open questions in automatic structures
  • CUNY Logic Workshop: 2/2009
    A finite automaton perspective on linear orders
  • University of Colorado at Boulder Math Colloquium: 1/2009
    Complexity of automatic structures
  • UCSD Faculty Colloquium: 4/2008
    Automatic structures: at the interface of classical and feasible mathematics
  • Dartmouth Logic Seminar: 2/2008
    Complexity of Tree Questions based on their Presentations
  • Connecticut Logic Seminar: 9/2007
    Model theoretic properties of automatic structures
  • Victoria University of Wellington Math Seminar: 3/2007
    Automatic Structures of High Ranks
  • University of Auckland Discrete Math and Theoretical CS Seminar: 3/2007
    Automatic Structures of High Ranks
  • Cornell Logic Seminar: Various talks while a graduate student 2004-2008
    • Automatic Sequences: Characterizations via logic, combinatorics, and algebra
    • Using automata to prove tractability
    • The ramified analytic hierarchy and Kreisel compactness
    • Automata and Automatic Structures
    • Ash-Nerode theorem: intrinsically computable sets and forcing
    • Weighted finite-state transducers and applications to speech recognition
    • Automata techniques for deciding Presburger arithmetic
    • Non-omega models: conservativity for WKL_0 over RCA_0 and PRA