Solvability of Equations in Free Partially Commutative Groups Is decidable

1. A. V. Anisimov and D. E. Knuth. Inhomogeneous sorting. International Journal of Computer and Information Sciences, 8:255–260, 1979.

   Article  MathSciNet  MATH  Google Scholar 

2. M. Benois. Parties rationelles du groupe libre. C. R. Acad. Sci. Paris, Sér. A, 269:1188–1190, 1969.

   MATH  MathSciNet  Google Scholar 

3. V. Diekert. Combinatorics on Traces. LNCS 454. Springer, 1990.

   MATH  Google Scholar 

4. V. Diekert, C. Gutiérrez, and C. Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE-complete. In Proc. 18th Ann. Symp. on Theor. Aspects of Comp. Sci. (STACS’01), LNCS 2010:170–182, Springer, 2001.

   Google Scholar 

5. V. Diekert, Yu. Matiyasevich, and A. Muscholl. Solving word equations modulo partial commutations. Theoretical Computer Science, 224:215–235, 1999. Special issue of LFCS’97.

   Article  MATH  MathSciNet  Google Scholar 

6. V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995.

   Google Scholar 

7. C. Droms. Isomorphisms of graph groups. Proc. American Mathematical Society, 100:407–408, 1987.

   Article  MATH  MathSciNet  Google Scholar 

8. C. Gutiérrez. Satisfiability of equations in free groups is in PSPACE. In Proc. 32nd Ann. ACM Symp. on Theory of Computing, STOC’2000, pp. 21–27. ACM Press 2000.

   Google Scholar 

9. A. Kościelski and L. Pacholski. Makanin’s algorithm is not primitive recursive. Theoretical Computer Science, 191:145–156, 1998.

   Article  MathSciNet  MATH  Google Scholar 

10. D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Ann. Symp. On Found. of Comp. Sci., FOCS’77, pp. 254–266, IEEE Computer Society Press 1977.

    Google Scholar 

11. G. S. Makanin. The problem of solvability of equations in a free semigroup. Math. Sbornik, 103:147–236, 1977. English transl. in Math. USSR Sbornik 32 (1977).

    MathSciNet  Google Scholar 

12. G. S. Makanin. Equations in a free group. Izv. Akad. Nauk SSR, Ser. Math. 46:1199–1273, 1983. English transl. in Math. USSR Izv. 21 (1983).

    MathSciNet  Google Scholar 

13. G. S. Makanin. Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR, Ser. Mat. 48:735–749, 1984. In Russian; English translation in: Math. USSR Izvestija, 25, 75-88, 1985.

    MathSciNet  Google Scholar 

14. Yu. Matiyasevich. Some decision problems for traces. In Proc. 4th Int. Symp. On Log. Found. of Comp. Sci. (LFCS’97), LNCS 1234: 248–257, Springer, 1997. Invited lecture.

    Google Scholar 

15. A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977.

    Google Scholar 

16. A. Mazurkiewicz. Trace theory. In Petri Nets, Applications and Relationship to other Models of Concurrency, LNCS 255: 279–324, Springer, 1987.

    Google Scholar 

17. E. Ochmański. Regular behaviour of concurrent systems. Bulletin of the European Association for Theoretical Computer Science (EATCS), 27:56–67, 1985.

    Google Scholar 

18. E. Ochmański. Recognizable trace languages. In The Book of Traces, Chapter 6: 167–204. World Scientific, Singapore, 1995.

    Google Scholar 

19. W. Plandowski. Satisfiability of word equations with constants is in PSPACE. In Proc. 40th Ann. Symp. on Found. of Comp. Sci., FOCS’99, pages 495–500. IEEE Computer Society Press 1999.

    Google Scholar 

20. K. U. Schulz. Makanin’s algorithm for word equations — Two improvements and a generalization. In Word Equations and Related Topics, LNCS 572: 85–150, Springer 1991.

    Google Scholar 

Download references