1
$\begingroup$

What maps to Semantic Analysis the way automata like Finite State Machines and Pushdown automatons map to Lexing and Parsing?

A couple of years ago I came across a paper that presented such a construct; I don't remember much about the paper to be useful, but here's what I think I remember:

  1. I think the paper was from the late 80s or early 90s,
  2. The construct had/employed a double-ended queue,
  3. Elements were replaced in the queue until the replacement rules could no longer be applied [and replacements were longer sequences than what they replaced],
  4. The paper mentioned that while it mapped to the Semantic Analysis, it was somewhat unwieldy to use.

Any help locating this paper would be most welcome, as would info on other constructs mapping to Semantic Analysis.

Thank you.

Improve this question
$\endgroup$
2
  • $\begingroup$ repeated substring replacing is turing complete. $\endgroup$
    – ratchet freak
    Jun 20, 2017 at 14:13
  • $\begingroup$ @ratchetfreak -- I hadn't heard that. That's interesting. $\endgroup$
    – Shark8
    Jun 20, 2017 at 19:37

1 Answer 1

Reset to default
1
$\begingroup$

Repeated substring string replacement is Turing complete.

To emulate a Turing machine you can use the following:

The current string encodes the tape with a new symbol $\$$ followed by an encoding of the current state inserted before the position where the current head is. The allowed replacements can be encoded by taking each transition $\delta(n, b) = (m, c, N|L|R)$ by creating the replacement rules to replace $a\$nb$ with $a\$mc$ $\$mac$ or $ac\$m$ for not moving the head or moving it left or right where a is every symbol in the alphabet.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.