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