Andrzej Ehrenfeucht

According to our database, Andrzej Ehrenfeucht authored at least 192 papers between 1957 and 2017.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2017

Evolving reaction systems.

Andrzej Ehrenfeucht, Jetty Kleijn, Maciej Koutny, Grzegorz Rozenberg

Theor. Comput. Sci., 2017

Reaction Systems: A Model of Computation Inspired by the Functioning of the Living Cell.

Andrzej Ehrenfeucht, Ion Petre, Grzegorz Rozenberg

Proceedings of the Role of Theory in Computer Science, 2017

2015

Standard and ordered zoom structures.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 2015

2014

Zoom Structures and reaction Systems Yield Exploration Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Int. J. Found. Comput. Sci., 2014

2013

Processes Inspired by the Functioning of Living Cells: Natural Computing Approach - (Abstract).

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Unconventional Computation and Natural Computation, 2013

Processes Inspired by the Functioning of Living Cells: Natural Computing Approach.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

2012

Minimal Reaction Systems.

Andrzej Ehrenfeucht, Jetty Kleijn, Maciej Koutny, Grzegorz Rozenberg

Trans. Comp. Sys. Biology, 2012

Stability and Chaos in reaction Systems.

Andrzej Ehrenfeucht, Michael G. Main, Grzegorz Rozenberg, Allison Thompson Brown

Int. J. Found. Comput. Sci., 2012

A Formal Framework for Processes Inspired by the Functioning of Living Cells.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Implementation and Application of Automata, 2012

Relevance of Entities in Reaction Systems.

Andrzej Ehrenfeucht, Jetty Kleijn, Maciej Koutny, Grzegorz Rozenberg

Proceedings of the Languages Alive, 2012

Representing Reaction Systems by Trees.

Robert Brijder, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Computation, Physics and Beyond, 2012

2011

Position heaps: A simple and dynamic text indexing data structure.

Andrzej Ehrenfeucht, Ross M. McConnell, Nissa Osheim, Sung-Whan Woo

J. Discrete Algorithms, 2011

Functions Defined by Reaction Systems.

Andrzej Ehrenfeucht, Michael G. Main, Grzegorz Rozenberg

Int. J. Found. Comput. Sci., 2011

A Tour of reaction Systems.

Robert Brijder, Andrzej Ehrenfeucht, Michael G. Main, Grzegorz Rozenberg

Int. J. Found. Comput. Sci., 2011

A Formal Framework for Bioprocesses in Living Cells.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Unconventional Computation - 10th International Conference, 2011

Reaction Systems with Duration.

Robert Brijder, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Computation, 2011

2010

Combinatorics of Life and Death for Reaction Systems.

Andrzej Ehrenfeucht, Michael G. Main, Grzegorz Rozenberg

Int. J. Found. Comput. Sci., 2010

Reaction Systems: a Formal Framework for Processes Based on Biochemical Interactions.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Electron. Commun. Eur. Assoc. Softw. Sci. Technol., 2010

A Note on Causalities in Reaction Systems.

Robert Brijder, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Electron. Commun. Eur. Assoc. Softw. Sci. Technol., 2010

Reaction Systems: A Model of Computation Inspired by Biochemistry.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009

Introducing time in reaction systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 2009

Computational Nature of Processes Induced by Biochemical Reactions.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Membrane Computing, 10th International Workshop, 2009

Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure.

Andrzej Ehrenfeucht, Ross M. McConnell, Sung-Whan Woo

Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

2008

Modeling Interactions between Biochemical Reactions.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Applications and Theory of Petri Nets, 29th International Conference, 2008

2007

Events and modules in reaction systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 2007

Reaction Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Fundam. Informaticae, 2007

Finite metrics in switching classes.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Discret. Appl. Math., 2007

Biochemical Reactions as Computations.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Computation and Logic in the Real World, 2007

2006

Covers from Templates.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Int. J. Found. Comput. Sci., 2006

The Embedding Problem for Switching Classes of Graphs.

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Fundam. Informaticae, 2006

Zdzislaw Pawlak (1926-2006).

Andrzej Ehrenfeucht, James F. Peters, Grzegorz Rozenberg, Andrzej Skowron

Bull. EATCS, 2006

Embedding linear orders in grids.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Acta Informatica, 2006

Computational Nature of Biochemical Reactions.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2004

String Searching.

Andrzej Ehrenfeucht, Ross M. McConnell

Proceedings of the Handbook of Data Structures and Applications., 2004

Transitivity of local complementation and switching on graphs.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Discret. Math., 2004

Embedding in Switching Classes with Skew Gains.

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Proceedings of the Graph Transformations, Second International Conference, 2004

Basic Notions of Reaction Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Developments in Language Theory, 2004

2003

Forbidding-enforcing systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 2003

Formal systems for gene assembly in ciliates.

Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David M. Prescott, Grzegorz Rozenberg

Theor. Comput. Sci., 2003

2002

Gene assembly through cyclic graph decomposition.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Theor. Comput. Sci., 2002

Characterizing the Micronuclear Gene Patterns in Ciliates.

Andrzej Ehrenfeucht, Tero Harju, Ion Petre, Grzegorz Rozenberg

Theory Comput. Syst., 2002

String and Graph Reduction Systems for Gene Assembly in Ciliates.

Andrzej Ehrenfeucht, Ion Petre, David M. Prescott, Grzegorz Rozenberg

Math. Struct. Comput. Sci., 2002

2001

Sequences of languages in forbidding-enforcing families.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg, Nike van Vugt

Soft Comput., 2001

Patterns of Micronuclear Genes in ciliates.

Andrzej Ehrenfeucht, Tero Harju, Ion Petre, Grzegorz Rozenberg

Proceedings of the DNA Computing, 7th International Workshop on DNA-Based Computers, 2001

Universal and simple operations for gene assembly in ciliates.

Andrzej Ehrenfeucht, Ion Petre, David M. Prescott, Grzegorz Rozenberg

Proceedings of the Where Mathematics, 2001

Circularity and Other Invariants of Gene Assembly in Ciliates.

Andrzej Ehrenfeucht, Ion Petre, David M. Prescott, Grzegorz Rozenberg

Proceedings of the Words, Semigroups, and Transductions, 2001

2000

Pancyclicity in switching classes.

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Inf. Process. Lett., 2000

1999

Forbidding and enforcing.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg, Nike van Vugt

Proceedings of the DNA Based Computers, 1999

The Theory of 2-Structures - A Framework for Decomposition and Transformation of Graphs.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

World Scientific, ISBN: 978-981-02-4042-4, 1999

1998

On Representing Recursively Enumerable Languages by Internal Contextual Languages.

Andrzej Ehrenfeucht, Gheorghe Paun, Grzegorz Rozenberg

Theor. Comput. Sci., 1998

Permutations, parenthesis words, and Schröder numbers.

Andrzej Ehrenfeucht, Tero Harju, Paulien ten Pas, Grzegorz Rozenberg

Discret. Math., 1998

Complexity Issues in Switching of Graphs.

Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

Proceedings of the Theory and Application of Graph Transformations, 1998

1997

Contextual Grammars and Formal Languages.

Andrzej Ehrenfeucht, Gheorghe Paun, Grzegorz Rozenberg

Proceedings of the Handbook of Formal Languages, 1997

Invariants of Inversive 2-Structures on Groups of Labels.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Math. Struct. Comput. Sci., 1997

Semantics of Nonsequential Tree-Based Computation Schemes.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa

Fundam. Informaticae, 1997

2-Structures - A Framework For Decomposition And Transformation Of Graphs.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Proceedings of the Handbook of Graph Grammars and Computing by Graph Transformations, 1997

1996

A Note on Binary Grammatical Codes of Trees.

Andrzej Ehrenfeucht, Paulien ten Pas, Grzegorz Rozenberg

Theor. Comput. Sci., 1996

Finite Languages for the Representation of Finite Graphs.

Andrzej Ehrenfeucht, Joost Engelfriet, Grzegorz Rozenberg

J. Comput. Syst. Sci., 1996

On Representing RE Languages by One-Sided Internal Contextual Languages.

Andrzej Ehrenfeucht, Alexandru Mateescu, Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa

Acta Cybern., 1996

The Linear Landscape of External Contextual Languages.

Andrzej Ehrenfeucht, Gheorghe Paun, Grzegorz Rozenberg

Acta Informatica, 1996

A browsing system based on mul timedia cohesion.

Jim Jungbauer, Patricia Baggett, Andrzej Ehrenfeucht

Proceedings of WebNet 96, 1996

Forbidding, Enforcing.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, 1996

1995

Grammatical Codes of Trees and Terminally Coded Grammars.

Andrzej Ehrenfeucht, Joost Engelfriet, Paulien ten Pas, Grzegorz Rozenberg

Fundam. Informaticae, 1995

The size of k-pseudotrees.

Emanuel Knill, Andrzej Ehrenfeucht, David Haussler

Discret. Math., 1995

Theory of 2-Structures.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994

Combinatorial Properties of Dependence Graphs

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

Inf. Comput., November, 1994

Properties of Grammatical Codes of Trees.

Andrzej Ehrenfeucht, Paulien ten Pas, Grzegorz Rozenberg

Theor. Comput. Sci., 1994

A k-Structure Generalization of the Theory of 2-Structures.

Andrzej Ehrenfeucht, Ross M. McConnell

Theor. Comput. Sci., 1994

Clans and Regions in 2-Structures.

André H. Deutz, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1994

Hyperedge Channels are Abelian.

André H. Deutz, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1994

Semantics of Trees.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Kai Salomaa

Math. Syst. Theory, 1994

Dynamic Labeled 2-Structures.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Math. Struct. Comput. Sci., 1994

An O(n²) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs.

Andrzej Ehrenfeucht, Harold N. Gabow, Ross M. McConnell, Stephen J. Sullivan

J. Algorithms, 1994

Square Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Fundam. Informaticae, 1994

Incremental construction of 2-structures.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Discret. Math., 1994

Context-free Text Grammars.

Andrzej Ehrenfeucht, Paulien ten Pas, Grzegorz Rozenberg

Acta Informatica, 1994

Group Based Graph Transformations and Hierarchical Representations of Graphs.

Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

Dynamic Labeled 2-Structures with Variable Domains.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Results and Trends in Theoretical Computer Science, 1994

Normal Forms for Contextual Grammars.

Andrzej Ehrenfeucht, Gheorghe Paun, Grzegorz Rozenberg

Proceedings of the Mathematical Aspects of Natural and Formal Languages, 1994

1993

T-structures, T-functions, and texts.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1993

Efficient Detection of Quasiperiodicities in Strings.

Alberto Apostolico, Andrzej Ehrenfeucht

Theor. Comput. Sci., 1993

Combinatorial Properties of Texts.

Andrzej Ehrenfeucht, Paulien ten Pas, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1993

On the Structure of Recognizable Languages of Dependence Graphs.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1993

An Introduction to Dynamic Labled 2-Structures.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

An Introduction to Context-free Text Grammars.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Paulien ten Pas, Grzegorz Rozenberg

Proceedings of the Developments in Language Theory, 1993

1992

Angular 2-Structures.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1992

A representation of partial Boolean algebras.

Andrzej Ehrenfeucht, Marek W. Zawadowski

Fundam. Informaticae, 1992

1991

Grammatical codes of trees.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Discret. Appl. Math., 1991

1990

Primitivity is Hereditary for 2-Structures.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1990

Theory of 2-Structures, Part II: Representation Through Labeled Tree Families.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1990

Theory of 2-Structures, Part I: Clans, Basic Subclasses, and Morphisms.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1990

A Characterization of Set Representable Labeled Partial 2-Structures Through Decompositions.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Acta Informatica, 1990

Partial (Set) 2-Structures. Part II: State Spaces of Concurrent Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Acta Informatica, 1990

Partial (Set) 2-Structures. Part I: Basic Notions and the Representation Problem.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Acta Informatica, 1990

1989

A General Lower Bound on the Number of Examples Needed for Learning

Andrzej Ehrenfeucht, David Haussler, Michael J. Kearns, Leslie G. Valiant

Inf. Comput., September, 1989

Learning Decision Trees from Random Examples

Andrzej Ehrenfeucht, David Haussler

Inf. Comput., September, 1989

Clans and the Complexity of Dependence graphs.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the A Perspective in Theoretical Computer Science, 1989

Learnability and the Vapnik-Chervonenkis dimension.

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth

J. ACM, 1989

Average sizes of suffix trees and DAWGs.

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler

Discret. Appl. Math., 1989

1988

A new distance metric on strings computable in linear time.

Andrzej Ehrenfeucht, David Haussler

Discret. Appl. Math., 1988

Recording the Use of Memory in Right-Boundary Grammars and Push-Down Automata.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

Acta Informatica, 1988

Textual and visual access to a computer by people who know nothing about it.

Patricia Baggett, Andrzej Ehrenfeucht

Proceedings of the 6th Annual International Conference on Systems Documentation, 1988

1987

Complete inverted files for efficient text retrieval and analysis.

Anselm Blumer, J. Blumer, David Haussler, Ross M. McConnell, Andrzej Ehrenfeucht

J. ACM, 1987

Occam's Razor.

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth

Inf. Process. Lett., 1987

1986

On the Active and Full Use of Memory in Right-Boundary Grammars and Push-Down Automata.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

Theor. Comput. Sci., 1986

Addendum to the paper "On the dependence of functions on their variables".

Andrzej Ehrenfeucht, Jeff Kahn, Roger D. Maddux, Jan Mycielski

J. Comb. Theory, Ser. A, 1986

Each Regular Code Is Included in A Maximal Regular Code.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1986

Coordinated Pair Systems; Part II: Sparse Structure of Dyck Words and Ogden's Lemma.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1986

Coordinated Pair Systems; Part I: Dyck Works and Classical Pumping.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1986

On the membership problem for regular DNLC grammars.

IJsbrand Jan Aalbersberg, Grzegorz Rozenberg, Andrzej Ehrenfeucht

Discret. Appl. Math., 1986

Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract)

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985

Adding Global Forbidding Context to Context-Free Grammars.

Andrzej Ehrenfeucht, H. C. M. Kleijn, Grzegorz Rozenberg

Theor. Comput. Sci., 1985

On Total Regulators Generated by Derivation Relations.

Walter Bucher, Andrzej Ehrenfeucht, David Haussler

Theor. Comput. Sci., 1985

The Smallest Automaton Recognizing the Subwords of a Text.

Anselm Blumer, J. Blumer, David Haussler, Andrzej Ehrenfeucht, M. T. Chen, Joel I. Seiferas

Theor. Comput. Sci., 1985

A Combinatorial Property of EOL Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, R. Verraedt

Math. Syst. Theory, 1985

Strong Iterative Pairs and The Regularity of Context-Free Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1985

A morphic representation of EOL languages and other ETOL languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Keijo Ruohonen

Discret. Appl. Math., 1985

On coordinated rewriting.

Andrzej Ehrenfeucht, Hendrik Jan Hoogeboom, Grzegorz Rozenberg

Proceedings of the Fundamentals of Computation Theory, 1985

1984

An Easy Proof of Greibach Normal Form

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Control., December, 1984

On Inherently Ambiguous E0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, R. Verraedt

Theor. Comput. Sci., 1984

Restrictions on NLC Graph Grammars.

Andrzej Ehrenfeucht, Michael G. Main, Grzegorz Rozenberg

Theor. Comput. Sci., 1984

On Ambiguity in Dos Systems.

Andrzej Ehrenfeucht, David Haussler, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1984

A new method of proving theorems on chromatic index.

Andrzej Ehrenfeucht, Vance Faber, Hal A. Kierstead

Discret. Math., 1984

On regularity of languages generated by copying systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Discret. Appl. Math., 1984

Building a Complete Inverted File for a Set of Text Files in Linear Time

Anselm Blumer, J. Blumer, Andrzej Ehrenfeucht, David Haussler, Ross M. McConnell

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Building the Minimal DFA for the Set of all Subwords of a Word On-line in Linear Time.

Anselm Blumer, J. Blumer, Andrzej Ehrenfeucht, David Haussler, Ross M. McConnell

Proceedings of the Automata, 1984

1983

On Regularity of Context-Free Languages.

Andrzej Ehrenfeucht, David Haussler, Grzegorz Rozenberg

Theor. Comput. Sci., 1983

Context Free Normal Systems and ETOL Systems.

Andrzej Ehrenfeucht, Joost Engelfriet, Grzegorz Rozenberg

J. Comput. Syst. Sci., 1983

On the Separating Power of Eol Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1983

On the Subword Complexity of m-Free D0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1983

On the Subword Complexity of Locally Catenative D0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1983

Repetition of Subwords in DOL Languages

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Control., 1983

Linear size finite automata for the set of all subwords of a word - an outline of results.

Anselm Blumer, J. Blumer, Andrzej Ehrenfeucht, David Haussler, Ross M. McConnell

Bull. EATCS, 1983

1982

Representation Theorems Using DOS Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1982

The (Generalized) Post Correspondence Problem with Lists Consisting of two Words is Decidable.

Andrzej Ehrenfeucht, Juhani Karhumäki, Grzegorz Rozenberg

Theor. Comput. Sci., 1982

On the Dependence of Functions on Their Variables.

Andrzej Ehrenfeucht, Jeff Kahn, Roger D. Maddux, Jan Mycielski

J. Comb. Theory, Ser. A, 1982

On Subword Complexities of Homomorphic Images of Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1982

Basic formulas and languages: PART II.Applications to E0L systems and forms.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, R. Verraedt

Discret. Appl. Math., 1982

Compositional complexity of Boolean functions.

Harold Abelson, Andrzej Ehrenfeucht, James Fickett, Jan Mycielski

Discret. Appl. Math., 1982

Repetitions in Homomorphisms and Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Automata, 1982

Conditions Enforcing Regularity of Context-Free Languages.

Andrzej Ehrenfeucht, David Haussler, Grzegorz Rozenberg

Proceedings of the Automata, 1982

1981

On the Subword Complexity of Square-Free D0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1981

On ET0L Systems with Finite Tree-Rank.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Dirk Vermeir

SIAM J. Comput., 1981

Pumping Lemmas for Regular Sets.

Andrzej Ehrenfeucht, Rohit Parikh, Grzegorz Rozenberg

SIAM J. Comput., 1981

A Morphic Representation of Complements of Recursively Enumerable Sets.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Keijo Ruohonen

J. ACM, 1981

FPOL Systems Generating Counting Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1981

On the Subword Complexity of D0L Languages with a Constant Distribution.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1981

Basic formulas and languages Part I. The theory.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, R. Verraedt

Discret. Appl. Math., 1981

On the Subword Complexity and Square-Freeness of Formal Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Theoretical Computer Science, 1981

On the (Generalized) Post Correspondence Problem with Lists of Length 2.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Automata, 1981

1980

On Basic Properties of DOS Systems and Languages

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Control., November, 1980

Continuous Grammars

Andrzej Ehrenfeucht, Hermann A. Maurer, Grzegorz Rozenberg

Inf. Control., July, 1980

On a Bound for the D0L Sequence Equivalence Problem.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1980

On Ambiguity in E0L Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1980

Every Two Equivalent D0L Systems have a Regular True Envelope.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1980

The Sequence Equivalence Problem is Decidable for 0S Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

J. ACM, 1980

On the Emptiness of the Intersection of Two D0S Languages Problem.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1980

Many-to-one simulation in E0L forms is decidable.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, R. Verraedt

Discret. Appl. Math., 1980

DOS Systems and Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Automata, 1980

1979

On k-Stable Functions.

Andrzej Ehrenfeucht, Jan Mycielski

J. Comb. Theory, Ser. A, 1979

On ET0L Systems with Rank.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Dirk Vermeir

J. Comput. Syst. Sci., 1979

Finding a Homomorphism Between Two Words is NP-Complete.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1979

An Observation on Scattered Grammars.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1979

Periodicity and unbordered segments of words.

Andrzej Ehrenfeucht, D. M. Silberger

Discret. Math., 1979

1978

Simplifications of Homomorphisms

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Control., September, 1978

Elementary Homomorphisms and a Solution of the D0L Sequence Equivalence Problem.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1978

E0L Languages are not Codings of FP0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Theor. Comput. Sci., 1978

On the Structure of Derivations in Deterministic ET0L Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

J. Comput. Syst. Sci., 1978

A note on DOL length sets.

Andrzej Ehrenfeucht, Juhani Karhumäki, Grzegorz Rozenberg

Discret. Math., 1978

1977

On Some Context Free Languages That Are Not Deterministic ETOL Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1977

1976

A Relationship between ET0L and EDT0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg, Sven Skyum

Theor. Comput. Sci., 1976

Complexity Measures for Regular Expressions.

Andrzej Ehrenfeucht, H. Paul Zeiger

J. Comput. Syst. Sci., 1976

On the number of subwords of everywhere growing DTOL languages.

Andrzej Ehrenfeucht, K. P. Lee, Grzegorz Rozenberg

Discret. Math., 1976

On Proving that Certain Languages are not ETOL.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Acta Informatica, 1976

1975

Subword Complexities of Various Classes of Deterministic Developmental Languages without Interactions.

Andrzej Ehrenfeucht, K. P. Lee, Grzegorz Rozenberg

Theor. Comput. Sci., 1975

Practical Decidability.

Andrzej Ehrenfeucht

J. Comput. Syst. Sci., 1975

A Pumping Theorem for Deterministic Etol Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

RAIRO Theor. Informatics Appl., 1975

Subword complexities of various classes of deterministic developmental languages with interactions.

Andrzej Ehrenfeucht, K. P. Lee, Grzegorz Rozenberg

Int. J. Parallel Program., 1975

On the (Combinatorial) Structure of L Languages without Interactions

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On (Un)predictability of Formal Languages (Extended Abstract)

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On Θ-Determined E0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Automata, Languages, Development: At the crossroads of biology, mathematics and computer science, result of an international conference held at Noordwijkerhout, The Netherlands, March 31, 1975

On Inverse Homomorphic Images of Deterministic ET0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Automata, Languages, Development: At the crossroads of biology, mathematics and computer science, result of an international conference held at Noordwijkerhout, The Netherlands, March 31, 1975

1974

The Number of Occurrences of Letters Versus Their Distribution in Some E0L Languages

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Control., November, 1974

On Families of Intersecting Sets.

Andrzej Ehrenfeucht, Jan Mycielski

J. Comb. Theory, Ser. A, 1974

Nonterminals Versus Homomorphisms in Defining Languages for Some Classes of Rewriting Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Acta Informatica, 1974

Trade-off between the Use of Nonterminals, Codings and Homomorphisms in Defining Languages for Some Classes of Rewriting Systems.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974

D0L Systems With Rank.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the L Systems, 1974

Three Useful Results Concerning L Languages Without Interactions.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Proceedings of the L Systems, 1974

Generatively Deterministic L Languages. Subword Point of View.

Andrzej Ehrenfeucht, K. P. Lee, Grzegorz Rozenberg

Proceedings of the L Systems, 1974

1973

Discernible Elements in Models for Peano Arithmetic.

Andrzej Ehrenfeucht

J. Symb. Log., 1973

A Limit Theorem for Sets of Subwords in Deterministic T0L Languages.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Inf. Process. Lett., 1973

1957

Two Theories with Axioms Built by Means of Pleonasms.

Andrzej Ehrenfeucht

J. Symb. Log., 1957