Papers

Journal papers

  • J.C. Birget, ``Iteration of expansions, unambiguous semigroups", J. of Pure and Applied Algebra 34 (1984) 1-57.
  • J.C. Birget, ``Arbitrary versus regular semigroups", J. of Pure and Applied Algebra 34 (1984) 57-115.
  • J.C. Birget, J. Rhodes, ``Almost finite expansions of arbitrary semigroups", J. of Pure and Applied Algebra 32 (1984) 239-287.
  • J.C. Birget, ``Stability and J-depth of expansions", Bull. of the Australian Mathematical Society 38 (1988) 41-55.
  • J.C. Birget, ``The Synthesis theorem for finite regular semigroups, and its generalization", J. of Pure and Applied Algebra 55 (1988) 1-79.
  • J.C. Birget, J. Rhodes, ``Group theory via global semigroup theory", J. of Algebra 120 (1989) 284-300.
  • J.C. Birget, ``Concatenation of inputs in a two-way automaton", Theoretical Computer Science 63 (1989) 141-156.
  • J.C. Birget, ``Two-way automaton computations", Informatique Théorique et Applications 24 (1990) 41-66.
  • J.C. Birget, S. Margolis, J. Rhodes, ``Semigroups whose idempotents form a subsemigroup", Bull. of the Australian Mathematical Society 41 (1990) 161-184.
  •  D. Klarner, J.C. Birget, W. Satterfield, ``On the undecidability of the freeness of integer matrix semigroups", Internat. J. of Algebra and Computation 1 (1991) 223-226.
  •  J.C. Birget, ``Strict local testability of the finite control of two-way automata, and of regular picture description languages", International J. of Algebra and Computation 1 (1991) 161-175.
  •  J.C. Birget, ``Positional simulation of two-way automata: Proof of a Conjecture of R. Kannan, and generalizations", J. of Computer and System Sciences (special issue on 1989 ACM STOC) 45 (1992) 154-179.
  •  H. Farhat, J.C. Birget, ``Circuits over monoids: a fault model, and a trade-off between testability and circuit delay", Applied Mathematics Letters 5 (no. 5) (1992) 55-58.
  •  J.C. Birget, ``Intersection and union of regular languages and state complexity", Information Processing Letters 43 (1992) 185-190.
  •  J.C. Birget, ``State-complexity of finite-state devices, state compressibility and incompressibility", Mathematical Systems Theory 26 (1993) 237-269.
  •  J.C. Birget, ``Partial orders on words, minimal elements of regular languages, and state complexity", Theoretical Computer Science 119 (1993) 267-291.
  •  J.C. Birget, S. Margolis, J. Meakin, ``The word problem for inverse semigroups presented by one relator", Theoretical Computer Science 123 (1994) 273-289.
  •  J.C. Birget, J.B. Stephen, ``Formal languages defined by uniform substitutions", Theoretical Computer Science 132 (1994) 243-258.
  •  J.C. Birget, ``Two-way automata and length-preserving homomorphisms", Mathematical Systems Theory 29 (1996) 191-226.
  •  J.C. Birget, ``The state complexity of  A* - A*(A*-L) and its connection with temporal logic", Information Processing Letters 58 (1996) 185-188.
  •  J.C. Birget, ``Time-complexity of the word problem for semigroups and the Higman Embedding Theorem", International J. of Algebra and Computation 8 (1998) 235-294.
  •  J.C. Birget, ``Infinite string rewrite systems and complexity", J. of Symbolic Computation 25 (1998) 759-793.
  •  J.C. Birget, S. Margolis, J. Meakin, ``On the word problem for tensor products and amalgams of monoids", International J. of Algebra and Computation 9 (1999) 271-294.
  •  J.C. Birget, ``Reductions and functors from problems to word problems", Theoretical Computer Science 237 (2000) 81-104.
  •  J.C. Birget, S. Margolis, J. Meakin, P. Weil, ``PSPACE-completeness of certain problems on the subgroups of free groups'', Theoretical Computer Science 242 (2000) 247-281.
  •  Dawei Hong, J.C. Birget, ``Approximation of some NP-hard optimization problems by finite machines, in probability'', Theoretical Computer Science 259 (2001) 323-339.
  •  J.C. Birget, S. Margolis, ``A complete rewrite system and normal forms for  (S)_reg'',  Semigroup Forum, 65 (2002) 348-373. (Earlier version: Mathematics ArXiv math.GR0112229, Dec. 2001.)
  • M.V. Sapir, J.C. Birget, E. Rips, ``Isoperimetric and isodiametric functions of groups'', Annals of Mathematics 156.2 (Sept. 2002) 345-466.   (Earlier version: Mathematics ArXiv,  math.GR/9811105, Nov. 1998.)
  •  J.C. Birget, A. Ol'shanskii, E. Rips, M.V. Sapir, ``Isoperimetric functions of groups and computational complexity of the word problem'', Annals of Mathematics 156.2 (Sept. 2002) 467-518.  (Earlier version:  Mathematics ArXiv, math.GR/9811106, Nov. 1998.)
  •  Dawei Hong, J.C. Birget, ``Deviation bounds for wavelet shrinkage'', IEEE Transactions on Information Theory 49(7) (July 2003) 1851-1858. (Earlier version: Mathematics ArXiv: math.PR/0104200, May 2001.)
  • J.C. Birget, ``Functions on groups and computational complexity'', International J. of Algebra and Computation 14(4) (Aug. 2004) 409-429. (Earlier version: Mathematics ArXiv: http://arXiv.org/abs/math.GR/0202124, Feb. 2002.)
  • J.C. Birget, ``The groups of Richard Thompson and complexity'', International J. of Algebra and Computation, 14(5-6) (Dec. 2004) 569-626. (Earlier version: Mathematics ArXiv: http://arXiv.org/abs/math.GR/0204292, Apr. 2002, revised Oct. 2003.)
  • S. Wiedenbeck, J. Waters, J.C. Birget, A. Brodskiy, N. Memon, ``PassPoints: Design and longitudinal evaluation of a graphical password system'',  International J. of Human-Computer Studies (Special Issue on HCI Research in Privacy and Security), 63 (2005) 102-127. (Check the Graphical Passwords Page.)
  • J.C. Birget, ``Circuits, coNP-completeness, and the groups of Richard Thompson'', International J. of  Algebra and Computation, 16(1) (Feb. 2006) 35-90.  (Slightly expanded version:  Mathematics ArXiv, http://arXiv.org/abs/math.GR/0310335, Oct. 2003.)
  • J.C. Birget, Dawei Hong, Nasir Memon, ``Graphical passwords based on robust discretization'', IEEE Transactions on Information Forensics and Security, 1(3) (Sept. 2006) 395-399.  (Earlier version: Cryptology ePrint Archive, http://eprint.iacr.org/2003/168, Aug. 2003. Revised preliminary version: pdf or ps .) 
  • J.C. Birget, S. Magliveras, M. Sramka, ``On public-key cryptosystems based on combinatorial group theory'', Tatra Mountains Mathematical Publications 33 (2006) 137-148. (Earlier version: Cryptology ePrint Archive, http://eprint.iacr.org/2005/070 , March 2005.)
  • J.C. Birget, S. Margolis, ``Two-letter group codes that preserve aperiodicity of inverse finite automata'', Semigroup Forum, 76 (Jan. 2008) 159-168. (Preprint: Mathematics ArXiv, http://arXiv.org/abs/math.GR/0701264  , Jan. 2007.)
  • J.C. Birget, ``Factorizations of the Thompson-Higman groups, and circuit complexity'', International J. of Algebra and Computation, 18.2 (March 2008) 285-320. (Preprint: Mathematics ArXiv, http://arXiv.org/abs/math.GR/0607349  , July 2006.)
    •  
    Submitted
    - J.C. Birget, ``Monoid generalizations of the Richard Thompson groups'', Mathematics ArXiv, http://arxiv.org/abs/0704.0189 [math.GR]  (Apr. 2, 2007).
    - J.C. Birget, ``One-way permutations, computational asymmetry and distortion'', Mathematics ArXiv, http://arxiv.org/abs/0704.1569 [math.GR]  (12 April 2007).

    Conference papers

  •  J.C. Birget, ``Structure of finite semigroups and generalizations'', Proc. Marquette Conference on Semigroups (1985) pp. 1-15.
  •  J.C. Birget, S. Margolis, J. Rhodes, ``Finite semigroups whose idempotents commute or form a subsemigroup", Proc. Semigroups and their Applications, S. Goberstein and P. Higgins (eds.), Reidel Publishing Co. (1987).
  •  J.C. Birget, ``Basic techniques for two-way finite automata", in Formal Properties of Finite Automata and Applications (J.E. Pin, editor), Proc. LITP Spring School on Theoretical Computer Science, Ramatuelle, France, May 1988, Lecture Notes in Computer Science 386, Springer-Verlag (pp. 56-64).
  •  J.C. Birget, ``Proof of a conjecture of R. Kannan", Proc. 21st Annual ACM Symposium on Theory of Computing (STOC) 1989, pp. 445-453.
  •  J.C. Birget, ``Historical and Technical Perspective on the Synthesis Theorem", in Monoids and Semigroups with Applications (J. Rhodes, editor), Proc. of 1989 Berkeley Workshop, World Scientific Publ. Co. (1991), pp. 393-402.
  • J.C. Birget, S. Margolis, J. Meakin, P. Weil, ``PSPACE-completeness of certain algorithmic problems on the subgroups of free groups", ICALP'94(S. Abiteboul, E. Shamir, eds.), Lecture Notes in Computer Science 820, Springer-Verlag (1994), pp. 274-285.
  •  Dawei Hong, J.C. Birget, ``Probabilistic approximation of some NP optimization problems by finite-state machines", in Randomization and approximation techniques in computer science (RANDOM'97), J. Rolim (ed.), Lecture Notes in Computer Science, Vol. 1269, Springer-Verlag (1997), pp. 151-164.
  •  J.C. Birget, Xukai Zou, G. Noubir, B. Ramamurthy, ``Hierarchy-based access control in distributed environments'', IEEE International Conference on Communications ICC 2001, Helsinki, Finland (June 2001), volume 1, pp. 229-233. (Expanded paper: ps , pdf .)


    • Book edited
    J.C. Birget, S. Margolis, J. Meakin, and M. Sapir, Algorithmic Problems in Groups and Semigroups, Birkhäuser, Boston (2000).

    Electronic reports
    - Leonardo Sobrado, J.C. Birget, ``Graphical passwords'', The Rutgers Scholar, vol. 4 (2002), http://RutgersScholar.rutgers.edu/volume04 .
    - Dawei Hong, J.C. Birget, Shushuang Man, ``Probabilistic behavior of hash tables'',  CS ArXiv http://arXiv.org/abs/cs.DS/0303022  (March 2003).

    Errata
  • Errata for  ``On the undecidability of the freeness of integer matrix semigroups", D. Klarner, J.C. Birget, W. Satterfield,  Internat. J. of Algebra and Computation 1 (1991) 223-226.
  • Errata for  ``Two-way automata and length-preserving homomorphisms", J.C. Birget,  Mathematical Systems Theory 29 (1996) 191-226.
  • Errata for  ``Partial orders on words, minimal elements of regular languages, and state complexity", J.C. Birget, Theoretical Computer Science 119 (1993) 267-291.


    • Oct. 2007