Separating words by occurrences of subwords

We obtain some lower bounds for the complexity of word separation by occurrences of subwords. In the case of length 1 subwords, we show that the bound is exact up to a constant factor. Connection with the problem of separating words by automata is considered.

Saved in:
Bibliographic Details
Published in:Journal of applied and industrial mathematics 2014-04, Vol.8 (2), p.293-299
Main Authors: Vyalyi, M. N., Gimadeev, R. A.
Format: Article
Language:English
Subjects:
Automata theory
Codes
Combinatorics
Complexity
Joints
Lower bounds
Mathematical analysis
Mathematics
Mathematics and Statistics
Polynomials
Separation
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We obtain some lower bounds for the complexity of word separation by occurrences of subwords. In the case of length 1 subwords, we show that the bound is exact up to a constant factor. Connection with the problem of separating words by automata is considered.
ISSN:1990-4789
1990-4797
DOI:10.1134/S1990478914020161