A Bibliography of Publications in Theoretical Computer Science: 1980–1984

Nelson H. F. Beebe University of Utah

Department of Mathematics, 110 LCB

155 S 1400 E RM 233 Salt Lake City, UT 84112-0090

USA

Tel: +1 801 581 5254 FAX: +1 801 581 4148

E-mail: beebe@math.utah.edu (Internet)
WWW URL: http://www.math.utah.edu/~beebe/

06 March 2016 Version 1.11

Title word cross-reference

(α, k) [94]. 1 [436]. 2 [126]. 3n [353, 7]. cβ [389]. ℓ(ℓ ≥ 3) [38]. F [231]. g_{0}, g_{1}, , g_{k} [235]. γ [84]. h(w) = w^{n} [437]. k [248]. λ [32, 226]. n [80, 194]. n^{2} log n [215]. Σ_{2}^{p} [436].

-calculus [32]. -complete [436]. -dimensional [194]. -lower [7]. -machines [94]. -output [126]. -reducibility [84]. -reduction [389]. -semantics [231]. -terms [226]. -th [248]. -trees [235].

0L [235, 422].

2DST [189].

Abstract [161, 430, 200, 394, 374, 271, 281]. abstractions [97, 198]. acceleration [429]. acceptability [246]. acceptors [17, 121, 278]. access [347]. Ackermann [124]. acyclic [408]. adaptation [289]. Additive [182, 1]. Adequacy [169]. Adherences [388, 223]. Admissible [280, 304]. admit [382]. advice [110]. AFLs [90]. aggregating [429]. Algebra [372, 160]. Algebraic [446, 323, 200, 453, 317, 50, 336, 391, 394, 36, 374, 104, 161, 393, 222]. algebraically [282]. algebras [327, 108, 380, 221, 16, 291, 160, 349]. algorithm [31, 346, 254, 404]. algorithmic [108, 220, 229]. algorithms [201, 85, 45, 96, 83]. allocation [136]. allowing [453]. alphabet [436, 127]. alphabets [437]. Alternating [418, 318]. alternation [167, 265]. Alternative [303]. ambiguity [47, 383]. ambiguous [307, 342]. among [212]. analysis [83]. AND/OR [280]. Any [234]. Applicability [3]. application [74, 247]. applications [163, 89, 316, 440, 171]. approach [44, 105, 245, 166, 173, 91]. appropriate [197]. Approximation [271, 339, 96]. approximations [111]. arbitrary [194]. arithmetic [239, 27, 167, 180]. arithmetical [219, 96]. array [422]. arrays [279, 422]. assignment [368, 151]. associated [393]. associative [108, 83]. asymptotic [256, 429]. asynchronous [315]. asynchrony [296]. ’atomic [89]. Attribute [149, 154, 428]. augmentation [187]. Automata [295, 395, 2, 260, 412, 321, 409, 105, 360, 288, 298, 77, 92, 326, 418, 246, 236, 124, 404, 171]. automaton [205, 162, 196, 228]. automorphism [208, 79]. Average [354, 35]. axiomatization [456]. axioms [217].

balanced [35]. bands [122]. Bandwidth [299]. based [335, 267]. Bases [383, 245]. basis [119]. BC [272]. BC-type [272]. be [148, 56]. behavior [395]. behaviour [62, 315, 297]. Behaviours [42, 222]. better [205]. between [192, 31, 187, 229, 288, 277, 195]. biconnectivity [187]. Bilimits [439]. binary [437, 197, 127]. bipolar [376]. Biprefix [409, 216, 352]. Boolean [353, 126, 16, 77, 7, 215]. bound [60, 358, 114, 7]. Bounded [101, 102, 167, 59, 288, 186, 121, 124, 265]. bounds [36, 347, 237]. Boyce [310]. Boyce-Codd [310]. branching [15, 18, 254, 404, 444].

Calculi [296, 405]. calculus [32, 416, 333, 116, 365]. can [195, 56]. Cartesian [320]. case [177, 354]. categorical [3]. categories [391]. category [320]. causal [341]. CCS [424]. cedar [357]. centers [268]. certain [31, 153]. CF [393]. chain [330]. channels [424]. characteristics [24]. Characterization [351, 384, 219, 252, 152, 159]. Characterizations [310, 360, 172, 75]. Characterizing [382]. checking [433, 254, 404]. Church [130, 177, 285, 266, 434]. claim [367]. class [267]. classes [306, 298, 34, 107, 397, 166, 311]. Classification [91, 44]. closed [321, 282, 320, 116]. Closure [319, 238]. Closures [362]. Codd [310]. code [216]. codes [409, 225, 243, 38, 352, 13]. coefficients [36]. colimits [391]. Color [140]. Color-families [140]. Coloured [98]. combinations [55]. combinatorial [96]. combinatory [380, 389]. Comma [391]. Comments [39]. common [127]. communicating [364, 302]. commutations [450]. commutativity [339]. compactness [367]. Comparison [294, 76, 45, 324]. Comparisons [195, 363]. Compatibility [329]. compilers [110]. complete [150, 155, 44, 402, 456, 58, 346, 210, 143, 302, 231, 436, 221, 38, 413, 299, 284, 387, 127]. Completeness [368, 226, 86]. Completing [352]. Complexity [115, 350, 16, 24, 55, 108, 415, 242, 23, 99, 348, 134, 214, 17, 377, 21, 151, 118, 74, 167, 229, 126, 79, 46, 182, 75, 5, 316, 180, 360, 113, 202, 107, 174, 240, 123, 256, 179, 1, 7, 166, 234, 215]. components [359]. compression [281]. Computation [264, 441, 14, 163, 391, 394, 186]. Computational [202, 214, 360, 124]. Computations [94, 182, 279, 300]. compute [37]. Computer [421, 253, 406]. Computing [315, 12]. concatenation [321, 265]. Concerning [87, 286]. Concise [93]. concrete [201]. concurrency [33, 359, 295]. concurrent [63, 42, 443]. Conditional [431]. conditions [233, 311]. Conference [421]. congruence [68]. congruences [285]. conjecture [367]. conjugacy [415]. Connections [408]. consequences [311]. consisting [211]. constant [38]. constraints [54, 185, 299]. constructability [145]. Constructing [228]. Construction [208, 410]. constructive [374]. containment [397]. Context [348, 132, 330, 309, 332, 141, 162, 25, 436, 178, 414]. Context-free [348, 132, 330, 309, 332, 141, 162, 436, 414]. context-sensitive [178]. continued [357]. continuous [327, 257, 131, 368, 341]. control [403, 50, 269, 64, 331, 267]. controlled [206, 422]. convexity [55]. Coping [426]. Coppo [345]. Coppo-Dezani [345]. correct [110]. correcting [272]. Correctness [371, 275, 147, 70, 73, 43, 69, 100]. correspond [345]. Correspondence [211]. counter [205, 230, 133, 204]. counterexample [252]. counting [49]. covering [24]. cpos [117, 304, 41]. criteria [294]. cross [456]. CSP [275, 435]. Curry [231]. cylindrification [109].

D [341]. D-continuous [341]. D0L [60, 4, 118, 388, 9]. D0L-sequences [9]. D0S [207]. data [343, 201, 430, 97, 200, 329, 358, 454, 245, 428, 161, 28, 271, 281, 198]. database [192, 185]. databases [276]. dataflow [61]. deadlines [151]. deadlock [61]. Decidability [145, 451]. Decidable [285, 157, 309, 211, 196, 416]. Deciding [436]. decision [27, 363, 286, 301, 265]. decisively [213]. decomposition [344, 92]. decompositions [185]. deductive [427]. Definability [282, 290]. defined [97, 263, 420, 423, 417]. defining [120]. definition [50]. definitions [221, 68, 373]. delay [425, 136]. Denotational [435, 170, 300]. dense [148, 140]. densities [441]. dependencies [456, 8, 427, 233, 454, 276, 185, 158]. dependency [287, 310, 305]. dependent [283]. depth [255, 167, 316, 410, 165]. depth-reduction [165]. derivatives [242]. describing [62]. description [93, 222]. descriptional [229]. design [406]. detection [241, 328]. Determinateness [217]. Determining [53]. Determinism [308]. Deterministic [59, 274, 253, 164, 322, 43, 298, 20, 204, 111, 228, 422, 254, 404]. Dezani [345]. diagonal [166]. differ [213]. different [441]. digital [123]. dimension [24]. dimensional [288, 318, 194, 278]. direct [196, 254, 404]. directed [10, 182, 417]. discrete [253]. distributed [448, 400, 62, 64, 406, 267]. distributed-implementation [406]. distribution [433]. Distributive [405]. divisibility [387]. division [269]. do [345]. DOL [225, 249]. domain [323, 245]. domains [452, 65, 320]. Dominoes [175]. DPDA’s [89, 451, 397]. dual [129]. Dynamic [137, 322, 43, 176, 160, 324].

E0L [47, 342, 48, 414, 95, 356]. economical [448, 162]. edge [24, 179]. edge-covering [24]. EDT0L [369]. EDTOL [255]. effective [304]. Effectively [361]. efficiency [85]. Efficient [403, 40, 45]. Ehrenfeucht [367]. elementary [86]. elements [79, 80]. eliminating [218]. elimination [220, 141, 282]. embeddability [115]. embedded [456, 233]. Embedding [117, 206]. embeddings [249]. emptiness [145]. encoding [197, 284]. encodings [28]. entails [145]. enumerable [178]. Enumeration [449, 446]. envelope [4]. EOL [213]. Epis [148]. equationally [97]. equations [2, 323, 437, 104, 82, 234]. Equivalance [395]. equivalence [192, 147, 217, 60, 89, 75, 164, 433, 414, 100, 254, 404]. equivalences [443]. equivalent [274, 4]. Erdos [209]. Ergodic [224]. error [272]. errors [453]. Evaluation [45, 19]. event [65]. Every [4, 160]. exact [145]. example [366]. exceptions [453]. exclusion [448]. executability [316]. existence [131, 116]. expansions [380]. expensive [165]. explicit [31]. exponentially [56]. express [185]. Expressing [176]. expression [145]. expressions [424, 180, 454, 227, 14, 19]. Expressive [432, 324]. expressiveness [289]. extended [340, 404]. extensional [61].

factor [349]. Factoring [447, 258]. fail [157]. ’fair [170, 425, 433]. fairness [362]. faithful [450]. families [310, 451, 20, 140]. family [260, 165]. Fast [328, 282, 191]. Fibonacci [357]. fields [282, 240]. Finite [225, 413, 395, 29, 2, 93, 348, 251, 321, 288, 240, 216, 407, 418, 67, 91]. finite-valuedness [251]. finitely [367]. Firing [81, 194]. firing-squad-synchronization-problem [194]. first [290, 351, 324, 265]. first-order [290, 351, 324]. fixed [8, 78, 178, 129, 52]. fixed-point [178]. Flow [100, 103, 85, 210]. flowchart [70, 73]. flows [253]. Floyd [147]. Fooling [205]. form [89, 310, 164, 423, 350, 414]. form-equivalence [164]. formal [168, 325, 247, 420]. formalism [185]. forms [213, 139, 164, 48, 414, 95, 312, 356]. formulas [377, 351]. foundation [245]. Foundations [421]. fractions [357]. fragment [220, 416]. Free [122, 415, 402, 29, 330, 248, 309, 348, 175, 118, 332, 141, 432, 162, 25, 436, 367, 132, 160, 414, 267]. full [40]. function [353]. functional [310, 276, 185, 158]. functionals [131, 264]. functions [369, 363, 263, 5, 202, 246, 7, 195, 124, 171, 215]. Fundamental [292, 391, 394].

G [152]. G-schemes [152]. Galois [74, 79]. game [76, 426]. games [357, 183]. General [96, 128, 138, 194, 406, 267]. general-purpose [406]. Generalization [178, 67]. Generalized [74, 378, 39, 211, 133, 82]. generated [367, 216, 160]. generating [171]. generation [6]. generators [455]. geometric [410]. Ginsburg [178]. Ginsburg-Rice [178]. given [361]. global [371]. Godel [143, 314]. grammar [139, 162, 164, 3, 335, 228]. grammar-which [162]. grammars [139, 330, 149, 154, 392, 141, 247, 436, 206, 350, 184, 125, 254, 393]. grammatical [99]. Graph [26, 206, 184, 152, 115, 392, 33, 262, 277, 399, 14, 19]. graph-like [14, 19]. graphs [280, 146, 24, 76, 276, 81, 100, 106, 165, 144, 365, 417]. Greendlinger [413]. group [177, 208, 413]. groups [415, 402, 31, 438]. growing [248]. growth [369]. guarded [373].

hard [37, 142, 387]. hardware [274]. heads [334, 445]. height [375, 72]. help [195]. heuristic [280]. heuristics [11]. Hierarchies [363, 199]. hierarchy [49, 261, 112, 313]. high [66]. high-level [66]. history [400]. Hoare [157, 239, 343, 370]. Hoare-like [157]. Hoares [337]. homeomorphism [10]. Homomorphic [423, 135]. homorphisms [248]. hypergraphs [408].

identification [294]. II

[155, 337, 154, 73, 394, 18, 319, 106, 116]. images [423]. implementability [97]. implementation [200, 329, 62, 191, 406]. implementations [198]. implicit [358]. Inclusion [192, 370, 298]. independence [46]. indexed [401]. Indexings [34]. induced [349]. induction [232]. inductive [294, 272, 338]. inequivalence [436]. inference [294, 403, 272, 338]. Inferences [8]. Infinitary [385]. Infinite [230, 293, 279, 422, 297, 395, 30, 292, 181, 420, 393, 234, 12, 300, 373]. infinitely [38]. information [355, 234]. Inherent [134]. inherently [342]. initial [264, 382]. injective [409]. integer [269, 387]. integers [347]. integral [447]. interaction [267]. interference [331]. interpolation [9]. interpretations [213, 30, 95]. intersection [415, 328]. invariant [25, 98, 95]. invariant-method [98]. inverse [409]. IO [199]. IO- [199]. isomorphism [144]. iterating [181]. Iteration [20, 51, 220, 234, 250]. Iterative [412, 291, 349, 267].

Jantzen [366, 413]. join [427].

known [426]. Krom [377].

L [260, 270, 243, 277]. L-systems [277]. label [424]. labelings [179]. lambda [405, 368, 116, 365]. language [309, 199, 207, 314, 82, 335, 216, 197, 236, 68, 91, 268]. Languages [135, 103, 307, 398, 51, 343, 2, 93, 348, 260, 385, 446, 401, 118, 332, 342, 336, 255, 369, 432, 400, 439, 225, 388, 247, 25, 189, 306, 178, 423, 54, 20, 351, 230, 224, 77, 382, 433, 277, 161, 125, 312, 319, 419, 259, 244, 378, 444]. large [407]. largest [262, 320]. lattice [283]. least [129, 52]. lemma [87]. lemmas [419]. length [38]. less [218]. letter [436]. letters [433]. level [66, 335]. Lexicographic [6]. lies [426]. like [157, 440, 14, 19, 371]. limited [109, 57, 244]. line [241, 278, 273]. Linear [401, 78, 444, 21, 400, 420, 230, 276, 195, 354, 171, 265, 234, 188]. linear-history [400]. Linear-time [78]. lists [211]. little [213]. LL [51, 250, 254]. LL-iteration [250]. LLP [125]. LLR [247]. Local [54, 78]. location [138]. locations [78]. log [210]. logarithm [218]. Logic [137, 150, 155, 337, 220, 157, 239, 343, 370, 322, 43, 345, 362, 176, 389, 449]. Logical [245, 23, 119]. logics [214, 303, 324]. looping [15, 18, 176]. Lower [36, 358, 7]. LR [105]. LRR [247].

machine [294, 59, 121, 313]. machines [29, 101, 102, 251, 274, 205, 263, 109, 286, 306, 288, 318, 347, 114, 212, 204, 218, 397, 94, 265, 273, 417]. manipulations [33]. many [84, 38, 445]. many-one [84]. mappings [189]. maps [208, 326]. Marvellous [213]. matching [78, 278]. mathematical [32]. matrices [393]. matrix [39, 145, 256, 429]. maximum [210]. measures [41]. MEIJE [373]. Membership [233, 454]. merge [170, 444]. Merging [80]. metatheorem [247]. method [98, 374, 39]. methodology [119]. Metric [30, 117]. metrics [349]. Minimal [58, 381, 146, 264]. minimization [378]. minimizing [136]. Mixed [163, 385]. mode [53]. model [150, 155, 341, 305, 302]. Modeling [64]. modelling [253, 66]. models [430, 368, 26, 198]. Monadic [190, 316, 434]. monoid [177, 175, 120, 413, 153]. monoids [409, 367, 438, 67, 91]. monotone [215]. morphism [433]. morphisms [172, 181]. mu [333]. mu-calculus [333]. multi [204]. multi-weak-counter [204]. multidimensional [114, 212, 191]. multihead [321]. multiplication [240, 256, 83]. Multiplicative [5]. multiprocessor [151]. multitape [298]. multivalued [8, 233]. multivariate [447]. mutual [448].

natural [157, 143, 284]. need [148]. Negation [56]. neighbourhood [206]. neighbourhood-controlled [206]. Nest [238]. nesting [316]. net [103]. Nets [359, 27, 261, 341, 66, 98, 407, 65, 312, 319, 297, 396]. network [353, 85, 7]. networks [170, 2, 126]. Nielsen [402]. Nivat [301]. NLC [392]. Non [111, 307, 341, 451, 434, 311, 373]. non-ambiguous [307]. non-guarded [373]. non-monadic [434]. non-sequential [341]. non-uniform [311]. nonalgebraic [223]. Nondeterminism [337, 257, 218, 41]. Nondeterministic [70, 73, 30, 405, 69, 32, 203, 355]. nonredundant [346]. nonsingular [397]. nonstandard [150, 155, 440]. nonterminal [95]. Normal [396, 89, 310, 350, 312]. note [99, 131, 143, 153, 259]. notion [335, 289]. NP [44, 101, 102, 142, 441, 283, 219, 107, 387, 127, 193]. NP-complete [387, 127, 44]. NP-hard [142, 387]. NPQUERY [102]. null [141]. number [35, 78, 383, 174, 243]. numberings [143]. numbers [31, 263, 386].

objects [452, 12]. obtain [166]. obtained [181]. off [241]. off-line [241]. offs [134]. OI [199]. OI-hierarchies [199]. omega [307, 17, 351, 418, 419, 259]. omega-languages [307, 419]. omega-regular [351, 259]. omega-type [17]. omega-words [418]. on-line [278, 273]. One [321, 205, 230, 84, 114, 438, 445]. one-relator [438]. one-tape [114]. One-way [321]. only [78]. Open [326]. operational [453, 184]. operations [35, 88, 429]. operator [170]. operators [373]. Optimal [241, 83, 19, 138, 11, 194]. optimality [354]. Optimization [112, 44, 111]. Oracle [283]. Oracle-dependent [283]. Order [305, 384, 71, 290, 351, 324, 265]. ordered [6]. Orderings [156]. orders [358]. ordinary [213]. other [107, 185]. outerplanar [144]. output [126].

P [402, 210, 11, 381, 193]. P-complete [402]. P-optimal [11]. P-selective [193]. pairs [381]. parallel [308, 379, 406, 444]. parallel-design [406]. Parallelism [33]. Parameter [336, 329]. parameterized [329]. Parametric [424]. parenthesis [398, 378]. parsing [105]. Partial [450, 242, 100, 106]. parts [378]. PASCAL [371]. PASCAL-like [371]. passing [329, 336]. path [169]. Pattern [92, 278]. patterns [426, 449]. PDDI [406]. PDL [86]. Peano [239, 217]. Pebble [183, 76]. performance [253]. periodicity [249]. permuters [252, 159]. Petri [103, 27, 66, 98, 407, 65, 312, 319, 297, 396]. PGCD [31]. picture [277]. Pictures [246]. Plotkin [384]. pluralism [272]. point [178]. points [129, 52]. polyhedral [328]. polynomial [49, 112, 84, 203, 111, 387, 299, 284, 234]. polynomial-time [49, 203]. polynomials [36, 447, 1, 37]. polyomino [446]. Position [139, 194]. Position-restricted [139]. possess [157]. Post [211]. potential [163]. power [168, 330, 325, 248, 97, 272, 432, 269, 420, 88, 324, 124, 338]. power-free [248]. powerdomains [384]. powerful [56]. precision [273]. precondition [364]. predicate [416]. prefix [38]. preperfectness [390]. Presburger [167, 75]. prescribed [208]. presentations [317]. preserving [141]. Primality [258, 45]. primitive [363]. primitives [267]. Principal [340, 31]. principle [147, 232]. probabilistic [59, 45, 121, 284, 273, 338]. probability [229]. Problem [211, 209, 27, 99, 251, 448, 377, 151, 60, 10, 79, 71, 210, 75, 233, 145, 298, 64, 197, 129, 81, 127, 144, 194, 72, 265, 273]. problem-language [197]. problems [49, 44, 415, 402, 115, 27, 375, 134, 163, 363, 187, 89, 142, 316, 189, 301, 454, 112, 96, 397, 111, 387, 83, 116, 299, 354, 267]. procedures [70, 73, 371]. processes [372, 364, 341, 302, 315, 443]. processing [170, 301]. processor [40]. product [385, 67]. production [3]. productions [141]. products [196]. program [147, 370, 149, 154, 128, 217, 113, 176]. programming [343, 21, 432, 400, 306, 54, 362, 335, 161, 68, 119, 444, 443]. Programs [128, 100, 106, 150, 155, 30, 157, 169, 214, 70, 73, 142, 322, 43, 69, 290, 371, 63, 449, 275, 379]. progress [429]. Projection [419]. PROLOG [449]. proof [86, 379]. proofs [275]. propagating [356]. Properties [171, 169, 292, 384, 247, 283, 319, 271, 173, 238, 13]. property [130]. Proposition [170]. Propositional [137, 214, 322, 345, 333]. protection [301]. proved [284]. Proving [370, 43, 416, 110]. PSPACE [101]. pure [309, 164, 95, 13]. purpose [406]. pushdown [205, 162, 286, 228, 252, 159, 404].

quantifier [167, 282]. quantifiers [220]. queries [403, 188]. query [101, 102, 134]. questions [286, 266].

Ramsey [440]. random [347, 262]. range [134, 403]. rank [325, 221]. ratio [369]. Rational [307, 450, 5, 221]. reachability [27]. Real [263, 451, 202, 386]. realtime [228]. reasoning [150, 155]. rebalancing [35]. recognisable [439]. recognition [236]. Recognizable [168]. Record [136]. rectangles [194]. rectangular [256]. Recursion [232, 106, 316, 444]. recursive [30, 149, 154, 363, 70, 73, 264, 178]. recursive-enumerable [178]. Recursively [358]. recursiveness [109]. Reducibilities [386, 203]. reducibility [84]. Reduction [365, 402, 39, 389, 165]. Reductions [193]. region [138]. register [109]. regular [375, 2, 309, 4, 43, 145, 351, 77, 122, 176, 293, 259, 244]. regularity [332]. related [189, 301, 24, 266, 397]. relation [229, 120]. relational [192, 305, 454, 276, 185]. Relations [103, 359, 317]. relationship [187, 288, 197, 277, 312]. relativized [238]. relator [438]. Remark [72]. Remarks [398, 366, 223]. repetitions [241]. replacement [22]. replacements [135]. representable [160]. Representation [207, 276, 355, 77]. representations [314, 153, 304]. requiring [353]. research [31]. resources [40]. respect [231]. restricted [139, 306, 233]. restriction [245]. Restrictions [392, 132, 64]. resulting [260]. Results [333, 427, 46, 451, 113, 434, 397]. retrieval [428]. reversal [411]. reversed [346]. revisited [425, 232]. revisited-with [425]. rewrite [431]. rewriting [156, 132, 413]. rewritings [399]. Rice [178]. rings [31]. Rosser [266, 434, 130, 177, 285]. rotated [358]. rule [289]. rules [330, 231, 431].

salesman [187]. satisfiability [214, 377]. satisfying [250]. SCCS [373]. scheduling [40]. schemata [192]. scheme [133, 284]. schemes [149, 154, 376, 249, 316, 340, 152, 152]. Schutzenberger [67, 178]. Science [421]. search [280, 426]. searches [357]. second [71, 421]. second-order [71]. Secondary [428]. seek [136]. segments [264]. Selection [57]. selective [132, 193]. Semantics [331, 30, 405, 257, 170, 364, 303, 400, 70, 73, 453, 391, 394, 32, 231, 362, 382, 184, 161, 63, 435, 300, 444]. semi [90, 423]. semi-AFLs [90]. semi-Thue [423]. semigroup [216]. semigroups [409]. sensitive [178]. sensitivity [83]. sentences [285]. sentential [423]. separable [160]. Separately [327]. Sequence [109, 60]. sequences [9]. Sequential [201, 2, 251, 341, 359]. series [168, 325, 420, 393]. sets [58, 75, 143, 441, 283, 107, 433, 407, 166, 193, 238]. setting [128]. Several [113]. sharing [183]. Sharp [172]. shortest [127]. Shyamasundar [252]. signatures [391, 123]. Signed [394]. Simple [306, 321, 142, 180]. simplified [142]. simulation [59, 356, 445]. Simulations [212]. single [120]. Size [237, 353, 113, 215]. Skolem [27, 145]. Skolemization [346]. small [455]. Software [421, 374]. Solution [104, 209, 138, 64, 194, 267]. solutions [375, 448]. Some [157, 427, 79, 391, 394, 46, 142, 223, 440, 434, 397, 311, 417, 37, 384, 5, 286, 233, 298, 24, 96, 393, 13]. sorting [347, 57, 188]. sound [456, 157]. space [138, 210, 411, 186, 114, 218, 124, 188]. space-bounded [186]. space-optimal [138]. spaces [361, 117]. special [120, 397]. specification [336, 374, 382]. Specifications [198, 453]. speed [314]. speed-up [314]. Speeding [22]. Sperner [209]. Sperner-Erdos [209]. Squad [81, 194]. square [118]. square-free [118]. squarefree [172]. Stability [270]. star [375, 72]. star-height [375]. star-height-problem [72]. starvation [267]. starvation-free [267]. state [29]. Stationary [253]. stochastic [344]. storage [78, 57, 191, 183, 445]. store [205]. strategies [338]. strict [20, 254]. string [241, 78, 249, 312]. string-matching [78]. strings [88]. Strong [203]. Structure [141, 29, 427, 79, 107, 171]. structured [322]. structures [157, 201, 50, 358, 290, 428, 65]. structuring [110]. study [430, 163]. studying [183, 173]. subclass [397]. subgraph [10, 144]. subrecursive [34]. Subset [312, 319]. Substitution [90, 87]. subtree [22]. subword [118]. success [449]. Succinct [77]. Succinctness [287, 314]. sum [373, 403]. Super [261]. Super-nets [261]. superconcentrator [410]. superconcentrators [237]. superexponential [124]. supersequence [127]. survey [337, 43]. symbolic [227]. Symmetric [448, 186]. synchronisation [372]. Synchronization [81, 442, 376, 301, 194]. Synchronized [48]. synchronizing [88]. synchrony [296]. syntactic [409, 216]. Syntax [54]. System [66, 448, 222]. systematic [430]. systems [190, 156, 47, 4, 287, 253, 270, 383, 301, 420, 423, 344, 230, 104, 235, 62, 64, 243, 277, 390, 266, 293, 413, 434, 308, 173, 422, 22, 171, 42]. Systolic [236, 260, 360].

table [422]. tape [59, 288, 114, 121]. tape-bounded [59, 288, 121]. tapes [334]. task [151]. tasks [40]. ‘Tautology [39]. technique [379]. techniques [429]. Technology [421]. template [158]. temporal [303, 63]. Ten [337]. term [156]. term-rewriting [156]. terminal [436, 95]. termination [425]. terms [226, 116]. tessellation [92, 326, 278]. test [433]. Testing [130, 443, 39, 258, 45]. tests [137]. th [248]. their [157, 380, 261, 451, 246, 111, 171, 378]. them [110]. theorem [226, 411, 178, 416, 250]. theorems [51, 207, 20, 174]. theoretic [26, 152]. Theoretical [421, 85]. theories [147, 23, 391, 394, 196, 174, 55, 265]. Theory [227, 150, 155, 99, 199, 74, 79, 376, 46, 105, 174, 340, 158, 281]. There [38]. three [288, 24]. three-way [288]. Thue [190, 423, 390, 266, 293, 434]. Time [194, 49, 78, 451, 84, 203, 299, 124, 273, 188, 313, 444]. Time-optimal [194]. time-precision [273]. time-space [188]. times [441]. TL [152]. TL-schemes [152]. too [231]. tools [391, 394]. Total [452, 69]. tractible [177]. trade [134]. trade-offs [134]. tradeoff [411, 273, 188]. transducers [59]. transductions [450]. transformation [216]. transformations [116]. transition [173]. traveling [187]. treatment [61]. tree [325, 260, 412, 199, 79, 428, 262, 191, 236]. trees [30, 168, 35, 375, 292, 357, 235, 179, 236, 442, 6]. trellis [360]. trilinear [429]. true [4]. Truncations [393]. Turing [274, 17, 263, 59, 306, 288, 318, 114, 212, 218, 121, 265, 273, 313]. Two [51, 318, 204, 278, 343, 375, 205, 4, 211, 75, 288, 335, 76, 45, 68]. Two-dimensional [318, 278, 288]. two-level [335]. Two-way [204]. type [17, 368, 432, 231, 340, 116, 272]. type-free [432]. type-rules [231]. typed [405, 432, 32]. types [343, 430, 200, 329, 345, 161, 271]. typing [226].

unary [235]. Unbounded [274, 257]. undecidability [71, 390, 414, 434]. Undecidable [266, 142, 247]. undetermined [8]. unification [71, 116]. unified [44, 173]. Uniform [123, 28, 166, 311]. Uniformly [248]. unifying [43]. Unique [52]. universal [185]. universes [8]. Unprovability [174]. Upper [347, 122]. use [40, 218]. user [245]. using [370, 207, 78, 264, 43, 428, 276, 234].

valuedness [251]. variables [371]. variations [76]. variety [160]. various [85]. verifications [128]. versus [84, 334]. very [13]. via [150, 155, 424]. vs [52, 254, 373].

way [205, 321, 288, 204]. weak [174, 204]. weaker [137]. weakest [364]. weight [35]. weight-balanced [35]. well [322]. well-structured [322]. whether [309]. which [157, 162, 382, 218, 438]. while [157]. while-programs [157]. whose [215]. without [137, 151, 109, 221, 40, 371]. words [58, 181, 211, 418]. wordsequence [363]. worktape [218]. Wythoff [357].

years [337].

References

Schnorr:1980:ACP

[1] C. P. Schnorr and J. P. Van de Wiele. On the additive complexity of polynomials. Theoretical Computer Science, 10(1):1– 18, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Brzozowski:1980:ERL

[2] J. A. Brzozowski and E. Leiss. On equations for regular languages, finite automata, and sequential networks. Theoretical Computer Science, 10(1):19– 35, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kurka:1980:APC

[3] P. Kůrka. Applicability of a production in a categorical grammar. Theoretical Computer Science, 10(1):37–44, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1980:ETE

[4] A. Ehrenfeucht and G. Rozenberg. Every two equivalent D0L systems have a regular true envelope. Theoretical Computer Science, 10(1):45–52, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hartmann:1980:MCS

[5] W. Hartmann and P. Schuster. Multiplicative complexity of some rational functions. Theoretical Computer Science, 10(1):53–61, January 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Zaks:1980:LGO

[6] S. Zaks. Lexicographic generation of ordered trees. Theoretical Computer Science, 10(1):63–82, January 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schnorr:1980:LBN

[7] C. P. Schnorr. A 3n-lower bound on the network complexity of Boolean functions. Theoretical Computer Science, 10 (1):83–92, January 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Biskup:1980:IMD

[8] J. Biskup. Inferences of multivalued dependencies in fixed and undetermined universes. Theoretical Computer Science, 10(1):93–105, January 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Prodinger:1980:IDS

[9] H. Prodinger. On the interpolation of D0L-sequences. Theoretical Computer Science, 10(1):107–108, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fortune:1980:DSH

[10] S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111–121, February 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lieberherr:1980:POH

[11] K. Lieberherr. P-optimal heuristics. Theoretical Computer Science, 10(2): 123–131, February 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wiedmer:1980:CIO

[12] E. Wiedmer. Computing with infinite objects. Theoretical Computer Science, 10(2):133–155, February 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deLuca:1980:SPV

[13] A. de Luca and A. Restivo. On some properties of very pure codes. Theoretical Computer Science, 10(2):157– 170, February 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Staples:1980:CGL

[14] J. Staples. Computation on graphlike expressions. Theoretical Computer Science, 10(2):171–185, February 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Havel:1980:BL

[15] I. M. Havel. On branching and looping. I. Theoretical Computer Science, 10(2): 187–220, February 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kozen:1980:CBA

[16] D. Kozen. Complexity of Boolean algebras. Theoretical Computer Science, 10 (3):221–247, March 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Cohen:1980:COT

[17] R. Cohen and A. Gold. On the complexity of omega-type Turing acceptors. Theoretical Computer Science, 10(3): 249–272, March 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Havel:1980:BLI

[18] I. M. Havel. On branching and looping. II. Theoretical Computer Science, 10(3):273–295, March 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Staples:1980:OEG

[19] J. Staples. Optimal evaluation of graphlike expressions. Theoretical Computer Science, 10(3):297–316, March 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

King:1980:ITF

[20] K. N. King. Iteration theorems for families of strict deterministic languages. Theoretical Computer Science, 10(3): 317–333, March 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Dobkin:1980:CLP

[21] D. P. Dobkin and S. P. Reiss. The complexity of linear programming. Theoretical Computer Science, 11(1):1–18, May 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Staples:1980:SSR

[22] J. Staples. Speeding up subtree replacement systems. Theoretical Computer Science, 11(1):39–47, May 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Berman:1980:CLT

[23] L. Berman. The complexity of logical theories. Theoretical Computer Science, 11(1):71–77, May 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kucera:1980:CDT

[24] L. Kucera, J. Nesetril, and A. Pultr. Complexity of dimension three and some related edge-covering characteristics of graphs. Theoretical Computer Science, 11(1):93–106, May 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hotz:1980:NIC

[25] G. Hotz. A new invariant for context free languages. Theoretical Computer Science, 11(1):107–116, May 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Harary:1980:GTM

[26] F. Harary. Graph theoretic models. Theoretical Computer Science, 11(2):117– 121, June 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Borger:1980:RPP

[27] E. Borger and H. Kleine Buning. The reachability problem for Petri nets and decision problems for Skolem arithmetic. Theoretical Computer Science, 11(2): 123–143, June 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rosenberg:1980:UDE

[28] A. L. Rosenberg, L. J. Stockmeyer, and L. Snyder. Uniform data encodings. Theoretical Computer Science, 11 (2):145–165, June 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Beynon:1980:SFF

[29] W. M. Beynon. On the structure of free finite state machines. Theoretical Computer Science, 11(2):167–180, June 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Arnold:1980:MII

[30] A. Arnold and M. Nivat. Metric interpretations of infinite trees and semantics of nondeterministic recursive programs. Theoretical Computer Science, 11(2):181–205, June 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bougaut:1980:EAP

[31] B. Bougaut. An explicit algorithm for PGCD research in certain principal rings between groups of numbers. Theoretical Computer Science, 11(2):207–220, June 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hennessy:1980:MSN

[32] M. C. B. Hennessy and E. A. Ashcroft. A mathematical semantics for a nondeterministic typed λ-calculus. Theoretical Computer Science, 11(3):227–245, July 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrig:1980:PCG

[33] H. Ehrig and B. K. Rosen. Parallelism and concurrency of graph manipulations. Theoretical Computer Science, 11(3):247–275, July 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kozen:1980:ISC

[34] D. Kozen. Indexings of subrecursive classes. Theoretical Computer Science, 11(3):277–301, July 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Blum:1980:ANR

[35] N. Blum and K. Mehlhorn. On the average number of rebalancing operations in weight-balanced trees. Theoretical Computer Science, 11(3):303–320, July 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Heintz:1980:LBP

[36] J. Heintz and M. Sieveking. Lower bounds for polynomials with algebraic coefficients. Theoretical Computer Science, 11(3):321–330, July 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

vonzurGathen:1980:SPH

[37] J. von zur Gathen and V. Strassen. Some polynomials that are hard to compute. Theoretical Computer Science, 11 (3):331–335, July 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Netto:1980:TIM

[38] A. B. Netto. There are infinitely many complete prefix codes of constant length ℓ(ℓ ≥ 3). Theoretical Computer Science, 11(3):337–339, July 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ben-Ari:1980:CTT

[39] M. Ben-Ari. Comments on ‘Tautology testing with a generalized matrix reduction method’. Theoretical Computer Science, 11(3):341–??, July 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jaffe:1980:EST

[40] J. M. Jaffe. Efficient scheduling of tasks without full use of processor resources. Theoretical Computer Science, 12(1):1– 17, September 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Saheb-Djahromi:1980:CMN

[41] N. Saheb-Djahromi. CPOs of measures for nondeterminism. Theoretical Computer Science, 12(1):19–37, September 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Winkowski:1980:BCS

[42] J. Winkowski. Behaviours of concurrent systems. Theoretical Computer Science, 12(1):39–60, September 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Harel:1980:PCR

[43] D. Harel. Proving the correctness of regular deterministic programs: a unifying survey using dynamic logic. Theoretical Computer Science, 12(1):61–81, September 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ausiello:1980:TUA

[44] G. Ausiello and A. Marchetti-Spaccamela. Toward a unified approach for the classification of NP-complete optimization problems. Theoretical Computer Science, 12(1):83–96, September 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Monier:1980:ECT

[45] L. Monier. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoretical Computer Science, 12(1):97–108, September 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Grant:1980:SMI

[46] P. W. Grant. Some more independence results in complexity theory. Theoretical Computer Science, 12(2):119–126, October 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1980:AES

[47] A. Ehrenfeucht and G. Rozenberg. On ambiguity in E0L systems. Theoretical Computer Science, 12(2):127–134, October 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maurer:1980:SEF

[48] H. A. Maurer, A. Salomaa, and D. Wood. Synchronized E0L forms. Theoretical Computer Science, 12(2):135– 159, October 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Angluin:1980:CPP

[49] D. Angluin. On counting problems and the polynomial-time hierarchy. Theoretical Computer Science, 12(2):161– 173, October 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Cousineau:1980:ADC

[50] G. Cousineau. An algebraic definition for control structures. Theoretical Computer Science, 12(2):175–192, October 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Beatty:1980:TIT

[51] J. C. Beatty. Two iteration theorems for the LL(k) languages. Theoretical Computer Science, 12(2):193–228, October 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Tiuryn:1980:UFP

[52] J. Tiuryn. Unique fixed points vs. least fixed points. Theoretical Computer Science, 12(3):229–254, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Dobkin:1980:DM

[53] D. Dobkin and J. I. Munro. Determining the mode. Theoretical Computer Science, 12(3):255–263, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Joshi:1980:LCP

[54] A. K. Joshi, L. S. Levy, and K. Yueh. Local constraints in programming languages. I. syntax. Theoretical Computer Science, 12(3):265–290, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Oppen:1980:CCC

[55] D. C. Oppen. Complexity, convexity and combinations of theories. Theoretical Computer Science, 12(3):291– 302, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Valiant:1980:NCE

[56] L. G. Valiant. Negation can be exponentially powerful. Theoretical Computer Science, 12(3):303–314, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Munro:1980:SSL

[57] J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12 (3):315–323, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Boe:1980:MCS

[58] J. M. Boe, A. de Luca, and A. Restivo. Minimal complete sets of words. Theoretical Computer Science, 12(3):325– 332, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gill:1980:DST

[59] J. Gill, J. Hunt, and J. Simon. Deterministic simulation of tape-bounded probabilistic Turing machine transducers. Theoretical Computer Science, 12 (3):333–338, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1980:BDS

[60] A. Ehrenfeucht and G. Rozenberg. On a bound for the D0L sequence equivalence problem. Theoretical Computer Science, 12(3):339–342, November 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wadge:1980:ETD

[61] W. W. Wadge. An extensional treatment of dataflow deadlock. Theoretical Computer Science, 13(1):3–15, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lynch:1980:DBI

[62] N. A. Lynch and M. J. Fischer. On describing the behaviour and implementation of distributed systems. Theoretical Computer Science, 13(1):17–43, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Pnueli:1980:TSC

[63] A. Pnueli. The temporal semantics of concurrent programs. Theoretical Computer Science, 13(1):45–60, January 1980. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maggiolo-Schettini:1980:MSC

[64] A. Maggiolo-Schettini, H. Wedde, and J. Winkowski. Modeling a solution for a control problem in distributed systems by restrictions. Theoretical Computer Science, 13(1):61–83, January 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nielsen:1980:PNE

[65] M. Nielsen, G. Plotkin, and G. Winskel. Petri nets, event structures and domains. I. Theoretical Computer Science, 13(1):85–108, January 1980. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Genrich:1980:SMH

[66] H. J. Genrich and K. Lautenbach. System modelling with high-level Petri nets. Theoretical Computer Science, 13(1): 109–136, January 1980. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Straubing:1981:GSP

[67] H. Straubing. A generalization of the schutzenberger product of finite monoids. Theoretical Computer Science, 13(2):137–150, February 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Stoy:1981:CTP

[68] J. E. Stoy. The congruence of two programming language definitions. Theoretical Computer Science, 13(2):151– 174, February 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Harel:1981:TCN

[69] D. Harel. On the total correctness of nondeterministic programs. Theoretical Computer Science, 13(2):175– 192, February 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gallier:1981:NFPa

[70] J. H. Gallier. Nondeterministic flowchart programs with recursive procedures: semantics and correctness. I. Theoretical Computer Science, 13(2):193–223, February 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Goldfarb:1981:USO

[71] W. D. Goldfarb. The undecidability of the second-order unification problem. Theoretical Computer Science, 13 (2):225–230, February 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Thomas:1981:RSH

[72] W. Thomas. Remark on the star-height-problem. Theoretical Computer Science, 13(2):231–237, February 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gallier:1981:NFPb

[73] J. H. Gallier. Nondeterministic flowchart programs with recursive procedures: semantics and correctness. II. Theoretical Computer Science, 13(3):239– 270, March 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Engeler:1981:GGT

[74] E. Engeler. Generalized Galois theory and its application to complexity. Theoretical Computer Science, 13(3):271– 293, March 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gurari:1981:CEP

[75] E. M. Gurari and O. H. Ibarra. The complexity of the equivalence problem for two characterizations of Presburger sets. Theoretical Computer Science, 13 (3):295–314, March 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

MeyerAufDerHeide:1981:CTV

[76] F. Meyer Auf Der Heide. A comparison of two variations of a pebble game on graphs. Theoretical Computer Science, 13(3):315–322, March 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Leiss:1981:SRR

[77] E. Leiss. Succinct representation of regular languages by Boolean automata. Theoretical Computer Science, 13(3): 323–330, March 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Galil:1981:LTS

[78] Z. Galil and J. Seireras. Linear-time string-matching using only a fixed number of local storage locations. Theoretical Computer Science, 13(3):331– 336, March 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gati:1981:SEG

[79] G. Gati. Some elements of a Galois theory of the structure and complexity of the tree automorphism problem. Theoretical Computer Science, 14 (1):1–17, April 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

SchulteMonting:1981:MEE

[80] J. Schulte Monting. Merging of 4 or 5 elements with n elements. Theoretical Computer Science, 14(1):19–37, April 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nishitani:1981:FSS

[81] Y. Nishitani and N. Honda. The firing squad synchronization problem for graphs. Theoretical Computer Science, 14(1):39–61, April 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Leiss:1981:GLE

[82] E. Leiss. On generalized language equations. Theoretical Computer Science, 14 (1):63–77, April 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rosenthal:1981:OAS

[83] A. Rosenthal. Optimal algorithms for sensitivity analysis in associative multiplication problems. Theoretical Computer Science, 14(1):79–90, April 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Long:1981:RVP

[84] T. J. Long. On γ-reducibility versus polynomial time many-one reducibility.

Theoretical Computer Science, 14(1):91– 101, April 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Galil:1981:TEV

[85] Z. Galil. On the theoretical efficiency of various network flow algorithms. Theoretical Computer Science, 14(1):103– 111, April 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kozen:1981:EPC

[86] D. Kozen and R. Parikh. An elementary proof of the completeness of PDL. Theoretical Computer Science, 14(1):113– 118, April 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Latteux:1981:CLS

[87] M. Latteux. Concerning a lemma of substitution. Theoretical Computer Science, 14(1):119–123, April 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jantzen:1981:PSO

[88] M. Jantzen. The power of synchronizing operations on strings. Theoretical Computer Science, 14(2):127–154, May 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gallier:1981:DAN

[89] J. H. Gallier. DPDA’s in ’atomic normal form’ and applications to equivalence problems. Theoretical Computer Science, 14(2):155–186, May 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Beauquier:1981:SSA

[90] J. Beauquier. Substitution of semi-AFLs. Theoretical Computer Science, 14 (2):187–193, May 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Therien:1981:CFM

[91] D. Therien. Classification of finite monoids: The language approach. Theoretical Computer Science, 14(2):195– 208, May 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maruoka:1981:PDT

[92] A. Maruoka, M. Kimura, and N. Shoji. Pattern decomposition for tessellation automata. Theoretical Computer Science, 14(3):211–226, June 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bucher:1981:CDF

[93] W. Bucher, H. A. Maurer, K. Culik, and D. Wotschke. Concise description of finite languages. Theoretical Computer Science, 14(3):227–246, June 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Stoklosa:1981:CM

[94] J. Stoklosa and W. Zakowski. Computations of (α, k)-machines. Theoretical Computer Science, 14(3):247–265, June 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rozenberg:1981:PTI

[95] G. Rozenberg and R. Verraedt. On pure, terminal invariant and nonterminal invariant interpretations of E0L forms. Theoretical Computer Science, 14 (3):267–288, June 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Moran:1981:GAA

[96] S. Moran. General approximation algorithms for some arithmetical combinatorial problems. Theoretical Computer Science, 14(3):289–303, June 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Callegarin:1981:AIP

[97] G. Callegarin and G. Pacini. About the implementability and the power of equationally defined data abstractions. Theoretical Computer Science, 14(3):305– 315, June 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jensen:1981:CPN

[98] K. Jensen. Coloured Petri nets and the invariant-method. Theoretical Computer Science, 14(3):317–336, June 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bucher:1981:NPT

[99] W. Bucher. A note on a problem in the theory of grammatical complexity. Theoretical Computer Science, 14(3):337– 344, June 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schmidt:1981:PPGa

[100] G. Schmidt. Programs as partial graphs. I. flow equivalence and correctness. Theoretical Computer Science, 15 (1):1–25, July 1981. CODEN TCSCDI.

ISSN 0304-3975 (print), 1879-2294 (electronic).

Book:1981:BQMa

[101] R. V. Book. Bounded query machines: on NP and PSPACE. Theoretical Computer Science, 15(1):27–39, July 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Book:1981:BQMb

[102] R. V. Book and C. Wrathall. Bounded query machines: on NP() and NPQUERY(). Theoretical Computer Science, 15(1):41–50, July 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Araki:1981:RFL

[103] T. Araki, T. Kagimasa, and N. Tokura. Relations of flow languages to Petri net languages. Theoretical Computer Science, 15(1):51–75, July 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lazard:1981:SAE

[104] D. Lazard. Solution of algebraic equations systems. Theoretical Computer Science, 15(1):77–110, July 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Heilbrunner:1981:PAA

[105] S. Heilbrunner. A parsing automata approach to LR theory. Theoretical Computer Science, 15(2):117–157, August 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schmidt:1981:PPGb

[106] G. Schmidt. Programs as partial graphs. II. recursion. Theoretical Computer Science, 15(2):159–179, August 1981. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Landweber:1981:SSN

[107] L. H. Landweber, R. J. Lipton, and E. L.

Robertson. On the structure of sets in NP and other complexity classes. Theoretical Computer Science, 15(2):181– 200, August 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Alder:1981:ACA

[108] A. Alder and V. Strassen. On the algorithmic complexity of associative algebras. Theoretical Computer Science, 15(2):201–211, August 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Germano:1981:SRC

[109] G. Germano and A. Maggiolo-Schettini.

Sequence recursiveness without cylindrification and limited register machines. Theoretical Computer Science, 15(2): 213–221, August 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Thatcher:1981:MAS

[110] J. W. Thatcher, E. G. Wagner, and J. B. Wright. More on advice on structuring compilers and proving them correct. Theoretical Computer Science, 15 (3):223–249, September 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Paz:1981:NDP

[111] A. Paz and S. Moran. Non deterministic polynomial optimization problems and their approximations. Theoretical Computer Science, 15(3):251–277, September 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Leggett:1981:OPP

[112] E. W. Leggett, Jr. and D. J. Moore. Optimization problems and the polynomial hierarchy. Theoretical Computer Science, 15(3):279–289, September 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Katseff:1981:SRP

[113] H. P. Katseff and M. Sipser. Several results in program size complexity. Theoretical Computer Science, 15(3):291– 309, September 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Loui:1981:SBO

[114] M. C. Loui. A space bound for one-tape multidimensional Turing machines. Theoretical Computer Science, 15(3):311– 320, September 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Benzaken:1981:CGE

[115] C. Benzaken and S. Foldes. Complexity of graph embeddability problems. Theoretical Computer Science, 15(3):321– 328, September 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Stratman:1981:ECT

[116] R. Stratman. On the existence of closed terms in the type lambda calculus. II: transformations of unification problems. Theoretical Computer Science, 15(3):

329–338, September 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Weihrauch:1981:EMS

[117] K. Weihrauch and U. Schreiber. Embedding metric spaces into cpos. Theoretical Computer Science, 16(1):5–24, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1981:SCS

[118] A. Ehrenfeucht and G. Rozenberg. On the subword complexity of square-free D0L languages. Theoretical Computer Science, 16(1):25–32, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Takasu:1981:LBP

[119] S. Takasu and S. Kawabata. A logical basis for programming methodology. Theoretical Computer Science, 16(1):43– 60, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jantzen:1981:SMS

[120] M. Jantzen. On a special monoid with a single defining relation. Theoretical Computer Science, 16(1):61–73, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Simon:1981:TBP

[121] J. Simon. On tape-bounded probabilistic Turing machine acceptors. Theoretical Computer Science, 16(1):75– 91, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Main:1981:FUR

[122] M. G. Main and D. B. Benson. Free upper regular bands. Theoretical Computer Science, 16(1):93–98, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lieberherr:1981:UCD

[123] K. Lieberherr. Uniform complexity and digital signatures. Theoretical Computer Science, 16(1):99–110, October 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Tao:1981:CPA

[124] Ren ji Tao. On the computational power of automata with time or space bounded by Ackermann’s or superexponential functions. Theoretical Computer Science, 16(2):115–148, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Pittle:1981:LKG

[125] J. Pittle. On LLP(k) grammars and languages. Theoretical Computer Science, 16(2):149–175, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Galbiati:1981:COB

[126] G. Galbiati and M. J. Eischer. On the complexity of 2-output Boolean networks. Theoretical Computer Science, 16 (2):177–185, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Raiha:1981:SCS

[127] K.-J. Raiha and E. Ukkonen. The shortest common supersequence problem over binary alphabet is NP-complete. Theoretical Computer Science, 16(2):187– 198, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Csirmaz:1981:PPV

[128] L. Csirmaz. Programs and program verifications in a general setting. Theoretical Computer Science, 16(2):199– 210, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nguyen:1981:DPL

[129] V. L. Nguyen and J. L. Lassez. A dual problem to least fixed points. Theoretical Computer Science, 16(2):211– 221, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Book:1981:TCR

[130] R. V. Book and C. P. O’Dunlaing.

Testing for the Church–Rosser property. Theoretical Computer Science, 16 (2):223–229, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Carter:1981:NEC

[131] I. L. Carter and R. Eagin. A note on the existence of continuous functionals. Theoretical Computer Science, 16 (2):231–235, November 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kleijn:1981:CFR

[132] H. C. M. Kleijn and G. Rozenberg.

Context-free restrictions on selective rewriting. Theoretical Computer Science, 16(3):237–269, December 1981.

CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lam:1981:GCS

[133] K. Lam, M. K. Siu, and C. T. Yu. A generalized counter scheme. Theoretical Computer Science, 16(3):271– 278, December 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Burkhard:1981:ICT

[134] W. A. Burkhard, M. L. Fredman, and D. J. Kleitman. Inherent complexity trade-offs for range query problems. Theoretical Computer Science, 16(3): 279–290, December 1981. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Albert:1981:LHR

[135] J. Albert and L. Wegner. Languages with homomorphic replacements. Theoretical Computer Science, 16(3):291– 305, December 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gupta:1981:RAM

[136] U. I. Gupta, D. T. Lee, J. W. Pruitt, and C. K. Wong. Record allocation for minimizing seek delay. Theoretical Computer Science, 16(3):307–319, December 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Berman:1981:PDL

[137] F. Berman and M. Paterson. Propositional dynamic logic is weaker without tests. Theoretical Computer Science, 16 (3):321–328, December 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Edelsbrunner:1981:SOS

[138] H. Edelsbrunner and H. A. Maurer. A space-optimal solution of general region location. Theoretical Computer Science, 16(3):329–336, December 1981. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Blattner:1982:PRG

[139] M. Blattner and S. Ginsburg. Positionrestricted grammar forms and grammars. Theoretical Computer Science, 17 (1):1–27, January 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Welzl:1982:CFD

[140] E. Welzl. Color-families are dense.

Theoretical Computer Science, 17(1):29– 41, January 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ekkonen:1982:SPE

[141] E. Ekkonen. Structure preserving elimination of null productions from contextfree grammars. Theoretical Computer Science, 17(1):43–54, January 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gurari:1982:SSU

[142] E. M. Gurari and O. H. Ibarra. Some simplified undecidable and NP-hard problems for simple programs. Theoretical Computer Science, 17(1):55– 73, January 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hartmanis:1982:NNC

[143] J. Hartmanis. A note on natural complete sets and godel numberings. Theoretical Computer Science, 17(1):75– 89, January 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Syslo:1982:SIP

[144] M. M. Syslo. The subgraph isomorphism problem for outerplanar graphs. Theoretical Computer Science, 17(1):91– 97, January 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Karpinski:1982:DSM

[145] M. Karpinski. Decidability of ‘Skolem matrix emptiness problem’ entails constructability of exact regular expression. Theoretical Computer Science, 17(1):99– 102, January 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fellner:1982:MG

[146] W. D. Fellner. On minimal graphs. Theoretical Computer Science, 17(1):103– 110, January 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bergstra:1982:FPC

[147] J. A. Bergstra, J. Tiuryn, and J. V. Tucker. Floyd’s principle, correctness theories and program equivalence. Theoretical Computer Science, 17(2):113– 149, February 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lehmann:1982:END

[148] D. Lehmann and A. Pasztor. Epis need not be dense. Theoretical Computer Science, 17(2):151–161, February 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Courcelle:1982:AGRa

[149] B. Courcelle and P. Franchi-Zannettacci.

Attribute grammars and recursive program schemes. I. Theoretical Computer Science, 17(2):163–191, February 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Andreka:1982:CLRa

[150] H. Andreka, I. Nemeti, and I. Sain. A complete logic for reasoning about programs via nonstandard model theory. I. Theoretical Computer Science, 17(2): 193–212, February 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Dutton:1982:CMT

[151] R. D. Dutton and R. C. Brigham.

The complexity of a multiprocessor task assignment problem without deadlines. Theoretical Computer Science, 17(2): 213–216, February 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Shepherdson:1982:GTC

[152] J. C. Shepherdson. Graph theoretic characterization of G-schemes and TLschemes. Theoretical Computer Science, 17(2):217–228, February 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Squier:1982:NRC

[153] C. Squier and C. Wrathall. A note on representations of a certain monoid. Theoretical Computer Science, 17(2): 229–231, February 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Courcelle:1982:AGRb

[154] B. Courcelle and P. Franchi-Zannettacci. Attribute grammars and recursive program schemes. II. Theoretical Computer Science, 17(3):235–257, March 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Andreka:1982:CLRb

[155] H. Andreka, I. Nemeti, and I. Sain. A complete logic for reasoning about programs via nonstandard model theory. II. Theoretical Computer Science, 17 (3):259–278, March 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Dershowitz:1982:OTR

[156] N. Dershowitz. Orderings for termrewriting systems. Theoretical Computer Science, 17(3):279–301, March 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bergstra:1982:SNS

[157] J. A. Bergstra and J. V. Tucker. Some natural structures which fail to possess a sound and decidable Hoare-like logic for their while-programs. Theoretical Computer Science, 17(3):303– 315, March 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Sadri:1982:TFT

[158] F. Sadri and J. D. Ullman. The theory of functional and template dependencies. Theoretical Computer Science, 17(3):317–331, March 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Shyamasundar:1982:CPP

[159] R. K. Shyamasundar. On a characterization of pushdown permuters. Theoretical Computer Science, 17(3):333– 341, March 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nemeti:1982:EFA

[160] I. Nemeti. Every free algebra in the variety generated by the representable dynamic algebras is separable and representable. Theoretical Computer Science, 17(3):343–347, March 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Pair:1982:ADT

[161] C. Pair. Abstract data types and algebraic semantics of programming languages. Theoretical Computer Science, 18(1):1–31, April 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Goldstine:1982:PAC

[162] J. Goldstine, J. K. Price, and D. Wotschke. A pushdown automaton or a context-free grammar-which is more economical? Theoretical Computer Science, 18(1):33–40, April 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ershov:1982:MCP

[163] A. P. Ershov. Mixed computation: potential applications and problems for study. Theoretical Computer Science, 18(1):41–67, April 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hagauer:1982:FED

[164] J. Hagauer. On form-equivalence of deterministic pure grammar forms. Theoretical Computer Science, 18(1):69– 87, April 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schnitger:1982:FGE

[165] G. Schnitger. A family of graphs with expensive depth-reduction. Theoretical Computer Science, 18(1):89–93, April 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schoning:1982:UAO

[166] U. Schoning. A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science, 18(1):95– 103, April 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Furer:1982:CPA

[167] M. Furer. The complexity of Presburger arithmetic with bounded quantifier alternation depth. Theoretical Computer Science, 18(1):105–111, April 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Berstel:1982:RFP

[168] J. Berstel and C. Reutenauer. Recognizable formal power series on trees. Theoretical Computer Science, 18(2):115– 148, May 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Best:1982:APP

[169] E. Best. Adequacy properties of path programs. Theoretical Computer Science, 18(2):149–171, May 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Boussinot:1982:PDS

[170] F. Boussinot. Proposition of denotational semantics for processing networks with a ’fair merge’ operator. Theoretical Computer Science, 18(2):173–206, May 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Uchimura:1982:PSG

[171] K. Uchimura. Properties of structure generating functions of automata and their applications for linear systems. Theoretical Computer Science, 18(2): 207–220, May 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Crochemore:1982:SCS

[172] M. Crochemore. Sharp characterizations of squarefree morphisms. Theoretical Computer Science, 18(2):221–226, May 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Sifakis:1982:UAS

[173] J. Sifakis. A unified approach for studying the properties of transition systems. Theoretical Computer Science, 18 (3):227–258, June 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Leivant:1982:UTC

[174] D. Leivant. Unprovability of theorems of complexity theory in weak number theories. Theoretical Computer Science, 18 (3):259–268, June 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Culik:1982:DFM

[175] K. Culik, II and T. Harju. Dominoes over a free monoid. Theoretical Computer Science, 18(3):279–300, June 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Meyer:1982:EPL

[176] A. R. Meyer and K. Winklmann. Expressing program looping in regular dynamic logic. Theoretical Computer Science, 18(3):301–323, June 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Book:1982:WMG

[177] R. V. Book. When is a monoid a group? the Church–Rosser case is tractible. Theoretical Computer Science, 18(3):325–331, June 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Istrail:1982:GGR

[178] S. Istrail. Generalization of the Ginsburg-Rice Schutzenberger fixedpoint theorem for context-sensitive and recursive-enumerable languages. Theoretical Computer Science, 18(3):333– 341, June 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Perl:1982:CEL

[179] Y. Perl and S. Zaks. On the complexity of edge labelings for trees. Theoretical Computer Science, 19(1):1–16, July 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ibarra:1982:CSA

[180] O. H. Ibarra, B. S. Leininger, and S. Moran. On the complexity of simple arithmetic expressions. Theoretical Computer Science, 19(1):17–28, July 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Culik:1982:IWO

[181] K. Culik, II and A. Salomaa. On infinite words obtained by iterating morphisms. Theoretical Computer Science, 19(1):29–38, July 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Grigorev:1982:ACD

[182] D. Yu. Grigor’ev. Additive complexity in directed computations. Theoretical Computer Science, 19(1):39–67, July 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Sethi:1982:PGS

[183] R. Sethi. Pebble games for studying storage sharing. Theoretical Computer Science, 19(1):69–84, July 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Padawitz:1982:GGO

[184] P. Padawitz. Graph grammars and operational semantics. Theoretical Computer Science, 19(2):117–141, August 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Paredaens:1982:UFE

[185] J. Paredaens. A universal formalism to express decompositions, functional dependencies and other constraints in a relational database. Theoretical Computer Science, 19(2):143–160, August 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lewis:1982:SSB

[186] H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19(2): 161–187, August 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Frederickson:1982:RBB

[187] G. N. Frederickson and J. Ja’Ja. On the relationship between the biconnectivity augmentation and traveling salesman problems. Theoretical Computer Science, 19(2):189–201, August 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Yao:1982:TST

[188] A. C.-C. Yao. On the time-space tradeoff for sorting with linear queries. Theoretical Computer Science, 19(2):203– 218, August 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ibarra:1982:MLR

[189] O. H. Ibarra. 2DST mappings on languages and related problems. Theoretical Computer Science, 19(2):219– 227, August 1982. CODEN TCSCDI.

ISSN 0304-3975 (print), 1879-2294 (electronic).

Book:1982:MTS

[190] R. V. Book, M. Jantzen, and C. Wrathall. Monadic Thue systems. Theoretical Computer Science, 19(3): 231–251, September 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Reischuk:1982:FIM

[191] K. R. Reischuk. A fast implementation of a multidimensional storage into a tree storage. Theoretical Computer Science, 19(3):253–266, September 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Atzeni:1982:IEB

[192] P. Atzeni, G. Ausiello, C. Batini, and M. Moscarini. Inclusion and equivalence between relational database schemata. Theoretical Computer Science, 19(3): 267–285, September 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Selman:1982:RNP

[193] A. L. Selman. Reductions on NP and P-selective sets. Theoretical Computer Science, 19(3):287–304, September 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Szwerinski:1982:TOS

[194] H. Szwerinski. Time-optimal solution of the firing-squad-synchronization-problem for n-dimensional rectangles with the general at an arbitrary position. Theoretical Computer Science, 19 (3):305–320, September 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Snir:1982:CBL

[195] M. Snir. Comparisons between linear functions can help. Theoretical Computer Science, 19(3):321–330, September 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hodgson:1982:DPA

[196] B. R. Hodgson. On direct products of automaton decidable theories. Theoretical Computer Science, 19(3):331– 335, September 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Megiddo:1982:BEA

[197] N. Megiddo. Is binary encoding appropriate for the problem-language relationship? Theoretical Computer Science, 19 (3):337–341, September 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wand:1982:SMI

[198] M. Wand. Specifications, models, and implementations of data abstractions. Theoretical Computer Science, 20(1):3– 32, March 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Damm:1982:IOH

[199] W. Damm. The IO- and OI-hierarchies (tree language theory). Theoretical Computer Science, 20(2):95–207, May 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrig:1982:AIA

[200] H. Ehrig, H.-J. Kreowski, B. Mahr, and P. Padawitz. Algebraic implementation of abstract data types. Theoretical Computer Science, 20(3):209–263, July 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Berry:1982:SAC

[201] G. Berry and P. L. Curien. Sequential algorithms on concrete data structures. Theoretical Computer Science, 20 (3):265–321, July 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ko:1982:CCR

[202] K.-I. Ko and H. Friedman. Computational complexity of real functions. Theoretical Computer Science, 20(3):323– 352, July 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Long:1982:SNP

[203] T. J. Long. Strong nondeterministic polynomial-time reducibilities. Theoretical Computer Science, 21(1):1–25, October 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Miyano:1982:TWD

[204] S. Miyano. Two-way deterministic multi-weak-counter machines. Theoretical Computer Science, 21(1):27– 37, October 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Duris:1982:FTW

[205] P. Duris and Z. Galil. Fooling a two way automaton, or, one pushdown store is better than one counter for two way machines. Theoretical Computer Science, 21(1):39–53, October 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Janssens:1982:GGN

[206] D. Janssens and G. Rozenberg. Graph grammars with neighbourhood-controlled embedding. Theoretical Computer Science, 21(1):55–74, October 1982. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1982:RTU

[207] A. Ehrenfeucht and G. Rozenberg. Representation theorems using D0S language. Theoretical Computer Science, 21 (1):75–90, October 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Cori:1982:CMP

[208] R. Cori and A. Machi. Construction of maps with prescribed automorphism group. Theoretical Computer Science, 21 (1):91–98, October 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Berenguer:1982:SSE

[209] X. Berenguer, J. Diaz, and L. H. Harper. A solution of the Sperner-Erdős problem. Theoretical Computer Science, 21 (1):99–103, October 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Goldschlager:1982:MFP

[210] L. M. Goldschlager, R. A. Shaw, and J. Staples. The maximum flow problem is log space complete for P. Theoretical Computer Science, 21(1):105–111, October 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1982:GPC

[211] A. Ehrenfeucht, J. Karhumaki, and G. Rozenberg. The (generalized) post correspondence problem with lists consisting of two words is decidable. Theoretical Computer Science, 21(2):119– 144, November 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Loui:1982:SAM

[212] M. C. Loui. Simulations among multidimensional Turing machines. Theoretical Computer Science, 21(2):145– 161, November 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ainhirn:1982:MID

[213] W. Ainhirn. Marvellous interpretations differ little but decisively from ordinary interpretations of EOL forms. Theoretical Computer Science, 21(2):163– 178, November 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Chlebus:1982:CCS

[214] B. S. Chlebus. On the computational complexity of satisfiability in propositional logics of programs. Theoretical Computer Science, 21(2):179–212, November 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wegener:1982:BFW

[215] I. Wegener. Boolean functions whose monotone complexity is of size n^{2} log n.

Theoretical Computer Science, 21(2): 213–224, November 1982. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Margolis:1982:STS

[216] S. W. Margolis. The syntactic transformation semigroup of a language generated by a finite biprefix code. Theoretical Computer Science, 21(2):225– 230, November 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Csirmaz:1982:DPE

[217] L. Csirmaz. Determinateness of program equivalence over Peano axioms. Theoretical Computer Science, 21(2):231– 235, November 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Monien:1982:ENT

[218] B. Monien and I. H. Sudborough. On eliminating nondeterminism from Turing machines which use less than logarithm worktape space. Theoretical Computer Science, 21(3):237–253, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kent:1982:ACN

[219] C. F. Kent and B. R. Hodgson. An arithmetical characterization of NP. Theoretical Computer Science, 21(3):255– 267, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bergstra:1982:EIQ

[220] J. A. Bergstra and J.-J. C. Meyer. On the elimination of iteration quantifiers in a fragment of algorithmic logic. Theoretical Computer Science, 21(3):269– 279, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Indermark:1982:RDC

[221] K. Indermark. On rational definitions in complete algebras without rank. Theoretical Computer Science, 21(3):281– 313, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Winkowski:1982:ADS

[222] J. Winkowski. An algebraic description of system behaviours. Theoretical Computer Science, 21(3):315–340, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Istrail:1982:SRN

[223] S. Istrail. Some remarks on nonalgebraic adherences. Theoretical Computer Science, 21(3):341–349, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kurka:1982:EL

[224] P. Kůrka. Ergodic languages. Theoretical Computer Science, 21(3):351– 355, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Head:1982:FDL

[225] T. Head and J. Wilkinson. Finite DOL languages and codes. Theoretical Computer Science, 21(3):357–361, December 1982. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hindley:1983:CTT

[226] R. Hindley. The completeness theorem for typing λ-terms. Theoretical Computer Science, 22(1–2):1–17, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Sato:1983:TSE

[227] M. Sato. Theory of symbolic expressions. I. Theoretical Computer Science, 22(1–2):19–55, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Pittl:1983:CRD

[228] J. Pittl and A. Yehudai. Constructing a realtime deterministic pushdown automaton from a grammar. Theoretical Computer Science, 22(1–2):57– 69, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gacs:1983:RBD

[229] P. Gacs. On the relation between descriptional complexity and algorithmic probability. Theoretical Computer Science, 22(1–2):71–93, January 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kuich:1983:ILS

[230] W. Kuich and F. J. Urbanek. Infinite linear systems and one counter languages. Theoretical Computer Science, 22(1–2): 95–126, January 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hindley:1983:CTR

[231] R. Hindley. Curry’s type-rules are complete with respect to the F -semantics too. Theoretical Computer Science, 22 (1–2):127–133, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Boudol:1983:RIP

[232] G. Boudol and L. Kott. Recursion induction principle revisited. Theoretical Computer Science, 22(1–2):135– 173, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ito:1983:MPE

[233] M. Ito, K. Taniguchi, and T. Kasami.

Membership problem for embedded multivalued dependencies under some restricted conditions. Theoretical Computer Science, 22(1–2):175–194, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wasilkowski:1983:IPE

[234] G. W. Wasilkowski. Any iteration for polynomial equations using linear information has infinite complexity. Theoretical Computer Science, 22(1–2):195– 208, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lee:1983:TUS

[235] D. T. Lee, C. L. Liu, and C. K. Wong.

(g_{0}, g_{1}, …, g_{k})-trees and unary 0L systems. Theoretical Computer Science, 22 (1–2):209–217, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Steinby:1983:STS

[236] M. Steinby. Systolic trees and systolic language recognition by tree automata. Theoretical Computer Science, 22(1–2):

219–232, January 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lev:1983:SBS

[237] G. Lev and L. G. Valiant. Size bounds for superconcentrators. Theoretical Computer Science, 22(3):233– 251, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Takahashi:1983:NSR

[238] M. Takahashi. Nest sets and relativized closure properties. Theoretical Computer Science, 22(3):253–264, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bergstra:1983:HLP

[239] J. A. Bergstra and J. V. Tucker. Hoare’s logic and Peano’s arithmetic. Theoretical Computer Science, 22(3):265– 284, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lempel:1983:CMF

[240] A. Lempel, G. Seroussi, and S. Winograd. On the complexity of multiplication in finite fields. Theoretical Computer Science, 22(3):285–296, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Apostolico:1983:OLD

[241] A. Apostolico and F. P. Preparata. Optimal off-line detection of repetitions in a string. Theoretical Computer Science, 22(3):297–315, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bauer:1983:CPD

[242] W. Bauer and V. Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22(3):317– 330, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maurer:1983:CNS

[243] H. A. Maurer. L codes and number systems. Theoretical Computer Science, 22 (3):331–346, February 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Tang:1983:LRL

[244] Chuang jie Tang and Yi li Zhang. The limited regular languages. Theoretical Computer Science, 23(1):1–10, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jankowski:1983:LFA

[245] A. Jankowski and C. Rauszer. Logical foundation approach to users’ domain restriction in data bases. Theoretical Computer Science, 23(1):11–36, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nakamura:1983:PFT

[246] A. Nakamura and H. Ono. Pictures of functions and their acceptability by automata. Theoretical Computer Science, 23(1):37–48, March 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Heilbrunner:1983:MUP

[247] S. Heilbrunner. A metatheorem for undecidable properties of formal languages and its application to LRR and LLR grammars and languages. Theoretical Computer Science, 23(1):49–68, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Brandenburg:1983:UGP

[248] F.-J. Brandenburg. Uniformly growing k-th power-free homorphisms. Theoretical Computer Science, 23(1):69– 82, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Head:1983:DSP

[249] T. Head, G. Thierrin, and J. Wilkinson. DOL schemes and the periodicity of string embeddings. Theoretical Computer Science, 23(1):83–89, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nijholt:1983:SLI

[250] A. Nijholt. On satisfying the LLiteration theorem. Theoretical Computer Science, 23(1):91–94, March 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Chan:1983:FVP

[251] Tat hung Chan and O. H. Ibarra. On the finite-valuedness problem for sequential machines. Theoretical Computer Science, 23(1):95–101, March 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ramanan:1983:CSC

[252] P. V. Ramanan. A counterexample to Shyamasundar’s characterization of pushdown permuters. Theoretical Computer Science, 23(1):103–105, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gelenbe:1983:SDF

[253] E. Gelenbe. Stationary deterministic flows in discrete systems. I (computer performance modelling). Theoretical Computer Science, 23(2):107–127, April 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Tomita:1983:DBA

[254] E. Tomita. A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars. Theoretical Computer Science, 23(2):129– 154, April 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Eisman:1983:DEL

[255] G. S. Eisman. On depth in EDTOL languages. Theoretical Computer Science, 23(2):155–169, April 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lotti:1983:ACR

[256] G. Lotti and F. Romani. On the asymptotic complexity of rectangular matrix multiplication. Theoretical Computer Science, 23(2):171–185, April 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Back:1983:CSU

[257] R. J. R. Back. A continuous semantics for unbounded nondeterminism. Theoretical Computer Science, 23(2):187– 210, April 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Finn:1983:PTF

[258] J. Finn and K. Lieberherr. Primality testing and factoring. Theoretical Computer Science, 23(2):211–215, April 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Takahashi:1983:NOR

[259] M. Takahashi and H. Yamasaki. A note on omega-regular languages. Theoretical Computer Science, 23(2):217–225, April 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Culik:1983:FLR

[260] K. Culik, J. Gruska, and A. Salomaa. On a family of L languages resulting for systolic tree automata. Theoretical Computer Science, 23(3):231–242, May 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Etzion:1983:SNT

[261] T. Etzion and M. Yoeli. Super-nets and their hierarchy. Theoretical Computer Science, 23(3):243–272, May 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Marchetti-Spaccamela:1983:LTR

[262] A. Marchetti-Spaccamela and M. Prtasi. The largest tree in a random graph. Theoretical Computer Science, 23(3):273– 286, May 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Freund:1983:RFN

[263] R. Freund. Real functions and numbers defined by Turing machines. Theoretical Computer Science, 23(3):287–304, May 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gordon:1983:CRF

[264] D. Gordon and E. Shamir. Computation of recursive functionals using minimal initial segments. Theoretical Computer Science, 23(3):305–315, May 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Volger:1983:TML

[265] H. Volger. Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories. Theoretical Computer Science, 23(3):333–337, May 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

ODunglaing:1983:UQR

[266] C. O’Dunglaing. Undecidable questions related to Church–Rosser Thue systems. Theoretical Computer Science, 23(3): 339–345, May 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wedde:1983:ISF

[267] H. Wedde. An iterative and starvationfree solution for a general class of distributed control problems based on interaction primitives. Theoretical Computer Science, 24(1):1–20, June 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deLuca:1983:CL

[268] A. de Luca, A. Restivo, and S. Salemi.

On the centers of a language. Theoretical Computer Science, 24(1):21–34, June 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ibarra:1983:CPI

[269] O. H. Ibarra, S. Moran, and L. E. Rosier. On the control power of integer division. Theoretical Computer Science, 24 (1):35–52, June 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Grefenstette:1983:SS

[270] J. J. Grefenstette. Stability in L systems. Theoretical Computer Science, 24(1):53–71, June 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schmidt:1983:APA

[271] D. A. Schmidt. Approximation properties of abstract data types. Theoretical Computer Science, 24(1):73–94, June 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Daley:1983:ECP

[272] R. P. Daley. On the error correcting power of pluralism in BC-type inductive inference. Theoretical Computer Science, 24(1):95–104, June 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Watanabe:1983:TPT

[273] O. Watanabe. The time-precision tradeoff problem on on-line probabilistic Turing machines. Theoretical Computer Science, 24(1):105–117, June 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Chazelle:1983:UHE

[274] B. Chazelle and L. Monier. Unbounded hardware is equivalent to deterministic Turing machines. Theoretical Computer Science, 24(2):123–130, July 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Soundararajan:1983:CPC

[275] N. Soundararajan. Correctness proofs of CSP programs. Theoretical Computer Science, 24(2):131–141, July 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nambiar:1983:RFD

[276] K. K. Nambiar, T. Radhakrishnan, and V. G. Tikekar. Representation of functional dependencies in relational databases using linear graphs. Theoretical Computer Science, 24(2):143– 159, July 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nakamura:1983:RBG

[277] A. Nakamura and K. Aizawa. On a relationship between graph L-systems and picture languages. Theoretical Computer Science, 24(2):161–177, July 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Toda:1983:TDP

[278] M. Toda, K. Inoue, and I. Takanami.

Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors. Theoretical Computer Science, 24(2):179–194, July 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Siromoney:1983:IAI

[279] R. Siromoney, R. Dare, and K. G. Subramanian. Infinite arrays and infinite computations. Theoretical Computer Science, 24(2):195–205, July 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bagchi:1983:AHS

[280] A. Bagchi and A. Mahanti. Admissible heuristic search in AND/OR graphs. Theoretical Computer Science, 24(2): 207–219, July 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Storer:1983:TAT

[281] J. A. Storer. Toward an abstract theory of data compression. Theoretical Computer Science, 24(3):221–237, August 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Heintz:1983:DFQ

[282] J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science, 24 (3):239–277, August 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Homer:1983:ODP

[283] S. Homer and W. Maass. Oracledependent properties of the lattice of NP sets. Theoretical Computer Science, 24 (3):279–289, August 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Vazirani:1983:NES

[284] U. V. Vazirani and V. V. Vazirani. A natural encoding scheme proved probabilistic polynomial complete. Theoretical Computer Science, 24(3):291– 300, August 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Book:1983:DSC

[285] R. V. Book. Decidable sentences of Church–Rosser congruences. Theoretical Computer Science, 24(3):301– 312, August 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ibarra:1983:SDQ

[286] O. H. Ibarra. On some decision questions concerning pushdown machines. Theoretical Computer Science, 24(3):313– 322, August 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fischer:1983:SDS

[287] P. C. Fischer, J. H. Jou, and D.-M.

Tsou. Succinctness in dependency systems. Theoretical Computer Science, 24 (3):323–329, August 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Inoue:1983:RBT

[288] K. Inoue, I. Takanami, and H. Taniguchi.

A relationship between two-dimensional finite automata and three-way tapebounded two-dimensional Turing machines. Theoretical Computer Science, 24(3):331–336, August 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Olderog:1983:NER

[289] E.-R. Olderog. On the notion of expressiveness and the rule of adaptation. Theoretical Computer Science, 24(3):337– 347, August 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kfoury:1983:DPF

[290] A. J. Kfoury. Definability by programs in first-order structures. Theoretical Computer Science, 25(1):1–66, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nelson:1983:IA

[291] E. Nelson. Iterative algebras. Theoretical Computer Science, 25(1):67– 94, January 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Courcelle:1983:FPI

[292] B. Courcelle. Fundamental properties of infinite trees. Theoretical Computer Science, 25(2):95–169, March 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

ODunlaing:1983:IRT

[293] C. O’Dunlaing. Infinite regular Thue systems. Theoretical Computer Science, 25(2):171–192, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Case:1983:CIC

[294] J. Case and C. Smith. Comparison of identification criteria for machine inductive inference. Theoretical Computer Science, 25(2):193–120, March 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Priese:1983:AC

[295] L. Priese. Automata and concurrency. Theoretical Computer Science, 25(3): 221–265, July 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Milner:1983:CSA

[296] R. Milner. Calculi for synchrony and asynchrony. Theoretical Computer Science, 25(3):267–310, July 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Valk:1983:IBP

[297] R. Valk. Infinite behaviour of Petri nets. Theoretical Computer Science, 25 (3):311–341, July 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kinber:1983:IPS

[298] E. B. Kinber. The inclusion problem for some classes of deterministic multitape automata. Theoretical Computer Science, 26(1–2):1–24, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Sudborough:1983:BCP

[299] I. H. Sudborough. Bandwidth constraints on problems complete for polynomial time. Theoretical Computer Science, 26(1–2):25–52, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deBakker:1983:ICD

[300] J. W. de Bakker, J.-J. Ch. Meyer, and J. I. Zucker. On infinite computations in denotational semantics. Theoretical Computer Science, 26(1–2):53– 82, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Istrail:1983:NPS

[301] S. Istrail and C. Masalagiu. Nivat’s processing systems: decision problems related to protection and synchronization. Theoretical Computer Science, 26(1–2): 83–103, September 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hehner:1983:MCM

[302] E. C. R. Hehner and C. A. R. Hoare. A more complete model of communicating processes. Theoretical Computer Science, 26(1–2):105–120, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Emerson:1983:AST

[303] E. A. Emerson. Alternative semantics for temporal logics. Theoretical Computer Science, 26(1–2):121–130, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Weihrauch:1983:ARE

[304] K. Weihrauch and G. Schafer. Admissible representations of effective CPO’s. Theoretical Computer Science, 26(1–2): 131–147, September 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ginsburg:1983:ODR

[305] S. Ginsburg and R. Hull. Order dependency in the relational model. Theoretical Computer Science, 26(1–2):149– 195, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ibarra:1983:SPL

[306] O. H. Ibarra and L. E. Rosier. Simple programming languages and restricted classes of Turing machines. Theoretical Computer Science, 26(1–2):197–220, September 1983. CODEN TCSCDI.

ISSN 0304-3975 (print), 1879-2294 (electronic).

Arnold:1983:ROL

[307] A. Arnold. Rational omega-languages are non-ambiguous. Theoretical Computer Science, 26(1–2):221–223, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rajlich:1983:DPS

[308] V. Rajlich. Determinism in parallel systems. Theoretical Computer Science, 26 (1–2):225–231, September 1983. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bucher:1983:IDW

[309] W. Bucher and J. Hagauer. It is decidable whether a regular language is pure context-free. Theoretical Computer Science, 26(1–2):233–241, September 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ginsburg:1983:CFD

[310] S. Ginsburg and R. Hull. Characterizations for functional dependency and Boyce-Codd normal form families. Theoretical Computer Science, 26(3):243– 286, October 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Yap:1983:SCN

[311] C. K. Yap. Some consequences of nonuniform conditions on uniform classes. Theoretical Computer Science, 26(3): 287–300, October 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rozenberg:1983:SLPa

[312] G. Rozenberg and R. Verraedt. Subset languages of Petri nets. I. the relationship to string languages and normal forms. Theoretical Computer Science, 26(3):301–326, October 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Zak:1983:TMT

[313] S. Zak. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327–333, October 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hartmanis:1983:GSS

[314] J. Hartmanis. On godel speed-up and succinctness of language representations. Theoretical Computer Science, 26(3):335–342, October 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Staples:1983:CBA

[315] J. Staples and V. L. Nguyen. Computing the behaviour of asynchronous processes. Theoretical Computer Science, 26(3):343–353, October 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hunt:1983:CMR

[316] H. B. Hunt and D. J. Rosenkrantz. The complexity of monadic recursion schemes: executability problems, nesting depth, and applications. Theoretical Computer Science, 27(1–2):3–38, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kamimura:1983:ARP

[317] T. Kamimura and A. Tang. Algebraic relations and presentations. Theoretical Computer Science, 27(1–2):39– 60, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Inoue:1983:TDA

[318] K. Inoue, I. Takanami, and H. Taniguchi.

Two-dimensional alternating Turing machines. Theoretical Computer Science, 27(1–2):61–83, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rozenberg:1983:SLPb

[319] G. Rozenberg and R. Verraedt. Subset languages of Petri nets. II. closure properties. Theoretical Computer Science, 27 (1–2):85–108, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Smyth:1983:LCC

[320] M. B. Smyth. The largest Cartesian closed category of domains. Theoretical Computer Science, 27(1–2):109–119, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Duris:1983:OWS

[321] P. Duris and J. Hromkovic. One-way simple multihead finite automata are not closed under concatenation. Theoretical Computer Science, 27(1–2):121– 125, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Halpern:1983:PDL

[322] J. Y. Halpern and J. H. Reif. The propositional dynamic logic of deterministic, well-structured programs. Theoretical Computer Science, 27(1–2):127– 165, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrich:1983:ADE

[323] H.-D. Ehrich and U. Lipeck. Algebraic domain equations. Theoretical Computer Science, 27(1–2):167–196, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Stolboushkin:1983:CEP

[324] A. P. Stolboushkin and M. A. Taitslin. The comparison of the expressive power of first-order dynamic logics. Theoretical Computer Science, 27(1–2):197– 209, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bozapalidis:1983:RFT

[325] S. Bozapalidis and O. Louscou-Bozapalidou. The rank of a formal tree power series. Theoretical Computer Science, 27(1–2):211–215, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maruoka:1983:OMT

[326] A. Maruoka. Open maps for tessellation automata. Theoretical Computer Science, 27(1–2):217–224, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Adamek:1983:SCA

[327] J. Adamek and E. Nelson. Separately continuous algebras. Theoretical Computer Science, 27(1–2):225–231, November 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Dobkin:1983:FDP

[328] D. P. Dobkin and D. G. Kirkpatrick.

Fast detection of polyhedral intersection. Theoretical Computer Science, 27 (3):241–253, December 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrig:1983:CPP

[329] H. Ehrig and H.-J. Kreowski. Compatibility of parameter passing and implementation of parameterized data types. Theoretical Computer Science, 27(3): 255–286, December 1983. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Blum:1983:MPC

[330] N. Blum. More on the power of chain rules in context-free grammars. Theoretical Computer Science, 27(3):287– 295, December 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Tennent:1983:SIC

[331] R. D. Tennent. Semantics of interference control. Theoretical Computer Science, 27(3):297–310, December 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1983:RCF

[332] A. Ehrenfeucht, D. Haussler, and G. Rozenberg. On regularity of contextfree languages. Theoretical Computer Science, 27(3):311–332, December 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kozen:1983:RPM

[333] D. Kozen. Results on the propositional mu-calculus. Theoretical Computer Science, 27(3):333–354, December 1983. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Paul:1984:HVT

[334] W. Paul. On heads versus tapes. Theoretical Computer Science, 28(1–2):1– 12, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maluszynski:1984:TPL

[335] J. Maluszynski. Towards a programming language based on the notion of two-level grammar. Theoretical Computer Science, 28(1–2):13–43, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrig:1984:PPA

[336] H. Ehrig, H.-J. Kreowski, J. Thatcher, E. Wagner, and J. Wright. Parameter passing in algebraic specification languages. Theoretical Computer Science, 28(1–2):45–81, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Apt:1984:TYH

[337] K. R. Apt. Ten years of hoares logic: a survey. II. nondeterminism. Theoretical Computer Science, 28(1–2):83– 109, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Wiehagen:1984:PPS

[338] R. Wiehagen, R. Freivalds, and E. B.

Kinber. On the power of probabilistic strategies in inductive inference. Theoretical Computer Science, 28(1–2):111– 133, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bini:1984:CA

[339] D. Bini. On commutativity and approximation. Theoretical Computer Science, 28(1–2):135–150, January 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

RonchiDellaRocca:1984:PTS

[340] S. Ronchi Della Rocca and B. Venneri. Principal type schemes for an extended type theory. Theoretical Computer Science, 28(1–2):151–169, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fernandez:1984:DCC

[341] C. Fernandez and P. S. Thiagarajan. Dcontinuous causal nets: a model of nonsequential processes. Theoretical Computer Science, 28(1–2):171–196, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1984:IAE

[342] A. Ehrenfeucht, G. Rozenberg, and R. Verraedt. On inherently ambiguous E0L languages. Theoretical Computer Science, 28(1–2):197–214, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bergstra:1984:HLP

[343] J. A. Bergstra and J. V. Tucker. Hoare’s logic for programming languages with two data types. Theoretical Computer Science, 28(1–2):215–221, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kanaoka:1984:DSS

[344] T. Kanaoka and S. Tomita. The decomposition of stochastic systems. Theoretical Computer Science, 28(1–2):223– 233, January 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hindley:1984:CDT

[345] J. R. Hindley. Coppo-Dezani types do not correspond to propositional logic. Theoretical Computer Science, 28(1–2): 235–236, January 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Cox:1984:CNA

[346] P. T. Cox and T. Pietrzykowski. A complete, nonredundant algorithm for reversed skolemization. Theoretical Computer Science, 28(3):239–261, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kirkpatrick:1984:UBS

[347] D. Kirkpatrick and S. Reisch. Upper bounds for sorting integers on random access machines. Theoretical Computer Science, 28(3):263–276, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bucher:1984:CFC

[348] W. Bucher, H. A. Maurer, and K. Culik. Context-free complexity of finite languages. Theoretical Computer Science, 28(3):277–285, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Parisi-Presicce:1984:IFA

[349] F. Parisi-Presicce. Iterative factor algebras and induced metrics. Theoretical Computer Science, 28(3):287– 298, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kelemenova:1984:CNF

[350] A. Kelemenova. Complexity of normal form grammars. Theoretical Computer Science, 28(3):299–314, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kobayashi:1984:COR

[351] K. Kobayashi, M. Takahashi, and H. Yamasaki. Characterization of omegaregular languages by first-order formulas. Theoretical Computer Science, 28 (3):315–327, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Perrin:1984:CBC

[352] D. Perrin. Completing biprefix codes.

Theoretical Computer Science, 28(3): 329–336, February 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Blum:1984:BFR

[353] N. Blum. A Boolean function requiring 3n network size. Theoretical Computer Science, 28(3):337–345, February 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Traub:1984:ACO

[354] J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski. Average case optimality for linear problems. Theoretical Computer Science, 29(1–2):1–25, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Orlowska:1984:RNI

[355] E. Orlowska and Z. Pawlak. Representation of nondeterministic information. Theoretical Computer Science, 29(1–2): 27–39, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Rozenberg:1984:SPE

[356] G. Rozenberg and R. Verraedt. On simulation and propagating E0L forms. Theoretical Computer Science, 29(1–2): 41–48, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fraenkel:1984:WGC

[357] A. S. Fraenkel. Wythoff games, continued fractions, cedar trees and Fibonacci searches. Theoretical Computer Science, 29(1–2):49–73, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Frederickson:1984:RRO

[358] G. N. Frederickson. Recursively rotated orders and implicit data structures: a lower bound. Theoretical Computer Science, 29(1–2):75–85, March 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Janicki:1984:NSC

[359] R. Janicki. Nets, sequential components and concurrency relations. Theoretical Computer Science, 29(1–2):87– 121, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ibarra:1984:CCC

[360] O. H. Ibarra and S. M. Kim. Characterizations and computational complexity of systolic trellis automata. Theoretical Computer Science, 29(1–2):123– 153, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kamimura:1984:EGS

[361] T. Kamimura and A. Tang. Effectively given spaces. Theoretical Computer Science, 29(1–2):155–166, March 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lassez:1984:CFS

[362] J.-L. Lassez and M. J. Maher. Closures and fairness in the semantics of programming logic. Theoretical Computer Science, 29(1–2):167–184, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fachini:1984:HPR

[363] E. Fachini and M. Napoli. Hierarchies of primitive recursive wordsequence functions: comparisons and decision problems. Theoretical Computer Science, 29 (1–2):185–227, March 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Elrad:1984:WPS

[364] T. Elrad and N. Francez. A weakest precondition semantics for communicating processes. Theoretical Computer Science, 29(3):231–250, April 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

VenturiniZilli:1984:RGL

[365] M. Venturini Zilli. Reduction graphs in the lambda calculus. Theoretical Computer Science, 29(3):251–275, April 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Potts:1984:REJ

[366] D. H. Potts. Remarks on an example of jantzen. Theoretical Computer Science, 29(3):277–284, April 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Karhumaki:1984:ECC

[367] J. Karhumaki. The Ehrenfeucht conjecture: a compactness claim for finitely generated free monoids. Theoretical Computer Science, 29(3):285–308, April 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Coppo:1984:CTA

[368] M. Coppo. Completeness of type assignment in continuous lambda models. Theoretical Computer Science, 29 (3):309–324, April 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Eisman:1984:RGF

[369] G. S. Eisman. On the ratio of growth functions in EDT0L languages. Theoretical Computer Science, 29(3):325– 349, April 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bergstra:1984:PPI

[370] J. A. Bergstra and J. W. Klop. Proving program inclusion using Hoare’s logic. Theoretical Computer Science, 30(1):1– 48, April 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Olderog:1984:CPP

[371] E.-R. Olderog. Correctness of programs with PASCAL-like procedures without global variables. Theoretical Computer Science, 30(1):49–90, April 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Austry:1984:APS

[372] D. Austry and G. Boudol. Algebra of processes and synchronisation. Theoretical Computer Science, 30(1):91– 131, April 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deSimone:1984:MSI

[373] R. de Simone. On MEIJE and SCCS:

infinite sum operators vs. non-guarded definitions. Theoretical Computer Science, 30(1):133–138, April 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Klaeren:1984:CMA

[374] H. A. Klaeren. A constructive method for abstract algebraic software specification. Theoretical Computer Science, 30 (2):139–204, August 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Braquelaire:1984:STS

[375] J. P. Braquelaire and B. Courcelle. The solutions of two star-height problems for regular trees. Theoretical Computer Science, 30(2):205–239, August 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Genrich:1984:TBS

[376] H. J. Genrich and P. S. Thiagarajan. A theory of bipolar synchronization schemes. Theoretical Computer Science, 30(3):241–318, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Denenberg:1984:CSP

[377] L. Denenberg and H. R. Lewis. The complexity of the satisfiability problem for krom formulas. Theoretical Computer Science, 30(3):319–341, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Yamasaki:1984:GPL

[378] H. Yamasaki and M. Takahashi. Generalized parenthesis languages and minimization of their parenthesis parts. Theoretical Computer Science, 31(1–2):1– 11, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Soundararajan:1984:PTP

[379] N. Soundararajan. A proof technique for parallel programs. Theoretical Computer Science, 31(1–2):13–29, May 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bruce:1984:CAT

[380] K. Bruce and G. Longo. On combinatory algebras and their expansions. Theoretical Computer Science, 31(1–2): 31–40, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schoning:1984:MPP

[381] U. Schoning. Minimal pairs for P.

Theoretical Computer Science, 31(1–2): 41–48, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Mahr:1984:CSL

[382] B. Mahr and J. A. Makowsky. Characterizing specification languages which admit initial semantics. Theoretical Computer Science, 31(1–2):49–59, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Honkala:1984:BAN

[383] J. Honkala. Bases and ambiguity of number systems. Theoretical Computer Science, 31(1–2):61–71, May 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Escrig:1984:CPO

[384] D. F. Escrig. A characterization of Plotkin’s order in powerdomains, and some of its properties. Theoretical Computer Science, 31(1–2):73–82, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

DeSimone:1984:IMP

[385] R. De Simone. Infinitary and mixed product languages. Theoretical Computer Science, 31(1–2):83–100, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ko:1984:RRN

[386] Ker-I Ko. Reducibilities on real numbers. Theoretical Computer Science, 31 (1–2):101–123, May 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Plaisted:1984:NNH

[387] D. A. Plaisted. New NP-hard and NP-complete polynomial and integer divisibility problems. Theoretical Computer Science, 31(1–2):125–138, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Head:1984:ADL

[388] T. Head. Adherences of D0L languages. Theoretical Computer Science, 31(1–2): 139–149, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Mezghiche:1984:NRC

[389] M. Mezghiche. A new cβ-reduction in combinatory logic. Theoretical Computer Science, 31(1–2):151–162, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Narendran:1984:UPT

[390] P. Narendran and R. McNaughton. The undecidability of the preperfectness of Thue systems. Theoretical Computer Science, 31(1–2):165–174, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Goguen:1984:SFAa

[391] J. A. Goguen and R. M. Burstall. Some fundamental algebraic tools for the semantics of computation. I. comma categories, colimits, signatures and theories. Theoretical Computer Science, 31(1–2): 175–209, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ehrenfeucht:1984:RNG

[392] A. Ehrenfeucht, M. G. Main, and G. Rozenberg. Restrictions on NLC graph grammars. Theoretical Computer Science, 31(1–2):211–223, May 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Uchimura:1984:TIM

[393] K. Uchimura. Truncations of infinite matrices and algebraic series associated with some CF grammars. Theoretical Computer Science, 31(3):227–261, June 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Goguen:1984:SFAb

[394] J. A. Goguen and R. M. Burstall. Some fundamental algebraic tools for the semantics of computation. II. signed and abstract theories. Theoretical Computer Science, 31(3):263–295, June 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Alaiwan:1984:EIB

[395] H. Alaiwan. Equivalance of infinite behavior of finite automata. Theoretical Computer Science, 31(3):297–306, June 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Yamasaki:1984:NPN

[396] H. Yamasaki. Normal Petri nets. Theoretical Computer Science, 31(3):307– 315, June 1984. CODEN TCSCDI.

ISSN 0304-3975 (print), 1879-2294 (electronic).

Oyamaguchi:1984:SRS

[397] M. Oyamaguchi. Some results on subclass containment problems for special classes of DPDAs related to nonsingular machines. Theoretical Computer Science, 31(3):317–335, June 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Autebert:1984:RPL

[398] J. M. Autebert, J. Beauquier, L. Boasson, and G. Senizergues. Remarks on parenthesis languages. Theoretical Computer Science, 31(3):337–349, June 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Raoult:1984:GR

[399] J. C. Raoult. On graph rewritings. Theoretical Computer Science, 32(1–2): 1–24, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Francez:1984:LHS

[400] N. Francez, D. Lehmann, and A. Pnueli. A linear-history semantics for languages for distributed programming. Theoretical Computer Science, 32(1–2):25– 46, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Duske:1984:LIL

[401] J. Duske and R. Parchmann. Linear indexed languages. Theoretical Computer Science, 32(1–2):47–60, July 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Avenhaus:1984:NRP

[402] J. Avenhaus and K. Madlener. The Nielsen reduction and P-complete problems in free groups. Theoretical Computer Science, 32(1–2):61–76, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Chin:1984:EIC

[403] F. Y. Chin, P. Kossowski, and S. C. Loh.

Efficient inference control for range SUM queries. Theoretical Computer Science, 32(1–2):77–86, July 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Tomita:1984:EDB

[404] E. Tomita. An extended direct branching algorithm for checking equivalence of deterministic pushdown automata. Theoretical Computer Science, 32(1–2):87– 120, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Astesiano:1984:DSN

[405] E. Astesiano and G. Costa. Distributive semantics for nondeterministic typed lambda — calculi. Theoretical Computer Science, 32(1–2):121–156, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Vishkin:1984:PDD

[406] U. Vishkin. A parallel-design distributedimplementation (PDDI) general-purpose computer. Theoretical Computer Science, 32(1–2):157–172, July 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

McAloon:1984:PNL

[407] D. McAloon. Petri nets and large finite sets. Theoretical Computer Science, 32 (1–2):173–183, July 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maier:1984:CAH

[408] D. Maier. Connections in acyclic hypergraphs. Theoretical Computer Science, 32(1–2):185–199, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hall:1984:BCI

[409] T. E. Hall. Biprefix codes, inverse semigroups and syntactic monoids of injective automata. Theoretical Computer Science, 32(1–2):201–213, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Meshulam:1984:GCS

[410] R. Meshulam. A geometric construction of a superconcentrator of depth 2. Theoretical Computer Science, 32(1–2): 215–219, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hong:1984:TTS

[411] J. W. Hong. A tradeoff theorem for space and reversal. Theoretical Computer Science, 32(1–2):221–224, July 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Culik:1984:ITA

[412] K. Culik, II and S. Yu. Iterative tree automata. Theoretical Computer Science, 32(3):227–247, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Otto:1984:FCR

[413] F. Otto. Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group. Theoretical Computer Science, 32(3):249–260, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Niemi:1984:UFE

[414] V. Niemi. The undecidability of form equivalence for context-free and E0L forms. Theoretical Computer Science, 32(3):261–277, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Avenhaus:1984:CIC

[415] J. Avenhaus and K. Madlener. On the complexity of intersection and conjugacy problems in free groups. Theoretical Computer Science, 32(3):279– 295, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ketonen:1984:DFP

[416] J. Ketonen and R. Weyhrauch. A decidable fragment of predicate calculus (theorem proving). Theoretical Computer Science, 32(3):297–307, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deBruijn:1984:SMD

[417] N. G. de Bruijn. Some machines defined by directed graphs. Theoretical Computer Science, 32(3):309–319, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Miyano:1984:AFA

[418] S. Miyano and T. Hayashi. Alternating finite automata on omega-words. Theoretical Computer Science, 32(3):321– 330, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Staiger:1984:PLO

[419] L. Staiger. Projection lemmas for omega-languages. Theoretical Computer Science, 32(3):331–337, August 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jacob:1984:FPS

[420] G. Jacob and C. Reutenauer. On formal power series defined by infinite linear systems. Theoretical Computer Science, 32(3):339–340, August 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Anonymous:1984:SCF

[421] Anonymous. Second Conference on Foundations of Software Technology and Theoretical Computer Science. Theoretical Computer Science, 33(1):??, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Siromoney:1984:IAC

[422] R. Siromoney, K. G. Subramanian, and V. R. Dare. Infinite arrays and controlled deterministic table 0L array systems. Theoretical Computer Science, 33 (1):3–11, September 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Jantzen:1984:HIS

[423] M. Jantzen and M. Kudlek. Homomorphic images of sentential form languages defined by semi-Thue systems. Theoretical Computer Science, 33(1):13– 43, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Astesiano:1984:PCL

[424] E. Astesiano and E. Zucca. Parametric channels via label expressions in CCS. Theoretical Computer Science, 33(1):45– 63, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Apt:1984:FTR

[425] K. R. Apt, A. Pnueli, and J. Stavi. Fair termination revisited-with delay. Theoretical Computer Science, 33(1):65–84, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ravikumar:1984:CKP

[426] B. Ravikumar and K. B. Lakshmanan.

Coping with known patterns of lies in a search game. Theoretical Computer Science, 33(1):85–94, September 1984. CO-DEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Dybjer:1984:SRD

[427] P. Dybjer. Some results on the deductive structure of join dependencies. Theoretical Computer Science, 33(1):95– 105, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Madhavan:1984:SAR

[428] C. E. Veni Madhavan. Secondary attribute retrieval using tree data structures. Theoretical Computer Science, 33 (1):107–116, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Pan:1984:TTA

[429] V. Ya. Pan. The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations. Theoretical Computer Science, 33(1):117–138, September 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Broy:1984:SSM

[430] M. Broy, M. Wirsing, and C. Pair. A systematic study of models of abstract data types. Theoretical Computer Science, 33 (2-3):139–174, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kaplan:1984:CRR

[431] S. Kaplan. Conditional rewrite rules. Theoretical Computer Science, 33(2-3): 175–193, October 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Fehr:1984:EPT

[432] E. Fehr. Expressive power of typed and type-free programming languages. Theoretical Computer Science, 33(2-3):195– 238, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Maon:1984:TSC

[433] Y. Maon and A. Yehudai. On test sets for checking morphism equivalence on languages with fair distribution of letters. Theoretical Computer Science, 33 (2-3):239–240, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Otto:1984:SUR

[434] F. Otto. Some undecidability results for non-monadic Church–Rosser Thue systems. Theoretical Computer Science, 33 (2-3):261–278, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Soundararajan:1984:DSC

[435] N. Soundararajan. Denotational semantics of CSP. Theoretical Computer Science, 33(2-3):279–304, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Huynh:1984:DIC

[436] D. T. Huynh. Deciding the inequivalence of context-free grammars with 1- letter terminal alphabet is Σ_{2}^{p}-complete. Theoretical Computer Science, 33(2-3):305– 326, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Harju:1984:EBA

[437] T. Harju and M. Linna. The equations h(w) = w^{n} in binary alphabets. Theoretical Computer Science, 33(2-3):327– 329, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Perrin:1984:ORM

[438] D. Perrin and P. Schupp. On the onerelator monoids which are groups. Theoretical Computer Science, 33(2-3):331– 334, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Girault-Beauquier:1984:BRL

[439] D. Girault-Beauquier. Bilimits of recognisable languages. Theoretical Computer Science, 33(2-3):335–342, October 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Nesetril:1984:SNR

[440] J. Nesetril. Some nonstandard Ramsey like applications. Theoretical Computer Science, 34(1–2):3–15, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Hartmanis:1984:CTN

[441] J. Hartmanis and Y. Yesha. Computation times of NP sets of different densities. Theoretical Computer Science, 34 (1–2):17–32, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Winskel:1984:ST

[442] G. Winskel. Synchronization trees. Theoretical Computer Science, 34(1–2):33– 82, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deNicola:1984:TEP

[443] R. de Nicola and M. C. B. Hennessy. Testing equivalences for processes (concurrent programming). Theoretical Computer Science, 34(1–2):83– 133, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

deBakker:1984:LTB

[444] J. W. de Bakker, J. A. Bergstra, J. W.

Klop, and J.-J. C. Meyer. Linear time and branching time semantics for recursion with merge (parallel programming languages). Theoretical Computer Science, 34(1–2):135–156, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Vitanyi:1984:SMS

[445] P. M. B. Vitanyi. On the simulation of many storage heads by one. Theoretical Computer Science, 34(1–2):157– 168, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Delest:1984:ALP

[446] M.-P. Delest and G. Viennot. Algebraic languages and polyomino enumeration. Theoretical Computer Science, 34(1–2): 169–206, November 1984. CODEN TC-SCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Lenstra:1984:FMI

[447] A. K. Lenstra. Factoring multivariate integral polynomials. Theoretical Computer Science, 34(1–2):207–213, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Cohen:1984:SES

[448] S. Cohen, D. Lehmann, and A. Pnueli.

Symmetric and economical solutions to the mutual exclusion problem in a distributed system. Theoretical Computer Science, 34(1–2):215–225, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Sato:1984:ESP

[449] T. Sato and H. Tamaki. Enumeration of success patterns in logic programs (PROLOG). Theoretical Computer Science, 34(1–2):227–240, November 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Clerbout:1984:PCF

[450] M. Clerbout and M. Latteux. Partial commutations and faithful rational transductions. Theoretical Computer Science, 34(3):241–254, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Itzhaik:1984:NFN

[451] Y. Itzhaik and A. Yehudai. New families of non real time DPDAs and their decidability results. Theoretical Computer Science, 34(3):255–274, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Kamimura:1984:TOD

[452] T. Kamimura and A. Tang. Total objects of domains. Theoretical Computer Science, 34(3):275–288, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Gogolla:1984:AOS

[453] M. Gogolla, K. Drosten, U. Lipeck, and H.-D. Ehrich. Algebraic and operational semantics of specifications allowing exceptions and errors. Theoretical Computer Science, 34(3):289–313, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Ito:1984:MPD

[454] M. Ito, M. Iwasaki, K. Taniguchi, and T. Kasami. Membership problems for data dependencies in relational expressions. Theoretical Computer Science, 34 (3):315–335, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Schoning:1984:SG

[455] U. Schoning. On small generators. Theoretical Computer Science, 34(3):337– 341, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).

Bancilhon:1984:SCA

[456] F. Bancilhon and P. Richard. A sound and complete axiomatization of embedded cross dependencies. Theoretical Computer Science, 34(3):343–350, December 1984. CODEN TCSCDI. ISSN 0304-3975 (print), 1879-2294 (electronic).