Descriptional Complexity of Formal Systems

Erik D Demaine, S. E., Shallit, J., & Wilson, D. A. (2011). Descriptional Complexity of Formal Systems: 13th International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011, Proceedings. Springer-Verlag.

Type

Book chapter

Intellectual base

Review or monograph

Year

2011

DOI

10.1007/978-3-642-22600-7_12

Link

https://doi.org/10.1007/978-3-642-22600-7_12

Cited by

1 citation across 1 artifact.

Domain-specific

• Separating words problem
  • Given distinct strings w and x, the separating-words problem minimizes DFA states subject to opposite acceptance outcomes for those two inputs, with alphabet and encoding conventions fixed.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:7141a399b797 · see in the full table