Independent Languages and Witnesses of Dependence (Non-satisfaction)
Abstract
We consider the independent language property defined by the language equation Ï(X)=\emptyset, where the expression Ï involves the language variable X, constant languages, and standard regular operations including transductions, but not complementation. This property consists of all languages L satisfying Ï(L)=\emptyset. Depending on the choice of the operations in Ï, the equation defines a broad class of codes, including combinations of standard variable-length codes and error-detecting codes. We show that any Ï-independence is a Jürgensen independence, we define what a witness of non-satisfaction of Ï(X)=\emptyset is, for a language L, and we show how to compute a witness of non-satisfaction when L is regular. We also discuss the complexity of the problem, showing that the decision version of the problem is PSPACE-complete.
- Comment
- In Proceedings AFL 2026, arXiv:2608.23071
- Journal ref
- EPTCS 451, 2026, pp. 201-216
- DOI
- 10.4204/EPTCS.451.14