{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T20:46:45Z","timestamp":1649191605321},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,1,23]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This paper studies the complexity of languages of finite words using automata theory. To go beyond the class of regular languages, we consider infinite automata and the notion of state complexity defined by Karp. Motivated by the seminal paper of Rabin from 1963 introducing probabilistic automata, we study the (deterministic) state complexity of probabilistic languages and prove that probabilistic languages can have arbitrarily high deterministic state complexity. We then look at alternating automata as introduced by Chandra, Kozen and Stockmeyer: such machines run independent computations on the word and gather their answers through boolean combinations. We devise a lower bound technique relying on boundedly generated lattices of languages, and give two applications of this technique. The first is a hierarchy theorem, stating that there are languages of arbitrarily high polynomial alternating state complexity, and the second is a linear lower bound on the alternating state complexity of the prime numbers written in binary. This second result strengthens a result of Hartmanis and Shank from 1968, which implies an exponentially worse lower bound for the same model.<\/jats:p>","DOI":"10.1093\/logcom\/exaa007","type":"journal-article","created":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T12:08:28Z","timestamp":1578312508000},"page":"175-192","source":"Crossref","is-referenced-by-count":0,"title":["Lower bounds for the state complexity of probabilistic languages and the language of prime numbers"],"prefix":"10.1093","volume":"30","author":[{"given":"Nathana\u00cbl","family":"Fijalkow","sequence":"first","affiliation":[{"name":"CNRS, LaBRI, Talence, 33405 Bordeaux, France and The Alan Turing Institute of Data Science and Artificial Intelligence, London"}]}],"member":"286","published-online":{"date-parts":[[2020,2,17]]},"reference":[{"key":"2020040702352395000_ref1","first-page":"1","article-title":"The online space complexity of probabilistic languages","volume-title":"LFCS\u20192016","author":"Fijalkow","year":"2016"},{"key":"2020040702352395000_ref2","first-page":"414","article-title":"The state complexity of alternating automata","volume-title":"LICS\u201918","author":"Fijalkow","year":"2018"},{"key":"2020040702352395000_ref3","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1145\/321406.321410","article-title":"Some bounds on the storage requirements of sequential machines and Turing machines","volume":"14","author":"Karp","year":"1967","journal-title":"Journal of the ACM"},{"key":"2020040702352395000_ref4","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1090\/S0002-9939-1958-0135681-9","article-title":"Linear automaton transformations","volume":"9","author":"Nerode","year":"1958","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2020040702352395000_ref5","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01746518","article-title":"Two memory bounds for the recognition of primes by automata","volume":"3","author":"Hartmanis","year":"1969","journal-title":"Mathematical Systems Theory"},{"key":"2020040702352395000_ref6","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","article-title":"Probabilistic automata","volume":"6","author":"Rabin","year":"1963","journal-title":"Information and Control"},{"key":"2020040702352395000_ref7","first-page":"1","article-title":"Alternation","volume-title":"FOCS\u201976","author":"Chandra","year":"1976"},{"key":"2020040702352395000_ref8","first-page":"89","article-title":"On parallelism in Turing machines","volume-title":"FOCS\u201976","author":"Kozen","year":"1976"},{"key":"2020040702352395000_ref9","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"Journal of the ACM"},{"key":"2020040702352395000_ref10","first-page":"1","article-title":"Distributed graph automata","volume-title":"LICS","author":"Reiter","year":"2015"},{"key":"2020040702352395000_ref11","first-page":"221","article-title":"State complexity of regular languages","volume":"6","author":"Yu","year":"2001","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"2020040702352395000_ref12","first-page":"142","article-title":"State complexity of finite and infinite regular languages","volume":"76","author":"Yu","year":"2002","journal-title":"Bulletin of the EATCS"},{"key":"2020040702352395000_ref13","first-page":"251","article-title":"A survey on operational state complexity","volume":"21","author":"Gao","year":"2017","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"2020040702352395000_ref14","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.tcs.2007.03.048","article-title":"Generalising automaticity to modal properties of finite structures","volume":"379","author":"Dawar","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"2020040702352395000_ref15","first-page":"33","article-title":"Irregular behaviours for probabilistic automata","volume-title":"RP\u20192015","author":"Fijalkow","year":"2015"},{"key":"2020040702352395000_ref16","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1006\/jcss.1996.0046","article-title":"Automaticity I: Properties of a measure of descriptional complexity","volume":"53","author":"Shallit","year":"1996","journal-title":"Journal of Computer and System Sciences"},{"key":"2020040702352395000_ref17","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0304-3975(96)00189-2","article-title":"Automaticity II: Descriptional complexity in the unary case","volume":"180","author":"Pomerance","year":"1997","journal-title":"Theoretical Computer Science"},{"key":"2020040702352395000_ref18","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1007\/s000370050016","article-title":"Automaticity III: Polynomial automaticity and context-free languages","volume":"7","author":"Glaister","year":"1998","journal-title":"Computational Complexity"},{"key":"2020040702352395000_ref19","doi-asserted-by":"crossref","first-page":"347","DOI":"10.5802\/jtnb.173","article-title":"Automaticity IV: Sequences, sets, and diversity","volume":"8","author":"Shallit","year":"1996","journal-title":"Journal de Th\u00e9orie des Nombres de Bordeaux"},{"key":"2020040702352395000_ref20","first-page":"529","article-title":"Canonical regular expressions and minimal state graphs for definite events","volume":"12","author":"Brzozowski","year":"1963","journal-title":"Symposium on Mathematical Theory of Automata"},{"key":"2020040702352395000_ref21","volume-title":"Handbook of Formal Languages","author":"Rozenberg","year":"1997"},{"key":"2020040702352395000_ref22","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1080\/00207169008803893","article-title":"Constructions for alternating finite automata","volume":"35","author":"Fellah","year":"1990","journal-title":"International Journal of Computer Mathematics"},{"key":"2020040702352395000_ref23","first-page":"1","article-title":"Complexity classes in communication complexity theory (preliminary version)","volume-title":"FOCS\u201986","author":"Babai","year":"1986"},{"key":"2020040702352395000_ref24","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","article-title":"Riemann\u2019s hypothesis and tests for primality","volume":"13","author":"Miller","year":"1976","journal-title":"Journal of Computer and System Sciences"},{"key":"2020040702352395000_ref25","first-page":"781","article-title":"Primes is in P","volume":"2","author":"Agrawal","year":"2002","journal-title":"Annals of Mathematics"},{"key":"2020040702352395000_ref26","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/321466.321470","article-title":"On the recognition of primes by automata","volume":"15","author":"Hartmanis","year":"1968","journal-title":"Journal of the ACM"},{"key":"2020040702352395000_ref27","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0304-3975(76)90024-4","article-title":"On tape bounds for single letter alphabet language processing","volume":"3","author":"Hartmanis","year":"1976","journal-title":"Theoretical Computer Science"},{"key":"2020040702352395000_ref28","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1006\/jcss.2000.1725","article-title":"A lower bound for primality","volume":"62","author":"Allender","year":"2001","journal-title":"Journal of Computer and System Sciences"},{"key":"2020040702352395000_ref29","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1090\/S0002-9947-1990-0972703-X","article-title":"Unusually large gaps between consecutive primes","volume":"322","author":"Maier","year":"1990","journal-title":"Transactions of the American Mathematical Society"},{"key":"2020040702352395000_ref30","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0759-7","volume-title":"The Book of Prime Number Records","author":"Ribenboim","year":"1996"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/1\/175\/33016460\/exaa007.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/1\/175\/33016460\/exaa007.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T06:35:50Z","timestamp":1586241350000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/30\/1\/175\/5739323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":30,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,2,17]]},"published-print":{"date-parts":[[2020,1,23]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaa007","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,1]]},"published":{"date-parts":[[2020,1]]}}}