article

Free access

The expressibility of languages and relations by word equations

Authors:

Juhani Karhumäki,

Filippo Mignosi,

Wojciech PlandowskiAuthors Info & Claims

Journal of the ACM (JACM), Volume 47, Issue 3

Pages 483 - 505

https://doi.org/10.1145/337244.337255

Published: 01 May 2000 Publication History

Abstract

Classically, several properties and relations of words, such as “being a power of the same word” can be expressed by using word equations. This paper is devoted to a general study of the expressive power of word equations. As main results we prove theorems which allow us to show that certain properties of words are not expressible as components of solutions of word equations. In particular, “the primitiveness” and “the equal length” are such properties, as well as being “any word over a proper subalphabet”.

References

[1]

ANGEVIN, D. 1979. Finding patterns common to a set of strings. In Proceedings of llth Annual Symposium on the Theory of Computing (STOC'79) (Atlanta, Ga., Apr. 30-May 2). ACM, New York, pp. 130-141.

[2]

BERSTEL, J., AND PERRIN, D. 1985. Theory of Codes. Academic Press, Orlando, Fla.

[3]

BUJCHI, R., AND SENGER, S. 1986/87. Coding in the existential theory of concatenation. Arch. Math. Logik, 26, 101-106.

[4]

BULITKO, V.K. 1970. Equations and inequalities in a free group and a free semi-group. Tul. Gos. Ped. Inst. Ucen. Zap. Mat. Kafedr. Geometr. i Algebra 2, 242-252, (in Russian).

[5]

CHOFFRUT, C., AND KARHUMAKI, J. 1997. Combinatorics of words. In Handbook of Formal Languages, G. Rozenberg and A. Salomaa, eds. Springer-Verlag, New York, pp. 329-438.

[6]

CULIK, K., II, AND KARHUMAKI, J. 1983. Systems of equations and Ehrenfeucht's conjecture. Discr. Math. 43, 139-153.

[7]

EYONO OBONO, S., GORALCIK, P., AND MAKSIMENKO, M. 1994. Efficient solving of the word equations in one variable. In Proceedings of MFCS'94. Lecture Notes in Computer Science, vol. 841. Springer-Verlag, New York, pp. 336-341.

[8]

HARRISON, M. A. 1978. Introduction to Formal Language Theory. Addison-Wesley Publishing Company, Reading, Mass.

[9]

JIANG, T., SALOMAA, A., SALOMAA, K., AND YU, S. 1995. Decision problems for patterns, J. Cornput. Syst. Sci. 50, 53-63.

[10]

KARHUMAKI, J., MIGNOSI, F., AND PLANDOWSKI, W. 1997. The expressibility of languages and relations by word equations. In ICALP'97. Lecture Notes in Computer Science, vol. 1256. Springer-Verlag, New York, pp. 98-109.

[11]

KHMELEVSKI, YU. I. 1971/1976. Equations in free semigroups, Trudy Mat. Inst. Steklov, 107. (English translation: Proc. Steklov Inst. of Mathematics 107 (1971), American Mathematical Society, Providence, R.I., 1976.)

[12]

KOSCIELSKI, A., AND PACHOLSKI, L. 1996. Complexity of Makanin's algorithm, J. ACM 43, 4, 670-684.

[13]

LENTIN, A. 1972. Equations dans des Monoides Libres. Gouthiers-Villars, Paris, France.

[14]

LOTHAIRE, M. 1983. Combinatorics on Words. Addison-Wesley, Reading, Mass.

[15]

MAKANIN, G.S. 1977. The problem of solvability of equations in a free semigroup. Mat. Sb. 103, (145), 147-233. (English transl, in Math. U.S.S.R. Sb. 32, 1977.)

[16]

MATIJASEVICH, Y. 1970/1971. Enumerable sets are diophantine. Soviet. Math. Doklady 11, 354- 357. (English translation in Dokl. Akad. Nauk SSSR 191, 279-282, 1971.)

[17]

ROZENBERG, G., AND SALOMAA, A. 1980. The Mathematical Theory of L Systems, Academic Press, Orlando, Fla.

[18]

SEIBERT, S. 1992. Quantifier hierarchies and word relations. In Lecture Notes in Computer Science, vol. 626. Springer-Verlag, New York, pp. 329-338.

Cited By

Murwanashyaka J(2024)Hilbert’s tenth problem for term algebras with a substitution operatorComputability10.3233/COM-230444(1-25)Online publication date: 11-Sep-2024
https://doi.org/10.3233/COM-230444
Thompson SFreydenberger D(2024)Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FCProceedings of the ACM on Management of Data10.1145/36511432:2(1-18)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651143
Thompson SFreydenberger D(2024)Languages Generated by Conjunctive Query Fragments of FC[REG]Theory of Computing Systems10.1007/s00224-024-10198-468:6(1640-1682)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00224-024-10198-4
Show More Cited By

Index Terms

The expressibility of languages and relations by word equations
1. Theory of computation
  1. Logic

Recommendations

The Expressibility of Languages and Relations by Word Equations
Word Equations with One Unknown
DLT '09: Proceedings of the 13th International Conference on Developments in Language Theory

We consider properties of the solution set of a word equation with one unknown. We prove that the solution set of a word equation possessing infinite number of solutions is of the form ( pq )^* p where pq is primitive. Next, we prove that a word ...
On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note)
Abstract
Denote by SWE the satisfiability problem for word equations. Consider the problem of computability of the maximal exponent of periodicity for word equations MaxExpProblem ( e , k ) in which given positive integer k and a word equation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 47, Issue 3

May 2000

168 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/337244

Issue’s Table of Contents

Copyright © 2000 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 2000

Published in JACM Volume 47, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

word equations

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
1,133
Total Downloads

Downloads (Last 12 months)157
Downloads (Last 6 weeks)15

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Murwanashyaka J(2024)Hilbert’s tenth problem for term algebras with a substitution operatorComputability10.3233/COM-230444(1-25)Online publication date: 11-Sep-2024
https://doi.org/10.3233/COM-230444
Thompson SFreydenberger D(2024)Generalized Core Spanner Inexpressibility via Ehrenfeucht-Fraïssé Games for FCProceedings of the ACM on Management of Data10.1145/36511432:2(1-18)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651143
Thompson SFreydenberger D(2024)Languages Generated by Conjunctive Query Fragments of FC[REG]Theory of Computing Systems10.1007/s00224-024-10198-468:6(1640-1682)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1007/s00224-024-10198-4
Day JGanesh VGrewal NKonefal MManea F(2024)A Closer Look at the Expressive Power of Logics Based on Word EquationsTheory of Computing Systems10.1007/s00224-023-10154-868:3(322-379)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00224-023-10154-8
Day JManea F(2024)On the structure of solution-sets to regular word equationsTheory of Computing Systems10.1007/s00224-021-10058-568:4(662-739)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00224-021-10058-5
Day JGanesh VGrewal NManea F(2023)On the Expressive Power of String ConstraintsProceedings of the ACM on Programming Languages10.1145/35712037:POPL(278-308)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571203
Lotz KGoel ADutertre BKiesl-Reiter BKong SMajumdar RNowotka D(2023)Solving String Constraints Using SATComputer Aided Verification10.1007/978-3-031-37703-7_9(187-208)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-37703-7_9
Thompson SFreydenberger D(2023)Languages Generated by Conjunctive Query Fragments of FC[REG]Developments in Language Theory10.1007/978-3-031-33264-7_19(233-245)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-33264-7_19
Kulczynski MLotz KNowotka DPoulsen D(2022)Solving String Theories Involving Regular Membership Predicates Using SATModel Checking Software10.1007/978-3-031-15077-7_8(134-151)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-15077-7_8
Day J(2022)Word Equations in the Context of String SolvingDevelopments in Language Theory10.1007/978-3-031-05578-2_2(13-32)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-05578-2_2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents