☰

Andrzej Ehrenfeucht - Publications

Affiliations: 
University of Colorado, Boulder, Boulder, CO, United States 
Website:
http://www.cs.colorado.edu/~andrzej/
Tree Info Similar researchers PubMed Report error

70 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2011 Ehrenfeucht A, McConnell RM, Osheim N, Woo SW. Position heaps: A simple and dynamic text indexing data structure Journal of Discrete Algorithms. 9: 100-121. DOI: 10.1016/J.Jda.2010.12.001  0.312
2003 Ehrenfeucht A, Rozenberg G. Forbidding-enforcing systems Theoretical Computer Science. 292: 611-638. DOI: 10.1016/S0304-3975(01)00088-3  0.334
1997 Ehrenfeucht A, Rozenberg G, Salomaa K. Semantics of nonsequential tree-based computation schemes Fundamenta Informaticae. 29: 305-324. DOI: 10.3233/Fi-1997-29401  0.306
1996 Ehrenfeucht A, Pǎun G, Rozenberg G. The linear landscape of external contextual languages Acta Informatica. 33: 571-593. DOI: 10.1007/Bf03036464  0.359
1996 Ehrenfeucht A, Engelfriet J, Rozenberg G. Finite languages for the representation of finite graphs Journal of Computer and System Sciences. 52: 170-184. DOI: 10.1006/Jcss.1996.0013  0.369
1995 Ehrenfeucht A, Engelfriet J, Pas Pt, Rozenberg G. GRAMMATICAL CODES OF TREES AND TERMINALLY CODED GRAMMARS Fundamenta Informaticae. 23: 1-32. DOI: 10.3233/Fi-1995-2311  0.373
1995 Knill E, Ehrenfeucht A, Haussler D. The size of k-pseudotrees Discrete Mathematics. 141: 185-194. DOI: 10.1016/0012-365X(93)E0197-C  0.47
1994 Ehrenfeucht A, ten Pas P, Rozenberg G. Context-free text grammars Acta Informatica. 31: 161-206. DOI: 10.1007/Bf01192159  0.36
1994 Ehrenfeucht A, Gabow HN, Mcconnell RM, Sullivan SJ. An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs Journal of Algorithms. 16: 283-294. DOI: 10.1006/Jagm.1994.1013  0.313
1993 Ehrenfeucht A, Hoogeboom HJ, Rozenberg G. On the structure of recognizable languages of dependence graphs Rairo - Theoretical Informatics and Applications. 27: 7-22. DOI: 10.1051/Ita/1993270100071  0.311
1993 Ehrenfeucht A, Rozenberg G. T-structures, T-functions, and texts Theoretical Computer Science. 116: 227-290. DOI: 10.1016/0304-3975(93)90323-L  0.337
1990 Ehrenfeucht A, Rozenberg G. Partial (set) 2-structures - Part I: basic notions and the representation problem Acta Informatica. 27: 315-342. DOI: 10.1007/Bf00264611  0.317
1989 Blumer A, Ehrenfeucht A, Haussler D, Warmuth MK. Learnability and the Vapnik-Chervonenkis dimension Journal of the Acm. 36: 929-965. DOI: 10.1145/76359.76371  0.498
1989 Ehrenfeucht A, Haussler D, Kearns M, Valiant L. A general lower bound on the number of examples needed for learning Information and Computation. 82: 247-261. DOI: 10.1016/0890-5401(89)90002-3  0.494
1989 Ehrenfeucht A, Haussler D. Learning decision trees from random examples Information and Computation. 82: 231-246. DOI: 10.1016/0890-5401(89)90001-1  0.424
1989 Blumer A, Ehrenfeucht A, Haussler D. Average sizes of suffix trees and DAWGs Discrete Applied Mathematics. 24: 37-45. DOI: 10.1016/0166-218X(92)90270-K  0.504
1988 Ehrenfeucht A, Haussler D. A new distance metric on strings computable in linear time Discrete Applied Mathematics. 20: 191-203. DOI: 10.1016/0166-218X(88)90076-5  0.492
1987 Blumer A, Blumer J, Haussler D, McConnell R, Ehrenfeucht A. COMPLETE INVERTED FILES FOR EFFICIENT TEXT RETRIEVAL AND ANALYSIS. Journal of the Acm. 34: 578-595. DOI: 10.1145/28869.28873  0.523
1987 Ehrenfeucht A, Haemer J, Haussler D. Quasi-Monotonic Sequences: Theory, Algorithms and Applications Siam Journal On Algebraic Discrete Methods. 8: 410-429. DOI: 10.1137/0608034  0.43
1987 Blumer A, Ehrenfeucht A, Haussler D, Warmuth MK. Occam's Razor Information Processing Letters. 24: 377-380. DOI: 10.1016/0020-0190(87)90114-1  0.489
1986 Ehrenfeucht A, Hoogeboom HJ, Rozenberg G. Coordinated pair systems ; part II : sparse structure of Dyck words and Ogden's lemma Rairo - Theoretical Informatics and Applications. 20: 425-439. DOI: 10.1051/Ita/1986200404251  0.304
1986 Ehrenfeucht A, Hoogeboom HJ, Rozenberg G. On the active and full use of memory in right-boundary grammars and push-down automata Theoretical Computer Science. 48: 201-228. DOI: 10.1016/0304-3975(86)90095-2  0.322
1986 Aalbersberg IJ, Rozenberg G, Ehrenfeucht A. On the membership problem for regular DNLC grammars Discrete Applied Mathematics. 13: 79-85. DOI: 10.1016/0166-218X(86)90070-3  0.348
1985 Bucher W, Ehrenfeucht A, Haussler D. On total regulators generated by derivation relations Theoretical Computer Science. 40: 131-148. DOI: 10.1016/0304-3975(85)90162-8  0.533
1985 Blumer A, Blumer J, Haussler D, Ehrenfeucht A, Chen MT, Seiferas J. The smallest automation recognizing the subwords of a text Theoretical Computer Science. 40: 31-55. DOI: 10.1016/0304-3975(85)90157-4  0.503
1985 Ehrenfeucht A, Kleijn HCM, Rozenberg G. Adding global forbidding context to context-free grammars Theoretical Computer Science. 37: 337-360. DOI: 10.1016/0304-3975(85)90096-9  0.349
1985 Ehrenfeucht A, Rozenberg G, Ruohonen K. A morphic representation of EOL languages and other ETOL languages Discrete Applied Mathematics. 12: 115-122. DOI: 10.1016/0166-218X(85)90065-4  0.342
1985 Ehrenfeucht A, Rozenberg G, Verraedt R. A combinatorial property of EOL languages Mathematical Systems Theory. 18: 207-235. DOI: 10.1007/Bf01699470  0.31
1984 Ehrenfeucht A, Haussler D, Rozenberg G. On ambiguity in DOS systems Rairo. Informatique ThéOrique. 18: 279-295. DOI: 10.1051/Ita/1984180302791  0.472
1984 Ehrenfeucht A, Rozenberg G. An easy proof of Greibach normal form Information and Control. 63: 190-199. DOI: 10.1016/S0019-9958(84)80013-3  0.304
1984 Ehrenfeucht A, Main MG, Rozenberg G. Restrictions on NLC graph grammars Theoretical Computer Science. 31: 211-223. DOI: 10.1016/0304-3975(84)90135-X  0.328
1984 Ehrenfeucht A, Rozenberg G. On regularity of languages generated by copying systems Discrete Applied Mathematics. 8: 313-317. DOI: 10.1016/0166-218X(84)90129-X  0.357
1984 Ehrenfeucht A, Haussler D, Rozenberg G, Zeiger P. On dos languages and dos mappings Semigroup Forum. 29: 123-148. DOI: 10.1007/Bf02573321  0.535
1983 Ehrenfeucht A, Rozenberg G. Repetition of subwords in DOL languages Information and Control. 59: 13-35. DOI: 10.1016/S0019-9958(83)80028-X  0.354
1983 Ehrenfeucht A, Rozenberg G, Verraedt R. On inherently ambiguous E0L languages Theoretical Computer Science. 28: 197-214. DOI: 10.1016/0304-3975(83)90071-3  0.36
1983 Ehrenfeucht A, Haussler D, Rozenberg G. On regularity of context-free languages Theoretical Computer Science. 27: 311-332. DOI: 10.1016/0167-7136(83)90297-4  0.53
1983 Ehrenfeucht A, Engelfriet J, Rozenberg G. Context Free Normal Systems and ETOL Systems Journal of Computer and System Sciences. 26: 34-46. DOI: 10.1016/0022-0000(83)90019-3  0.338
1983 Ehrenfeucht A, Karhumäki J, Rozenberg G. On binary equality sets and a solution to the test set conjecture in the binary case Journal of Algebra. 85: 76-85. DOI: 10.1016/0021-8693(83)90119-9  0.312
1983 Ehrenfeucht A, Rozenberg G. On the subword complexity of m-free D0L languages Information Processing Letters. 17: 121-124. DOI: 10.1016/0020-0190(83)90050-9  0.333
1983 Ehrenfeucht A, Rozenberg G. On the subword complexity of locally catenative dol languages Information Processing Letters. 16: 7-9. DOI: 10.1016/0020-0190(83)90003-0  0.322
1983 Ehrenfeucht A, Rozenberg G. On the size of the alphabet and the subword complexity of square-free DOI languages Semigroup Forum. 26: 215-223. DOI: 10.1007/Bf02572832  0.356
1982 Ehrenfeucht A, Karhumäki J, Rozenberg G. The (generalized) post correspondence problem with lists consisting of two words is decidable Theoretical Computer Science. 21: 119-144. DOI: 10.1016/0304-3975(89)90080-7  0.32
1982 Ehrenfeucht A, Rozenberg G. Representation theorems using DOS languages Theoretical Computer Science. 21: 75-90. DOI: 10.1016/0304-3975(82)90089-5  0.354
1982 Ehrenfeucht A, Rozenberg G, Verraedt R. Basic formulas and languages. PART II.Applications to E0L systems and forms Discrete Applied Mathematics. 4: 11-22. DOI: 10.1016/0166-218X(82)90030-0  0.367
1981 Ehrenfeucht A, Parikh R, Rozenberg G. Pumping Lemmas for Regular Sets Siam Journal On Computing. 10: 536-541. DOI: 10.1137/0210039  0.334
1981 Ehrenfeucht A, Rozenberg G, Vermeir D. On Etol Systems with Finite Tree-Rank Siam Journal On Computing. 10: 40-58. DOI: 10.1137/0210004  0.35
1981 Ehrenfeucht A, Rozenberg G. FPOL systems generating counting languages Rairo. Informatique ThéOrique. 15: 161-173. DOI: 10.1051/Ita/1981150201611  0.354
1981 Ehrenfeucht A, Rozenberg G. On the subword complexity of square-free DOL languages Theoretical Computer Science. 16: 25-32. DOI: 10.1016/0304-3975(81)90028-1  0.369
1981 Ehrenfeucht A, Rozenberg G, Verraedt R. Basic formulas and languages Part I. The theory Discrete Applied Mathematics. 3: 235-255. DOI: 10.1016/0166-218X(81)90002-0  0.318
1981 Ehrenfeucht A, Rozenberg G. On the subword complexity of DOL languages with a constant distribution Information Processing Letters. 13: 108-113. DOI: 10.1016/0020-0190(81)90121-6  0.309
1981 Ehrenfeucht A, Rozenberg G. On the Subword Complexity and Square-Freeness of Formal Languages Theoretical Computer Science. 1-4. DOI: 10.1007/Bfb0017289  0.327
1980 Ehrenfeucht A, Rozenberg G. ON BASIC PROPERTIES OF DOS SYSTEMS AND LANGUAGES Information and Control. 47: 137-153. DOI: 10.1016/S0019-9958(80)90749-4  0.373
1980 Ehrenfeucht A, Rozenberg G. Every two equivalent D0L systems have a regular true envelope Theoretical Computer Science. 10: 45-52. DOI: 10.1016/0304-3975(80)90071-7  0.301
1980 Ehrenfeucht A, Rozenberg G. On ambiguity in E0L systems Theoretical Computer Science. 12: 127-134. DOI: 10.1016/0304-3975(80)90025-0  0.336
1980 Ehrenfeucht A, Rozenberg G. On the emptiness of the intersection of two DOS languages problem Information Processing Letters. 10: 223-225. DOI: 10.1016/0020-0190(80)90145-3  0.335
1979 Ehrenfeucht A, Mostowski A. Models of axiomatic theories admitting automorphisms Studies in Logic and the Foundations of Mathematics. 93: 494-512. DOI: 10.1016/S0049-237X(09)70467-7  0.508
1979 Ehrenfeucht A, Mostowski A. A Compact Space of Models of First Order Theories Studies in Logic and the Foundations of Mathematics. 93: 432-436. DOI: 10.1016/S0049-237X(09)70275-7  0.508
1979 Ehrenfeucht A, Rozenberg G, Vermeir D. On ET0L Systems with rank Journal of Computer and System Sciences. 19: 237-255. DOI: 10.1016/0022-0000(79)90003-5  0.307
1978 Ehrenfeucht A, Rozenberg G. On the structure of derivations in deterministic ET0L systems Journal of Computer and System Sciences. 17: 331-347. DOI: 10.1016/0022-0000(78)90013-2  0.379
1978 Ehrenfeucht A, Karhumäki J, Rozenberg G. A note on DOL length sets Discrete Mathematics. 22: 233-242. DOI: 10.1016/0012-365X(78)90056-0  0.326
1977 Ehrenfeucht A, Rozenberg G. ON SOME CONTEXT FREE LANGUAGES THAT ARE NOT DETERMINISTIC ETOL LANGUAGES Rairo Inf Theor Theor Comput Sci. 11: 273-291. DOI: 10.1051/Ita/1977110402731  0.339
1976 Ehrenfeucht A, Rozenberg G, Skyum S. A relationship between ET0L and EDT0L languages Theoretical Computer Science. 1: 325-330. DOI: 10.1016/0304-3975(76)90076-1  0.34
1976 Ehrenfeucht A, Lee KP, Rozenberg G. On the number of subwords of everywhere growing DTOL languages Discrete Mathematics. 15: 223-234. DOI: 10.1016/0012-365X(76)90027-3  0.365
1976 Ehrenfeucht A, Rozenberg G. On proving that certain languages are not ETOL Acta Informatica. 6: 407-415. DOI: 10.1007/Bf00268142  0.37
1975 Ehrenfeucht A, Rozenberg G. A pumping theorem for deterministic ETOL languages Revue FrançAise D'Automatique Informatique Recherche OpéRationnelle. Informatique ThéOrique. 9: 13-23. DOI: 10.1051/Ita/197509R200131  0.346
1975 Ehrenfeucht A, Lee KP, Rozenberg G. Subword complexities of various classes of deterministic developmental languages with interactions International Journal of Computer & Information Sciences. 4: 219-236. DOI: 10.1007/Bf01007760  0.364
1974 Ehrenfeucht A, Rozenberg G. The Equality of EOL Languages and Codings of OL Languages International Journal of Computer Mathematics. 4: 95-104. DOI: 10.1080/00207167408803083  0.338
1974 Ehrenfeucht A, Rozenberg G. The number of occurrences of letters versus their distribution in some EOL languages Information and Control. 26: 256-271. DOI: 10.1016/S0019-9958(74)91379-5  0.363
1974 Ehrenfeucht A, Rozenberg G. Nonterminals versus homomorphisms in defining languages for some classes of rewriting systems Acta Informatica. 3: 265-283. DOI: 10.1007/Bf00288638  0.37
1973 Ehrenfeucht A, Rozenberg G. A limit theorem for sets of subwords in deterministic TOL languages Information Processing Letters. 2: 70-73. DOI: 10.1016/0020-0190(73)90003-3  0.365
Show low-probability matches.