Claudio Gutiérrez
- 1.V. Diekert, Personal communication, 8 Oct. 1999.Google Scholar
- 2.V. Durnev, Studying Algorithmic Problems for Free Semi-groups and Groups, Proceedings of the 4th International Symposium in Logical Foundations of Computer Science, Yaroslavl 1997. LNCS 1234. Google ScholarDigital Library
- 3.C. Guti(~rrez, Satisfiability of Word Equations with Constants is in Exponential Space, in Proceedings FOCS'98, IEEE Computer Soc. Press, Palo Alto, California, 1998. Google ScholarDigital Library
- 4.C. Guti~rrez, Equations in free Semigroups with antiinvolution and their relation to equations in free Groups, Proceedings of Latin American Theoretical INformatics, LATIN'2000, to appear in LNCS 1776. Also available as Technical Report MA-99-B-474, Departamento de Ingenierfa Matem~tica, Universidad de Chile; and in http://www, wesleyan, edu/~ cgut ierrez/stocO0, ps Google ScholarDigital Library
- 5.Y.I. Kmelevskii, Equations in a free semigroup, Trudy Mat. Inst. Steklov 107(1971); English trans. Proc. Steklov Inst. Math. 107(1971).Google Scholar
- 6.Y.I. Kmelevskii, Systems of equations in a free group I, Izv. Akad. Nauk. SSSR Ser. Mat. 35(1971), 1237-1268; English trans, in Math USSR Izv. 5(1971).Google Scholar
- 7.Y.I. Kmelevskii, Systems of equations in a free group II, Izv. Akad. Nauk. SSSR Set. Mat. 36(1972), 110-179; English trans, in Math USSR Izv. 6(1972).Google Scholar
- 8.A. Ko~cielski, L. Pacholski, Complexity of Makanin's algorithm, J. Assoc. Comput. Mach. 43 (1996) 670-684. Google ScholarDigital Library
- 9.A. Ko~cielski, L. Pacholski, Makanin's algorithm is not primitive recursive, Theoretical Computer Science 191 (1998) 145-156. Google ScholarDigital Library
- 10.A.A. Lorents, Representation of solution sets of systems of equations with one unknown in free groups, Dokl. Akad. Nauk SSSR 178(1968), 290-292; English trans, in Soviet Math. Dokl. 9 (1968).Google Scholar
- 11.Lothaire, M. Combinatorics on Words, Cambridge Mathematical Texts, reprinted 1998.Google Scholar
- 12.R.C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96(1960), 445-457.Google ScholarCross Ref
- 13.G.S. Makanin, The problem of solvability of equations in a free semigroup, Mat. Sbornik 103, 147-236 (in Russian). English translation in Math. USSR Sbornik 32, 129-198.Google Scholar
- 14.G.S. Makanin. Equations in a free group, Izvestiya NA SSSR 46(1982), 1199-1273; English translation in Math USSR Izvestiya, 21 (1983), 483-546.Google Scholar
- 15.G.S. Makanin. Decidability of the universal and positive theories of a free group, Izvestiya NA SSSR 48(1984), 735-749; English translation in Math USSR Izvestiya, 25 (1985), 75-88.Google Scholar
- 16.W. Rytter and W. Plandowski, Applications of Lempel- Ziv encodings to the solution of word equations, in Proceedings of the 25th. ICALP, 1998. Google ScholarDigital Library
- 17.Plandowski, W., $atisfiability of word equations with constants is in NEXPTIME, in Proc. STOC'99. Google ScholarDigital Library
- 18.Plandowski, W., $atisfiability of word equations with constants is in PSPA CE, in Proc. FOCS'99. Google ScholarDigital Library
- 19.A.A. Razborov, On systems of equations in a free group, Izvestiya AN SSSR 48 (1984) 779-832 (in Russian). English translation in Math. USSR Izvestiya 25 (1985) 115- 162.Google Scholar
Index Terms
- Satisfiability of equations in free groups is in PSPACE
Recommendations
A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiabilityWe present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSATCNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Satisfiability of mixed Horn formulas
In this paper the class of mixed Horn formulas is introduced that contain a Horn part and a 2-CNF (conjunctive normal form) (also called quadratic) part. We show that SAT remains NP-complete for such instances and also that any CNF formula can be ...
Backjumping for quantified Boolean logic satisfiability
The implementation of effective reasoning tools for deciding the satisfiability of Quantified Boolean Formulas (QBFs) is an important research issue in Artificial Intelligence. Many decision procedures have been proposed in the last few years, most of ...
Comments