Edit Profile (opens in new tab) Ehrenfeucht, Andrzej Co-Author Distance Author ID: ehrenfeucht.andrzej Published as: Ehrenfeucht, A.; Ehrenfeucht, Andrzej Homepage: http://www.cs.colorado.edu/~andrzej/ External Links: MGP · Wikidata · dblp · GND · IdRef Documents Indexed: 233 Publications since 1954, including 2 Books 1 Contribution as Editor · 1 Further Contribution Biographic References: 3 Publications Co-Authors: 74 Co-Authors with 219 Joint Publications 1,751 Co-Co-Authors all top 5 Co-Authors 15 single-authored 157 Rozenberg, Grzegorz 20 Harju, Tero 17 Haussler, David 15 Mycielski, Jan 10 Hoogeboom, Hendrik Jan 8 Petre, Ion 7 McConnell, Ross M. 7 Prescott, David M. 6 Blumer, Anselm C. 6 ten Pas, Paulien 5 Kleijn, Jetty 5 Main, Michael G. 5 Silberger, Donald M. 5 Verraedt, Raymond 4 Faber, Vance 4 Hage, Jurriaan 4 Karhumaki, Juhani 4 Koutny, Maciej 3 Blumer, Janet A. 3 Brijder, Robert 3 Engelfriet, Joost 3 Fajtlowicz, Siemion 3 Păun, Gheorghe 3 Ruohonen, Keijo 3 Zeiger, Paul 2 Bucher, Walter 2 Deutz, André H. 2 Fuhrken, Gebhard 2 Grzegorek, Edward 2 Kahn, Jeff D. 2 Maddux, Roger D. 2 Malitz, Jerome I. 2 Maurer, Hermann A. 2 Mostowski, Andrzej Stanisław 2 Orłowska, Ewa S. 2 Salomaa, Arto Kustaa 2 Salomaa, Kai T. 2 van Vugt, Nikè 2 Vermeir, Dirk 2 Warmuth, Manfred K. 2 Woo, Sung-Whan 1 Aalbersberg, Ijsbrand Jan 1 Abelson, Harold 1 Apostolico, Alberto 1 Bean, Dwight R. 1 Bersted, J. 1 Bezem, J. J. 1 Brown, Allison Thompson 1 Chang, Chen-Chung 1 Culik, Karel II 1 Dziobiak, Wiesław 1 Ede, D. A. 1 Ehrig, Hartmut 1 Erickson, Ralph O. 1 Feferman, Solomon 1 Fickett, James Wildon 1 Fisz, Marek 1 Foreman, Matthew D. 1 Frijters, Dinnus 1 Gabow, Harold N. 1 Golze, Ulrich 1 Grace, Jacqueline B. 1 Haemer, Jeffrey 1 Harte, C. 1 Jürgensen, Helmut 1 Kearns, Michael Justin 1 Kierstead, Henry A. 1 Knill, Emanuel 1 Kreisel, Georg 1 Kreowski, Hans-Jörg 1 Lewis, John Henry 1 Lindenmayer, Aristid 1 Łoś, Jerzy 1 Lück, Hermann B. 1 Lück, Jacqueline 1 Marek, V. Wiktor 1 Mateescu, Alexandru 1 Mayoh, Brian H. 1 McNulty, George F. 1 Moran, Gadi 1 Nagl, Manfred 1 Nielsen, Mogens 1 Opartny, J. 1 Ortman, A. 1 Osheim, Nissa 1 Pawlak, Zdzisław 1 Paz, Azaria 1 Peters, James Francis III 1 Raven, C. P. 1 Rosenfeld, Azriel 1 Sawitch, W. J. 1 Seiferas, Joel I. 1 Shur, H. J. 1 Simmons, Gustavus James 1 Skowron, Andrzej 1 Soittola, Matti 1 Srebrny, Marian 1 Sullivan, Stephen J. 1 Thierrin, Gabriel 1 Valiant, Leslie Gabriel ...and 5 more Co-Authors all top 5 Serials 36 Theoretical Computer Science 11 Discrete Applied Mathematics 9 Acta Informatica 9 Information Processing Letters 9 Bulletin de l’Académie Polonaise des Sciences, Série des Sciences Mathématiques, Astronomiques et Physiques 8 Discrete Mathematics 7 Fundamenta Mathematicae 6 Information and Control 6 Journal of Computer and System Sciences 6 RAIRO, Informatique Théorique 6 Annales Societatis Mathematicae Polonae. Series IV 6 International Journal of Foundations of Computer Science 5 RAIRO. Informatique Théorique et Applications 4 Algebra Universalis 4 Journal of the Association for Computing Machinery 4 Journal of Combinatorial Theory. Series A 4 Semigroup Forum 4 Bulletin de l’Académie Polonaise des Sciences, Classe 3 3 Information and Computation 3 MSCS. Mathematical Structures in Computer Science 3 Fundamenta Informaticae 2 Archiv für Mathematische Logik und Grundlagenforschung 2 Colloquium Mathematicum 2 Foundations of Control Engineering 2 The Journal of Symbolic Logic 2 Mathematical Systems Theory 2 SIAM Journal on Computing 2 Nederlandse Akademie van Wetenschappen. Proceedings. Series A. Indagationes Mathematicae 2 Journal of Theoretical Biology 1 American Mathematical Monthly 1 Israel Journal of Mathematics 1 Acta Cybernetica 1 Ars Combinatoria 1 International Journal of Computer & Information Sciences 1 International Journal of Game Theory 1 Journal of Algebra 1 Journal of Approximation Theory 1 Mathematica Scandinavica 1 Pacific Journal of Mathematics 1 Journal of Algorithms 1 SIAM Journal on Algebraic and Discrete Methods 1 International Journal of Computer Mathematics 1 Proceedings of the National Academy of Sciences of the United States of America 1 Theory of Computing Systems 1 Soft Computing 1 Journal of Discrete Algorithms 1 Bulletin of the American Mathematical Society 1 Annales Societatis Mathematicae Polonae 1 Natural Computing Series all top 5 Fields 164 Computer science (68-XX) 33 Combinatorics (05-XX) 27 Mathematical logic and foundations (03-XX) 17 Biology and other natural sciences (92-XX) 15 Group theory and generalizations (20-XX) 7 Order, lattices, ordered algebraic structures (06-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 5 Information and communication theory, circuits (94-XX) 4 General algebraic systems (08-XX) 2 General and overarching topics; collections (00-XX) 2 Convex and discrete geometry (52-XX) 2 General topology (54-XX) 2 Systems theory; control (93-XX) 1 History and biography (01-XX) 1 Number theory (11-XX) 1 Field theory and polynomials (12-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Approximations and expansions (41-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Operations research, mathematical programming (90-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 190 Publications have been cited 2,851 times in 2,021 Documents Cited by ▼ Year ▼ Learnability and the Vapnik-Chervonenkis dimension. Zbl 0697.68079Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. 291 1989 An application of games to the completeness problem for formalized theories. Zbl 0096.24303Ehrenfeucht, A. 151 1961 Avoidable patterns in strings of symbols. Zbl 0428.05001Bean, Dwight R.; Ehrenfeucht, Andrzej; McNulty, George F. 133 1979 Occam’s razor. Zbl 0653.68084Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. 132 1987 Positional strategies for mean payoff games. Zbl 0499.90098Ehrenfeucht, A.; Mycielski, J. 122 1979 Reaction systems. Zbl 1108.68056Ehrenfeucht, A.; Rozenberg, G. 88 2007 The smallest automaton recognizing the subwords of a text. Zbl 0574.68070Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M. T.; Seiferas, J. 75 1985 A general lower bound on the number of examples needed for learning. Zbl 0679.68158Ehrenfeucht, Andrzej; Haussler, David; Kearns, Michael; Valiant, Leslie 67 1989 Primitivity is hereditary for 2-structures. Zbl 0701.05053Ehrenfeucht, A.; Rozenberg, G. 62 1990 The theory of 2-structures. A framework for decomposition and transformation of graphs. Zbl 0981.05002Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 57 1999 A tour of reaction systems. Zbl 1252.68115Brijder, Robert; Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz 52 2011 On regularity of context-free languages. Zbl 0553.68044Ehrenfeucht, A.; Haussler, D.; Rozenberg, G. 48 1983 Efficient detection of quasiperiodicities in strings. Zbl 0804.68109Apostolico, Alberto; Ehrenfeucht, Andrzej 43 1993 Partial (set) 2-structures. II: State spaces of concurrent systems. Zbl 0696.68083Ehrenfeucht, A.; Rozenberg, G. 42 1990 Theory of 2-structures. I: Clans, basic subclasses, and morphisms. Zbl 0701.05051Ehrenfeucht, A.; Rozenberg, G. 41 1990 Computation in living cells. Gene assembly in ciliates. Zbl 1069.68048Ehrenfeucht, A.; Harju, T.; Petre, I.; Prescott, D. M.; Rozenberg, G. 39 2004 Subword complexities of various classes of deterministic developmental languages without interactions. Zbl 0316.68043Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G. 38 1975 Elementary homomorphisms and a solution of the DOL sequence equivalence problem. Zbl 0407.68085Ehrenfeucht, A.; Rozenberg, G. 38 1978 Complexity measures for regular expressions. Zbl 0329.94024Ehrenfeucht, Andrzej; Zeiger, Paul 36 1976 Partial (set) 2-structures. I: Basic notions and the representation problems. Zbl 0696.68082Ehrenfeucht, A.; Rozenberg, G. 35 1990 Periodicity and unbordered segments of words. Zbl 0416.20051Ehrenfeucht, Andrzej; Silberger, D. M. 34 1979 Complete inverted files for efficient text retrieval and analysis. Zbl 1433.68118Blumer, A.; Blumer, J.; Haussler, D.; McConnell, R.; Ehrenfeucht, A. 33 1987 Introducing time in reaction systems. Zbl 1156.93306Ehrenfeucht, A.; Rozenberg, G. 32 2009 The (generalized) Post correspondence problem with lists consisting of two words is decidable. Zbl 0493.68076Ehrenfeucht, A.; Karhumäki, Juhani; Rozenberg, G. 31 1982 Theory of 2-structures. II: Representation through labeled tree families. Zbl 0701.05052Ehrenfeucht, A.; Rozenberg, G. 31 1990 Models of axiomatic theories admitting automorphisms. Zbl 0073.00704Ehrenfeucht, A.; Mostowski, A. 29 1956 Each regular code is included in a maximal regular code. Zbl 0609.68053Ehrenfeucht, A.; Rozenberg, G. 29 1986 Functions defined by reaction systems. Zbl 1213.68259Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz 26 2011 Events and modules in reaction systems. Zbl 1119.93011Ehrenfeucht, A.; Rozenberg, G. 25 2007 On some context-free languages that are not deterministic ETOL languages. Zbl 0378.68040Ehrenfeucht, A.; Rozenberg, G. 22 1977 Finding a homomorphism between two words is NP-complete. Zbl 0414.68022Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 22 1979 Minimal reaction systems. Zbl 1382.68070Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 22 2012 Building the minimal DFA for the set of all subwords of a word on-line in linear time. Zbl 0554.68058Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; McConnell, R. 21 1984 Learning decision trees from random examples. Zbl 0679.68157Ehrenfeucht, Andrzej; Haussler, David 21 1989 On the subword complexity of square-free DOL languages. Zbl 0481.68073Ehrenfeucht, A.; Rozenberg, G. 20 1981 Reaction systems with duration. Zbl 1330.68068Brijder, Robert; Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 20 2011 A relationship between ETOL and EDTOL languages. Zbl 0339.68055Ehrenfeucht, A.; Rozenberg, G.; Skyum, S. 18 1976 Combinatorics of life and death for reaction systems. Zbl 1192.68458Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz 18 2010 Repetition of subwords in DOL languages. Zbl 0549.68076Ehrenfeucht, A.; Rozenberg, G. 18 1983 An \(O(n^ 2)\) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. Zbl 0797.68079Ehrenfeucht, Andrzej; Gabow, Harold N.; McConnell, Ross M.; Sullivan, Stephen J. 17 1994 Simplifications of homomorphisms. Zbl 0387.68062Ehrenfeucht, A.; Rozenberg, G. 17 1978 Formal systems for gene assembly in ciliates. Zbl 1063.68054Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 16 2003 Evolving reaction systems. Zbl 1371.68083Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 14 2017 On binary equality sets and a solution to the test set conjecture in the binary case. Zbl 0523.68066Ehrenfeucht, A.; Karhumäki, Juhani; Rozenberg, G. 14 1983 Reaction systems: a model of computation inspired by the functioning of the living cell. Zbl 1395.68122Ehrenfeucht, Andrzej; Petre, Ion; Rozenberg, Grzegorz 14 2017 Pumping lemmas for regular sets. Zbl 0461.68081Ehrenfeucht, A.; Parikh, R.; Rozenberg, G. 13 1981 Do infinite nilpotent groups always have equipotent Abelian subgroups? Zbl 0256.20032Ehrenfeucht, A.; Faber, V. 13 1972 Interpolation of functions over a measure space and conjectures about memory. Zbl 0308.65008Ehrenfeucht, Andrzej; Mycielski, Jan 13 1973 Reaction systems: a natural computing approach to the functioning of living cells. Zbl 1256.68071Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 13 2013 On regularity of languages generated by copying systems. Zbl 0549.68075Ehrenfeucht, A.; Rozenberg, G. 13 1984 Characterizing the micronuclear gene patterns in ciliates. Zbl 1001.68903Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Rozenberg, Grzegorz 12 2002 Basic notions of reaction systems. Zbl 1117.68349Ehrenfeucht, A.; Rozenberg, G. 12 2004 Universal and simple operations for gene assembly in ciliates. Zbl 1007.68067Ehrenfeucht, Andrzej; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 12 2001 Discernible elements in models for Peano arithmetic. Zbl 0279.02036Ehrenfeucht, Andrzej 12 1973 Nonterminals versus homomorphisms in defining languages for some classes of rewriting systems. Zbl 0313.68062Ehrenfeucht, A.; Rozenberg, G. 12 1974 String and graph reduction systems for gene assembly in ciliates. Zbl 1007.68127Ehrenfeucht, Andrzej; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 12 2002 Zoom structures and reaction systems yield exploration systems. Zbl 1360.68463Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 12 2014 Average sizes of suffix trees and DAWGs. Zbl 0679.68031Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David 12 1989 Abbreviating proofs by adding new axioms. Zbl 0216.01002Ehrenfeucht, A.; Mycielski, J. 12 1971 Template-guided recombination for IES elimination and unscrambling of genes in stichotrichous ciliates. Zbl 1464.92175Prescott, David M.; Ehrenfeucht, Andrzej; Rozenberg, G. 12 2003 Polynomial functions with exponentiation are well ordered. Zbl 0308.06001Ehrenfeucht, A. 11 1973 Restrictions on NLC graph grammars. Zbl 0566.68062Ehrenfeucht, Andrzej; Main, Michael G.; Rozenberg, Grzegorz 11 1984 On subword complexities of homomorphic images of languages. Zbl 0495.68069Ehrenfeucht, A.; Rozenberg, G. 10 1982 T-structures, T-functions, and texts. Zbl 0783.68097Ehrenfeucht, A.; Rozenberg, G. 10 1993 Universal terms of the form \(B^nA^m\). Zbl 0441.20037Ehrenfeucht, Andrzej; Silberger, D. M. 10 1980 The equality of EOL languages and codings of OL languages. Zbl 0314.68027Ehrenfeucht, A.; Rozenberg, G. 10 1974 On the subword complexity of DOL languages with a constant distribution. Zbl 0546.68062Ehrenfeucht, A.; Rozenberg, G. 10 1981 A limit theorem for set of subwords in deterministic TOL laguages. Zbl 0299.68044Ehrenfeucht, A.; Rozenberg, G. 9 1973 Automata, languages, development. Zbl 0346.92001 9 1976 Representability of recursively enumerable sets in formal theories. Zbl 0118.25102Ehrenfeucht, A.; Feferman, S. 9 1961 Sur les produits cartésiens des groupes cycliques infinis. Zbl 0055.25304Ehrenfeucht, A.; Łoś, Jerzy 9 1954 Some problem in elementary arithmetics. Zbl 0362.02049Jensen, D.; Ehrenfeucht, A. 8 1976 Angular 2-structures. Zbl 0753.05069Ehrenfeucht, A.; Rozenberg, G. 8 1992 On simplifications of PDOL systems. Zbl 0414.68046Ehrenfeucht, A.; Rozenberg, G. 8 1977 On proving that certain languages are not ETOL. Zbl 0349.68034Ehrenfeucht, A.; Rozenberg, G. 8 1976 Gene assembly through cyclic graph decomposition. Zbl 1024.68039Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 8 2002 Application of games to some problems of mathematical logic. Zbl 0105.00901Ehrenfeucht, A. 8 1957 On total regulators generated by derivation relations. Zbl 0606.68074Bucher, W.; Ehrenfeucht, A.; Haussler, D. 8 1985 On the membership problem for regular DNLC grammars. Zbl 0602.68064Aalbersberg, Ijsbrand Jan; Rozenberg, G.; Ehrenfeucht, A. 7 1986 On theories categorical in power. Zbl 0105.00601Ehrenfeucht, A. 7 1957 A new method of proving theorems on chromatic index. Zbl 0553.05035Ehrenfeucht, A.; Faber, V.; Kierstead, H. A. 7 1984 Dynamic labeled 2-structures. Zbl 0829.68099Ehrenfeucht, A.; Rozenberg, G. 7 1994 Position heaps: a simple and dynamic text indexing data structure. Zbl 1216.68083Ehrenfeucht, Andrzej; McConnell, Ross M.; Osheim, Nissa; Woo, Sung-Whan 7 2011 On the dependence of functions on their variables. Zbl 0494.04003Ehrenfeucht, Andrzej; Kahn, Jeff; Maddux, Roger; Mycielski, Jan 6 1982 Conditions enforcing regularity of context-free languages. Zbl 0495.68068Ehrenfeucht, A.; Haussler, D.; Rozenberg, G. 6 1982 Patterns of micronuclear genes in ciliates. Zbl 1065.68541Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Rozenberg, Grzegorz 6 2002 Decomposing a transformation with an involution. Zbl 0389.04001Ehrenfeucht, Andrzej; Silberger, D. M. 6 1977 On a bound for the DOL sequence equivalence problem. Zbl 0456.68085Ehrenfeucht, A.; Rozenberg, G. 6 1980 A morphic representation of complements of recursively enumerable sets. Zbl 0491.68078Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K. 6 1981 Representations of finite lattices as partition lattices on finite sets. Zbl 0296.06002Ehrenfeucht, A.; Faber, V.; Fajtlowicz, S.; Mycielski, J. 6 1973 Practical decidability. Zbl 0329.02020Ehrenfeucht, Andrzej 6 1975 Universal and point universal terms. Zbl 0347.20035Ehrenfeucht, A.; Silberger, D. M. 6 1976 Computations in coordinated pair systems. Zbl 0642.68133Ehrenfeucht, A.; Hoogeboom, H. J.; Rozenberg, G. 6 1986 Forbidding and enforcing. Zbl 0969.68074Ehrenfeucht, Andrzej; Hoogeboom, Hendrik Jan; Rozenberg, Grzegorz; van Vugt, Nikè 6 1999 Forbidding–enforcing systems. Zbl 1023.68054Ehrenfeucht, A.; Rozenberg, G. 5 2003 Context-free text grammars. Zbl 0790.68061Ehrenfeucht, A.; ten Pas, P.; Rozenberg, G. 5 1994 Some problems on the universality of words in groups. Zbl 0388.20030Ehrenfeucht, A.; Fajtlowicz, S.; Malitz, J.; Mycielski, J. 5 1980 On the structure of polynomially bounded DOL systems. Zbl 0452.68075Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 5 1979 On basic properties of DOS systems and languages. Zbl 0469.68076Ehrenfeucht, A.; Rozenberg, G. 5 1980 A pseudorandom sequence – how random is it? Zbl 1279.94047Ehrenfeucht, Andrzej; Mycielski, Jan 5 1992 String searching. 2nd edition. Zbl 1387.68087Ehrenfeucht, Andrzej; McConnell, Ross M. 1 2018 Evolving reaction systems. Zbl 1371.68083Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 14 2017 Reaction systems: a model of computation inspired by the functioning of the living cell. Zbl 1395.68122Ehrenfeucht, Andrzej; Petre, Ion; Rozenberg, Grzegorz 14 2017 Zoom structures and reaction systems yield exploration systems. Zbl 1360.68463Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 12 2014 Reaction systems: a natural computing approach to the functioning of living cells. Zbl 1256.68071Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 13 2013 Minimal reaction systems. Zbl 1382.68070Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 22 2012 Stability and chaos in reaction systems. Zbl 1279.68094Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz; Brown, Allison Thompson 4 2012 Representing reaction systems by trees. Zbl 1353.68080Brijder, R.; Ehrenfeucht, A.; Rozenberg, G. 3 2012 Relevance of entities in reaction systems. Zbl 1367.68099Ehrenfeucht, Andrzej; Kleijn, Jetty; Koutny, Maciej; Rozenberg, Grzegorz 1 2012 A tour of reaction systems. Zbl 1252.68115Brijder, Robert; Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz 52 2011 Functions defined by reaction systems. Zbl 1213.68259Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz 26 2011 Reaction systems with duration. Zbl 1330.68068Brijder, Robert; Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 20 2011 Position heaps: a simple and dynamic text indexing data structure. Zbl 1216.68083Ehrenfeucht, Andrzej; McConnell, Ross M.; Osheim, Nissa; Woo, Sung-Whan 7 2011 Combinatorics of life and death for reaction systems. Zbl 1192.68458Ehrenfeucht, Andrzej; Main, Michael; Rozenberg, Grzegorz 18 2010 Reaction systems: a model of computation inspired by biochemistry. Zbl 1250.68108Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 4 2010 Introducing time in reaction systems. Zbl 1156.93306Ehrenfeucht, A.; Rozenberg, G. 32 2009 Contracted suffix trees: A simple and dynamic text indexing data structure. Zbl 1247.68066Ehrenfeucht, Andrzej; McConnell, Ross M.; Woo, Sung-Whan 1 2009 Andrzej Mostowski and foundational studies. Zbl 1134.03004 4 2008 Reaction systems. Zbl 1108.68056Ehrenfeucht, A.; Rozenberg, G. 88 2007 Events and modules in reaction systems. Zbl 1119.93011Ehrenfeucht, A.; Rozenberg, G. 25 2007 Pawlak, Zdzisław – life and work 1926–2006. Zbl 1120.01302Ehrenfeucht, Andrzej; Orłowska, Ewa; Peters, James F.; Rozenberg, Grzegorz; Skowron, Andrzej 3 2007 Covers from templates. Zbl 1093.68049Ehrenfeucht, A.; Rozenberg, G. 1 2006 Computation in living cells. Gene assembly in ciliates. Zbl 1069.68048Ehrenfeucht, A.; Harju, T.; Petre, I.; Prescott, D. M.; Rozenberg, G. 39 2004 Basic notions of reaction systems. Zbl 1117.68349Ehrenfeucht, A.; Rozenberg, G. 12 2004 Transitivity of local complementation and switching on graphs. Zbl 1033.05052Ehrenfeucht, Andrzej; Harju, Tero; Rozenberg, Grzegorz 1 2004 Formal systems for gene assembly in ciliates. Zbl 1063.68054Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 16 2003 Template-guided recombination for IES elimination and unscrambling of genes in stichotrichous ciliates. Zbl 1464.92175Prescott, David M.; Ehrenfeucht, Andrzej; Rozenberg, G. 12 2003 Forbidding–enforcing systems. Zbl 1023.68054Ehrenfeucht, A.; Rozenberg, G. 5 2003 Characterizing the micronuclear gene patterns in ciliates. Zbl 1001.68903Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Rozenberg, Grzegorz 12 2002 String and graph reduction systems for gene assembly in ciliates. Zbl 1007.68127Ehrenfeucht, Andrzej; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 12 2002 Gene assembly through cyclic graph decomposition. Zbl 1024.68039Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 8 2002 Patterns of micronuclear genes in ciliates. Zbl 1065.68541Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Rozenberg, Grzegorz 6 2002 Universal and simple operations for gene assembly in ciliates. Zbl 1007.68067Ehrenfeucht, Andrzej; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 12 2001 Sequences of languages in forbidding-enforcing families. Zbl 0992.68512Ehrenfeucht, A.; Hoogeboom, H. J.; Rozenberg, G.; van Vugt, N. 5 2001 Circularity and other invariants of gene assembly in ciliates. Zbl 1504.92087Ehrenfeucht, Andrzej; Petre, Ion; Prescott, David M.; Rozenberg, Grzegorz 3 2001 Complexity issues in switching of graphs. Zbl 0958.68133Ehrenfeucht, Andrzej; Hage, Jurriaan; Harju, Tero; Rozenberg, Grzegorz 5 2000 Pancyclicity in switching classes. Zbl 1338.68101Ehrenfeucht, Andrzej; Hage, Jurriaan; Harju, Tero; Rozenberg, Grzegorz 3 2000 The theory of 2-structures. A framework for decomposition and transformation of graphs. Zbl 0981.05002Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 57 1999 Forbidding and enforcing. Zbl 0969.68074Ehrenfeucht, Andrzej; Hoogeboom, Hendrik Jan; Rozenberg, Grzegorz; van Vugt, Nikè 6 1999 Permutations, parenthesis words, and Schröder numbers. Zbl 0956.05011Ehrenfeucht, A.; Harju, T.; ten Pas, P.; Rozenberg, G. 4 1998 On representing recursively enumerable languages by internal contextual languages. Zbl 0913.68117Ehrenfeucht, Andrzej; Păun, Gheorghe; Rozenberg, Grzegorz 2 1998 Invariants of inversive 2-structures on groups of labels. Zbl 0882.05119Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 3 1997 On representing RE languages by one-sided internal contextual languages. Zbl 0880.68073Ehrenfeucht, A.; Mateescu, A.; Păun, Gh.; Rozenberg, G.; Salomaa, A. 4 1996 Finite languages for the representation of finite graphs. Zbl 0846.68080Ehrenfeucht, Andrzej; Engelfriet, Joost; Rozenberg, Grzegorz 1 1996 The linear landscape of external contextual languages. Zbl 0858.68050Ehrenfeucht, Andrzej; Păun, Gheorghe; Rozenberg, Grzegorz 1 1996 Theory of 2-structures. Zbl 1412.68168Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 2 1995 Grammatical codes of trees and terminally coded grammars. Zbl 0827.68068Ehrenfeucht, Andrzej; Engelfriet, Joost; ten Pas, Paulien; Rozenberg, Grzegorz 1 1995 An \(O(n^ 2)\) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. Zbl 0797.68079Ehrenfeucht, Andrzej; Gabow, Harold N.; McConnell, Ross M.; Sullivan, Stephen J. 17 1994 Dynamic labeled 2-structures. Zbl 0829.68099Ehrenfeucht, A.; Rozenberg, G. 7 1994 Context-free text grammars. Zbl 0790.68061Ehrenfeucht, A.; ten Pas, P.; Rozenberg, G. 5 1994 A \(k\)-structure generalization of the theory of 2-structures. Zbl 0808.05089Ehrenfeucht, A.; McConnell, R. 5 1994 Incremental construction of 2-structures. Zbl 0796.05083Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 4 1994 Properties of grammatical codes of trees. Zbl 0795.68119Ehrenfeucht, A.; ten Pas, P.; Rozenberg, G. 2 1994 Efficient detection of quasiperiodicities in strings. Zbl 0804.68109Apostolico, Alberto; Ehrenfeucht, Andrzej 43 1993 T-structures, T-functions, and texts. Zbl 0783.68097Ehrenfeucht, A.; Rozenberg, G. 10 1993 Combinatorial properties of texts. Zbl 0803.68098Ehrenfeucht, A.; ten Pas, P.; Rozenberg, G. 4 1993 Permutable transformation semigroups. Zbl 0792.20060Ehrenfeucht, A.; Harju, T.; Rozenberg, G. 3 1993 An introduction to dynamic labeled 2-structures. Zbl 0925.68339Ehrenfeucht, A.; Rozenberg, G. 1 1993 Angular 2-structures. Zbl 0753.05069Ehrenfeucht, A.; Rozenberg, G. 8 1992 A pseudorandom sequence – how random is it? Zbl 1279.94047Ehrenfeucht, Andrzej; Mycielski, Jan 5 1992 Grammatical codes of trees. Zbl 0737.68050Ehrenfeucht, A.; Rozenberg, G. 4 1991 Primitivity is hereditary for 2-structures. Zbl 0701.05053Ehrenfeucht, A.; Rozenberg, G. 62 1990 Partial (set) 2-structures. II: State spaces of concurrent systems. Zbl 0696.68083Ehrenfeucht, A.; Rozenberg, G. 42 1990 Theory of 2-structures. I: Clans, basic subclasses, and morphisms. Zbl 0701.05051Ehrenfeucht, A.; Rozenberg, G. 41 1990 Partial (set) 2-structures. I: Basic notions and the representation problems. Zbl 0696.68082Ehrenfeucht, A.; Rozenberg, G. 35 1990 Theory of 2-structures. II: Representation through labeled tree families. Zbl 0701.05052Ehrenfeucht, A.; Rozenberg, G. 31 1990 Learnability and the Vapnik-Chervonenkis dimension. Zbl 0697.68079Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. 291 1989 A general lower bound on the number of examples needed for learning. Zbl 0679.68158Ehrenfeucht, Andrzej; Haussler, David; Kearns, Michael; Valiant, Leslie 67 1989 Learning decision trees from random examples. Zbl 0679.68157Ehrenfeucht, Andrzej; Haussler, David 21 1989 Average sizes of suffix trees and DAWGs. Zbl 0679.68031Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David 12 1989 A new distance metric on strings computable in linear time. Zbl 0644.68114Ehrenfeucht, A.; Haussler, D. 3 1988 Occam’s razor. Zbl 0653.68084Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. 132 1987 Complete inverted files for efficient text retrieval and analysis. Zbl 1433.68118Blumer, A.; Blumer, J.; Haussler, D.; McConnell, R.; Ehrenfeucht, A. 33 1987 Quasi-monotonic sequences: Theory, algorithms and applications. Zbl 0692.06011Ehrenfeucht, Andrzej; Haemer, Jeffrey; Haussler, David 2 1987 On the structure of dependence graphs. Zbl 0642.68031Ehrenfeucht, A.; Rozenberg, G. 1 1987 Each regular code is included in a maximal regular code. Zbl 0609.68053Ehrenfeucht, A.; Rozenberg, G. 29 1986 On the membership problem for regular DNLC grammars. Zbl 0602.68064Aalbersberg, Ijsbrand Jan; Rozenberg, G.; Ehrenfeucht, A. 7 1986 Computations in coordinated pair systems. Zbl 0642.68133Ehrenfeucht, A.; Hoogeboom, H. J.; Rozenberg, G. 6 1986 On the active and full use of memory in right-boundary grammars and push- down automata. Zbl 0638.68075Ehrenfeucht, A.; Hoogeboom, H. J.; Rozenberg, G. 3 1986 Coordinated pair systems. I: Dyck words and classical pumping. Zbl 0639.68075Ehrenfeucht, A.; Hoogeboom, H. J.; Rozenberg, G. 3 1986 Addendum to the paper ”On the dependence of functions on their variables”. Zbl 0588.04009Ehrenfeucht, A.; Kahn, J.; Maddux, R.; Mycielski, J. 1 1986 The smallest automaton recognizing the subwords of a text. Zbl 0574.68070Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M. T.; Seiferas, J. 75 1985 On total regulators generated by derivation relations. Zbl 0606.68074Bucher, W.; Ehrenfeucht, A.; Haussler, D. 8 1985 On total regulators generated by derivation relations. Zbl 0571.68056Bucher, W.; Ehrenfeucht, A.; Haussler, D. 3 1985 A morphic representation of EOL languages and other ETOL languages. Zbl 0579.68046Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K. 3 1985 Strong iterative pairs and the regularity of context-free languages. Zbl 0601.68053Ehrenfeucht, A.; Rozenberg, G. 1 1985 Adding global forbidding context to context-free grammars. Zbl 0603.68078Ehrenfeucht, A.; Kleijn, H. C. M.; Rozenberg, G. 1 1985 Building the minimal DFA for the set of all subwords of a word on-line in linear time. Zbl 0554.68058Blumer, A.; Blumer, J.; Ehrenfeucht, A.; Haussler, D.; McConnell, R. 21 1984 On regularity of languages generated by copying systems. Zbl 0549.68075Ehrenfeucht, A.; Rozenberg, G. 13 1984 Restrictions on NLC graph grammars. Zbl 0566.68062Ehrenfeucht, Andrzej; Main, Michael G.; Rozenberg, Grzegorz 11 1984 A new method of proving theorems on chromatic index. Zbl 0553.05035Ehrenfeucht, A.; Faber, V.; Kierstead, H. A. 7 1984 An easy proof of Greibach normal form. Zbl 0589.68054Ehrenfeucht, Andrzej; Rozenberg, Grzegorz 4 1984 On inherently ambiguous E0L languages. Zbl 0544.68051Ehrenfeucht, A.; Rozenberg, G.; Verraedt, R. 2 1984 On DOS languages and DOS mappings. Zbl 0535.68034Ehrenfeucht, Andrzej; Haussler, David; Rozenberg, Grzegorz; Zeiger, Paul 1 1984 On regularity of context-free languages. Zbl 0553.68044Ehrenfeucht, A.; Haussler, D.; Rozenberg, G. 48 1983 Repetition of subwords in DOL languages. Zbl 0549.68076Ehrenfeucht, A.; Rozenberg, G. 18 1983 On binary equality sets and a solution to the test set conjecture in the binary case. Zbl 0523.68066Ehrenfeucht, A.; Karhumäki, Juhani; Rozenberg, G. 14 1983 On the subword complexity of m-free DOL languages. Zbl 0526.68067Ehrenfeucht, A.; Rozenberg, G. 5 1983 On the subword complexity of locally catenative DOL languages. Zbl 0501.68038Ehrenfeucht, A.; Rozenberg, G. 4 1983 On the size of the alphabet and the subword complexity of square-free DOL languages. Zbl 0512.68058Ehrenfeucht, A.; Rozenberg, G. 4 1983 ...and 90 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 2,167 Authors 123 Rozenberg, Grzegorz 101 Ehrenfeucht, Andrzej 40 Harju, Tero 24 Anthony, Martin H. G. 24 Honkala, Juha 22 Hoogeboom, Hendrik Jan 20 Karhumaki, Juhani 19 Blanchet-Sadri, Francine 19 Ille, Pierre 18 Haussler, David 18 Inenaga, Shunsuke 17 Crochemore, Maxime 17 Kleijn, Jetty 17 Petre, Ion 17 Salomaa, Arto Kustaa 16 Brijder, Robert 14 Boros, Endre 14 Boudabbous, Youssef 14 Chatterjee, Krishnendu 14 Holub, Štěpán 14 Koutny, Maciej 14 Ratsaby, Joel 14 Rytter, Wojciech 14 Servedio, Rocco A. 13 Grytczuk, Jarosław 13 Nowotka, Dirk 13 Takeda, Masayuki 12 Engelfriet, Joost 12 Gurvich, Vladimir A. 12 Long, Philip M. 12 Păun, Gheorghe 12 Radoszewski, Jakub 11 Belkhechine, Houmem 11 Boussairi, Abderrahim 11 Bshouty, Nader H. 11 Holzer, Markus 11 Iliopoulos, Costas S. 11 Makino, Kazuhisa 11 Shelah, Saharon 10 Currie, James D. 10 Gruber, Hermann 10 Main, Michael G. 10 Mignosi, Filippo 10 Ochem, Pascal 10 Randour, Mickael 10 Raskin, Jean-François 10 Restivo, Antonio 10 Richomme, Gwénaël 10 Shallit, Jeffrey Outlaw 10 Shinohara, Ayumi 10 Varricchio, Stefano 9 Bannai, Hideo 9 Boudabbous, Imed 9 Darondeau, Philippe 9 de Luca, Aldo 9 Halava, Vesa 9 Hellmuth, Marc 9 McConnell, Ross M. 9 Néraud, Jean 9 Pietkiewicz-Koutny, Marta 9 Reidenbach, Daniel 8 Apostolico, Alberto 8 Barbuti, Roberto 8 Bartlett, Peter L. 8 Elbassioni, Khaled M. 8 Fernau, Henning 8 Geffert, Viliam 8 Jonoska, Nataša 8 Kociumaka, Tomasz 8 Mercaş, Robert George 8 Milazzo, Paolo 8 Mycielski, Jan 8 Rampersad, Narad 8 Shur, Arseny M. 8 Wood, Derick 8 Zamboni, Luca Quardo 7 Alhazov, Artiom 7 Blum, Avrim L. 7 Bouyer, Patricia 7 Bruyère, Véronique 7 Bucher, Walter 7 Cassaigne, Julien 7 Chergui, Brahim 7 Culik, Karel II 7 Genova, Daniela 7 Gori, Roberta 7 Hanneke, Steve 7 Ivanov, Sergiu 7 Lecroq, Thierry 7 Manea, Florin 7 Manzoni, Luca E. 7 Markey, Nicolas 7 Pissis, Solon P. 7 Porreca, Antonio E. 7 Rabinovich, Alexander 7 Ruohonen, Keijo 7 Schmid, Markus L. 7 Simon, Hans-Ulrich 7 Stadler, Peter F. 7 ten Pas, Paulien ...and 2,067 more Authors all top 5 Cited in 234 Serials 386 Theoretical Computer Science 97 Discrete Applied Mathematics 90 Journal of Computer and System Sciences 79 Information and Computation 66 Information Processing Letters 53 Discrete Mathematics 51 International Journal of Foundations of Computer Science 47 Acta Informatica 31 Annals of Pure and Applied Logic 28 Machine Learning 26 RAIRO. Informatique Théorique et Applications 22 Algorithmica 21 Artificial Intelligence 21 RAIRO. Theoretical Informatics and Applications 20 Journal of Combinatorial Theory. Series A 20 Journal of Discrete Algorithms 17 Algebra Universalis 17 European Journal of Combinatorics 15 International Journal of Computer Mathematics 14 Israel Journal of Mathematics 13 Archiv für Mathematische Logik und Grundlagenforschung 13 The Journal of Symbolic Logic 13 Transactions of the American Mathematical Society 13 International Journal of Algebra and Computation 13 RAIRO. Theoretical Informatics and Applications 12 Journal of Algebra 12 Semigroup Forum 12 Archive for Mathematical Logic 11 Proceedings of the American Mathematical Society 11 Studia Logica 11 Discrete & Computational Geometry 11 The Electronic Journal of Combinatorics 11 Journal of Membrane Computing 9 Information Sciences 9 Mathematical Systems Theory 9 Advances in Applied Mathematics 9 Graphs and Combinatorics 9 Theory of Computing Systems 9 Comptes Rendus. Mathématique. Académie des Sciences, Paris 9 Natural Computing 7 Notre Dame Journal of Formal Logic 7 RAIRO, Informatique Théorique 7 Combinatorica 7 Neural Computation 6 Mathematical Notes 6 SIAM Journal on Computing 6 Journal of Complexity 6 New Generation Computing 6 Journal of Machine Learning Research (JMLR) 5 Algebra and Logic 5 Siberian Mathematical Journal 5 SIAM Journal on Discrete Mathematics 5 Random Structures & Algorithms 5 Linear Algebra and its Applications 5 Combinatorics, Probability and Computing 5 Journal of Mathematical Sciences (New York) 5 Mathematical Logic Quarterly (MLQ) 5 Fundamenta Informaticae 4 The Annals of Statistics 4 Applied Mathematics and Computation 4 Order 4 Journal of Symbolic Computation 4 European Journal of Operational Research 4 Journal of Multiple-Valued Logic and Soft Computing 4 Contributions to Discrete Mathematics 4 Logical Methods in Computer Science 4 Discrete Mathematics, Algorithms and Applications 4 Computer Science Review 4 Journal of Logical and Algebraic Methods in Programming 3 Journal of Mathematical Biology 3 International Journal of Computer & Information Sciences 3 Journal of Combinatorial Theory. Series B 3 Journal of Graph Theory 3 Journal of Mathematical Psychology 3 Kybernetika 3 Synthese 3 Statistics & Probability Letters 3 Operations Research Letters 3 Pattern Recognition 3 Annals of Mathematics and Artificial Intelligence 3 Quantum Information Processing 2 Acta Mathematica Academiae Scientiarum Hungaricae 2 Computers & Mathematics with Applications 2 International Journal of Theoretical Physics 2 Journal of Mathematical Analysis and Applications 2 International Journal of Game Theory 2 Journal of Approximation Theory 2 Journal of Number Theory 2 Journal of Philosophical Logic 2 Journal of Soviet Mathematics 2 Manuscripta Mathematica 2 Ergodic Theory and Dynamical Systems 2 Mathematical Social Sciences 2 Optimization 2 Journal of Computer Science and Technology 2 Mathematical and Computer Modelling 2 Formal Aspects of Computing 2 Neural Networks 2 JETAI. Journal of Experimental & Theoretical Artificial Intelligence 2 MSCS. Mathematical Structures in Computer Science ...and 134 more Serials all top 5 Cited in 45 Fields 1,476 Computer science (68-XX) 307 Mathematical logic and foundations (03-XX) 295 Combinatorics (05-XX) 132 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 127 Group theory and generalizations (20-XX) 78 Biology and other natural sciences (92-XX) 60 Information and communication theory, circuits (94-XX) 55 Order, lattices, ordered algebraic structures (06-XX) 54 Statistics (62-XX) 51 Operations research, mathematical programming (90-XX) 32 Number theory (11-XX) 29 General algebraic systems (08-XX) 25 Probability theory and stochastic processes (60-XX) 21 Convex and discrete geometry (52-XX) 17 Dynamical systems and ergodic theory (37-XX) 16 Linear and multilinear algebra; matrix theory (15-XX) 15 Numerical analysis (65-XX) 14 History and biography (01-XX) 13 Systems theory; control (93-XX) 8 Algebraic geometry (14-XX) 8 Associative rings and algebras (16-XX) 8 Category theory; homological algebra (18-XX) 7 Quantum theory (81-XX) 5 Approximations and expansions (41-XX) 5 Geometry (51-XX) 5 General topology (54-XX) 4 Functional analysis (46-XX) 3 General and overarching topics; collections (00-XX) 3 Field theory and polynomials (12-XX) 3 Commutative algebra (13-XX) 3 Real functions (26-XX) 3 Measure and integration (28-XX) 3 Manifolds and cell complexes (57-XX) 2 Nonassociative rings and algebras (17-XX) 2 Fluid mechanics (76-XX) 1 Topological groups, Lie groups (22-XX) 1 Difference and functional equations (39-XX) 1 Operator theory (47-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Differential geometry (53-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Mechanics of deformable solids (74-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Geophysics (86-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.