Back to Search Start Over

Length of the Shortest Word in the Intersection of Regular Languages

Authors :
Ang, Thomas
Shallit, Jeffrey
Publication Year :
2009
Publisher :
arXiv, 2009.

Abstract

In this note, we give a construction that provides a tight lower bound of mn-1 for the length of the shortest word in the intersection of two regular languages with state complexities m and n.

Subjects

Subjects :
FOS: Computer and information sciences
Formal Languages and Automata Theory (cs.FL)
Computer Science - Formal Languages and Automata Theory
Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)

Details

Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....6f743a1fdbe8195c814c9206de22ed2b
Full Text :
https://doi.org/10.48550/arxiv.0910.1528
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details