The expressibility of languages and relations by word equations

DOI10.1145/337244.337255zbMath1094.68618OpenAlexW2053013024WikidataQ60162918 ScholiaQ60162918MaRDI QIDQ4406307

Juhani Karhumäki, Wojciech Plandowski, Filippo Mignosi

Publication date: 25 June 2003

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/337244.337255

zbMATH Keywords

expressive power of word equations

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (19)

Equations in the Partial Semigroup of Words with Overlapping Products ⋮ Document spanners: from expressive power to decision problems ⋮ Word equations in the context of string solving ⋮ ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS ⋮ Languages generated by conjunctive query fragments of FC[REG] ⋮ Bad News on Decision Problems for Patterns ⋮ First-order concatenation theory with bounded quantifiers ⋮ Unnamed Item ⋮ Z3str2: an efficient solver for strings, regular expressions, and length constraints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph Logics with Rational Relations ⋮ Unnamed Item ⋮ A logic for document spanners ⋮ The hardness of solving simple word equations ⋮ On PSPACE generation of a solution set of a word equation and its applications ⋮ Bad news on decision problems for patterns ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ Multiple factorizations of words and defect effect

This page was built for publication: The expressibility of languages and relations by word equations