Language equations

Language equations are formally specified relations between sets of strings, while this page is under construction.

My work on the subject is listed below.

  1. A. Okhotin, “Decision problems for language equations” (ps, pdf, html), submitted for publication.
  2. A. Okhotin, “Sistemy yazykovykh uravnenii i zamknutye klassy funktsii algebry logiki” (Systems of language equations and closed classes of logic algebra functions) (ps, pdf), in Russian, presented at Discrete Models in the Theory of Control Systems 2003.
  3. A. Okhotin, “The dual of concatenation”, (ps, pdf, slides from the talk: ps, pdf), Proceedings of MFCS 2004.
  4. A. Okhotin, “On computational universality in language equations”, (ps, pdf, slides from the talk: ps, pdf), Proceedings of MCU 2004, to appear.
  5. .
  6. A. Okhotin, “A characterization of the arithmetical hierarchy by language equations”, (ps, pdf, slides from the talk: ps, pdf), Pre-proceedings of DCFS 2004.
  7. A. Okhotin, “Strict language inequalities and their decision problems” (ps), MFCS 2005.
  8. A. Okhotin, “Language equations with symmetric difference” (ps), CSR 2006.
  9. A. Okhotin, “Seven families of language equations” (pdf), AutoMathA 2007 (Palermo, Italy).

Last updates:
19 December, 2005. Written “Language equations with symmetric difference”.
23 March, 2005. Written “Strict language inequalities and their decision problems”.
27 September, 2004. Posted my MCU 2004 slides.
29 July, 2004. Posted my DCFS 2004 slides.
29 June, 2004. This page created.