Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete

DOI10.1137/090777669zbMath1348.68060arXiv0911.3674OpenAlexW2963693828MaRDI QIDQ3020012

Sebastian Maneth, Guillem Godoy, Omer Giménez

Publication date: 29 July 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0911.3674

zbMATH Keywords

regularitypattern matchingregular constraintsEXPTIME-complexityterms with variables

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Excessively duplicating patterns represent non-regular languages ⋮ The HOM Problem is EXPTIME-Complete

This page was built for publication: Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete