Back to Search
Start Over
Decidability and Shortest Strings in Formal Languages
- 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 :
- 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
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....f0f51b334db49c7a5c3139c4f48bd008
- Full Text :
- https://doi.org/10.48550/arxiv.1103.1622