On the membership problem for pattern languages and related topics

In this thesis, we investigate the complexity of the membership problem for pattern languages. A pattern is a string over the union of the alphabets A and X, where X := {x_1, x_2, x_3, ...} is a countable set of variables and A is a finite alphabet containing terminals (e.g., A := {a, b, c, d}). Eve...

Full description

Saved in:
Bibliographic Details
Main Author: Markus L. Schmid
Format: Default Thesis
Published: 2012
Subjects:
Other information and computing sciences not elsewhere classified
Formal language theory
Automata theory
Pattern Languages
Membership problem
NP-complete problems
Information and Computing Sciences not elsewhere classified
Online Access:https://hdl.handle.net/2134/10304
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items