PROGRAM SYSTEMS: THEORY AND APPLICATIONS

12+

 

Online Scientific Journal published by the Ailamazyan Program Systems Institute of the Russian Academy of Sciences

Mathematical Foundations of Programming
Methods for Optimal Control and Control Theory

Papers are accepted in the form of a PDF file

To view the PDF files, you will need Adobe Acrobat Reader

    


• Содержание выпуска •
• Mathematical Foundations of Programming •
• Methods for Optimal Control and Control Theory •

Mathematical Foundations of Programming

Responsible for the Section: doctor of physico-mathematical Sciences Nikolay Nepeivoda

On the left: assigned number of the paper, submission date, the number of A5 pages contained in the paper, and the reference to the full-text PDF .

 

Article # 6_2018

19 p.

PDF

submitted on 16th May 2018 displayed on website on 05th June 2018

 

Antonina Nepeivoda
On solving quadratic word equations


Word equations are natural constraints in an automatic analysis of string manipulating programs. In particular, equations with at most two occurrences of each variable (quadratic word equations) are of interest of the analysis. The algorithm solving such equations with the exponential complexity is given by Yu. Hmelevskij in 1971. V. Diekert in 1999 proved that the satisfiability problem for the quadratic word equations is NP-hard. In this paper we suggest some refinements of Hmelevskij’s algorithm to make it more applicable in the automatic analysis of programs. We consider the length analysis and splitting procedures and show when these refinements can be used to extract explicit solutions of the equations and when they can be used only for deciding satisfiability. (In Russian).


Key words: supercompilation, word equations.

article citation

 http://psta.psiras.ru/read/psta2018_2_3-21.pdf

DOI

https://doi.org/10.25209/2079-3316-2018-9-2-3-21

• Содержание выпуска •
• Mathematical Foundations of Programming •
• Methods for Optimal Control and Control Theory •

 

Adress: Ailamazyan Program Systems Institute of the Russian Academy of Sciences, PSTA Online Journal, 4 a Peter the First Street,
Veskovo village, Pereslavl area, Yaroslavl region, 152021 Russia
Phone: +7-4852-695-228.       E-mail: info@psta.psiras.ru.      Website: http://psta.psiras.ru

© Electronic Scientific Journal "Program Systems: Theory and Applications" 2010-2017
© Ailamazyan Program System Institute of RAS 2010-2018