Back to Search Start Over

Decidability and Shortest Strings in Formal Languages

Authors :
Alpoge, Levent
Ang, Thomas
Schaeffer, Luke
Shallit, Jeffrey
Publication Year :
2011
Publisher :
arXiv, 2011.

Abstract

Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length of the shortest string in L.

Subjects

Subjects :
FOS: Computer and information sciences
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Formal Languages and Automata Theory (cs.FL)
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Computer Science - Formal Languages and Automata Theory
MathematicsofComputing_DISCRETEMATHEMATICS

Details

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

Tools

Authors Abstract Subjects Details