LEADER 03388nam 22005655 450 001 996466112903316 005 20200703043022.0 010 $a3-540-48669-0 024 7 $a10.1007/3-540-58355-6 035 $a(CKB)1000000000234160 035 $a(SSID)ssj0000327440 035 $a(PQKBManifestationID)11268703 035 $a(PQKBTitleCode)TC0000327440 035 $a(PQKBWorkID)10301358 035 $a(PQKB)11009333 035 $a(DE-He213)978-3-540-48669-5 035 $a(PPN)155213814 035 $a(EXLCZ)991000000000234160 100 $a20121227d1994 u| 0 101 0 $aeng 135 $aurnn|008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aTuring Machines with Sublogarithmic Space$b[electronic resource] /$fby Andrzej Szepietowski 205 $a1st ed. 1994. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d1994. 215 $a1 online resource (VIII, 114 p.) 225 1 $aLecture Notes in Computer Science,$x0302-9743 ;$v843 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-58355-6 327 $aBasic Notions -- Languages acceptable with logarithmic space -- Examples of languages acceptable with sublogarithmic space -- Lower bounds for accepting non-regular languages -- Space constructible functions -- Halting property and closure under complement -- Strong versus weak mode of space complexity -- Padding -- Deterministic versus nondeterministic Turing machines -- Space hierarchy -- Closure under concatenation -- Alternating hierarchy -- Independent complement -- Other models of Turing machines. 330 $aThis comprehensive monograph investigates the computational power of Turing machines with sublogarithmic space. The studies are devoted to the Turing machine model introduced by Stearns, Hartmanis, and Lewis (1965) with a two-way read-only input tape and a separate two-way read-write work tape. The book presents the key results on space complexity, also as regards the classes of languages acceptable, under the perspective of a sublogarithmic number of cells used during computation. It originates from courses given by the author at the Technical University of Gdansk and Gdansk University in 1991 and 1992. It was finalized in 1994 when the author visited Paderborn University and includes the most recent contributions to the field. 410 0$aLecture Notes in Computer Science,$x0302-9743 ;$v843 606 $aComputer logic 606 $aMathematical logic 606 $aLogics and Meanings of Programs$3https://scigraph.springernature.com/ontologies/product-market-codes/I1603X 606 $aMathematical Logic and Formal Languages$3https://scigraph.springernature.com/ontologies/product-market-codes/I16048 606 $aMathematical Logic and Foundations$3https://scigraph.springernature.com/ontologies/product-market-codes/M24005 615 0$aComputer logic. 615 0$aMathematical logic. 615 14$aLogics and Meanings of Programs. 615 24$aMathematical Logic and Formal Languages. 615 24$aMathematical Logic and Foundations. 676 $a511.3 700 $aSzepietowski$b Andrzej$4aut$4http://id.loc.gov/vocabulary/relators/aut$0714670 906 $aBOOK 912 $a996466112903316 996 $aTuring machines with sublogarithmic space$91382012 997 $aUNISA LEADER 01275nam 2200337Ia 450 001 996396394203316 005 20221108045153.0 035 $a(CKB)4330000000355978 035 $a(EEBO)2240866989 035 $a(OCoLC)13114988 035 $a(EXLCZ)994330000000355978 100 $a19860206d1680 uy | 101 0 $aeng 135 $aurbn||||a|bb| 200 14$aThe loving enemies$b[electronic resource] $ea comedy : as it was acted at His Highness the Duke of York's Theatre /$fwritten by L. Maidwell 210 $aLondon $cPrinted for John Guy ...$d1680 215 $a[6], 74 p 300 $aBorrows from Shadwell's The virtuoso. 300 $aWritten by Lewis Maidwell, whose name has been given variously as Lawrence and John Maidwell. Cf. Venn, J. Alum. cant.; Summers, M. Playhouse of Pepys, 1935, p. 434-436; BM; Baker, D.E. Companion to the play-house, 1764, v. 1. 300 $aReproduction of original in Cambridge University Library. 330 $aeebo-0021 700 $aMaidwell$b Lewis$f1650-1715.$01004546 701 $aShadwell$b Thomas$f1642?-1692.$0969846 801 0$bEAA 801 1$bEAA 801 2$bm/c 801 2$bWaOLN 906 $aBOOK 912 $a996396394203316 996 $aThe loving enemies$92398146 997 $aUNISA