Andrzej Ehrenfeucht

Affiliations:
  • University of Colorado, USA


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

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2017
Evolving reaction systems.
Theor. Comput. Sci., 2017

Reaction Systems: A Model of Computation Inspired by the Functioning of the Living Cell.
Proceedings of the Role of Theory in Computer Science, 2017

2015
Standard and ordered zoom structures.
Theor. Comput. Sci., 2015

2014
Zoom Structures and reaction Systems Yield Exploration Systems.
Int. J. Found. Comput. Sci., 2014

2013
Processes Inspired by the Functioning of Living Cells: Natural Computing Approach - (Abstract).
Proceedings of the Unconventional Computation and Natural Computation, 2013

Processes Inspired by the Functioning of Living Cells: Natural Computing Approach.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

2012
Minimal Reaction Systems.
Trans. Comp. Sys. Biology, 2012

Stability and Chaos in reaction Systems.
Int. J. Found. Comput. Sci., 2012

A Formal Framework for Processes Inspired by the Functioning of Living Cells.
Proceedings of the Implementation and Application of Automata, 2012

Relevance of Entities in Reaction Systems.
Proceedings of the Languages Alive, 2012

Representing Reaction Systems by Trees.
Proceedings of the Computation, Physics and Beyond, 2012

2011
Position heaps: A simple and dynamic text indexing data structure.
J. Discrete Algorithms, 2011

Functions Defined by Reaction Systems.
Int. J. Found. Comput. Sci., 2011

A Tour of reaction Systems.
Int. J. Found. Comput. Sci., 2011

A Formal Framework for Bioprocesses in Living Cells.
Proceedings of the Unconventional Computation - 10th International Conference, 2011

Reaction Systems with Duration.
Proceedings of the Computation, 2011

2010
Combinatorics of Life and Death for Reaction Systems.
Int. J. Found. Comput. Sci., 2010

Reaction Systems: a Formal Framework for Processes Based on Biochemical Interactions.
Electron. Commun. Eur. Assoc. Softw. Sci. Technol., 2010

A Note on Causalities in Reaction Systems.
Electron. Commun. Eur. Assoc. Softw. Sci. Technol., 2010

Reaction Systems: A Model of Computation Inspired by Biochemistry.
Proceedings of the Developments in Language Theory, 14th International Conference, 2010

2009
Introducing time in reaction systems.
Theor. Comput. Sci., 2009

Computational Nature of Processes Induced by Biochemical Reactions.
Proceedings of the Membrane Computing, 10th International Workshop, 2009

Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure.
Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

2008
Modeling Interactions between Biochemical Reactions.
Proceedings of the Applications and Theory of Petri Nets, 29th International Conference, 2008

2007
Events and modules in reaction systems.
Theor. Comput. Sci., 2007

Reaction Systems.
Fundam. Informaticae, 2007

Finite metrics in switching classes.
Discret. Appl. Math., 2007

Biochemical Reactions as Computations.
Proceedings of the Computation and Logic in the Real World, 2007

2006
Covers from Templates.
Int. J. Found. Comput. Sci., 2006

The Embedding Problem for Switching Classes of Graphs.
Fundam. Informaticae, 2006

Zdzislaw Pawlak (1926-2006).
Bull. EATCS, 2006

Embedding linear orders in grids.
Acta Informatica, 2006

Computational Nature of Biochemical Reactions.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

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

Transitivity of local complementation and switching on graphs.
Discret. Math., 2004

Embedding in Switching Classes with Skew Gains.
Proceedings of the Graph Transformations, Second International Conference, 2004

Basic Notions of Reaction Systems.
Proceedings of the Developments in Language Theory, 2004

2003
Forbidding-enforcing systems.
Theor. Comput. Sci., 2003

Formal systems for gene assembly in ciliates.
Theor. Comput. Sci., 2003

2002
Gene assembly through cyclic graph decomposition.
Theor. Comput. Sci., 2002

Characterizing the Micronuclear Gene Patterns in Ciliates.
Theory Comput. Syst., 2002

String and Graph Reduction Systems for Gene Assembly in Ciliates.
Math. Struct. Comput. Sci., 2002

2001
Sequences of languages in forbidding-enforcing families.
Soft Comput., 2001

Patterns of Micronuclear Genes in ciliates.
Proceedings of the DNA Computing, 7th International Workshop on DNA-Based Computers, 2001

Universal and simple operations for gene assembly in ciliates.
Proceedings of the Where Mathematics, 2001

Circularity and Other Invariants of Gene Assembly in Ciliates.
Proceedings of the Words, Semigroups, and Transductions, 2001

2000
Pancyclicity in switching classes.
Inf. Process. Lett., 2000

1999
Forbidding and enforcing.
Proceedings of the DNA Based Computers, 1999

The Theory of 2-Structures - A Framework for Decomposition and Transformation of Graphs.
World Scientific, ISBN: 978-981-02-4042-4, 1999

1998
On Representing Recursively Enumerable Languages by Internal Contextual Languages.
Theor. Comput. Sci., 1998

Permutations, parenthesis words, and Schröder numbers.
Discret. Math., 1998

Complexity Issues in Switching of Graphs.
Proceedings of the Theory and Application of Graph Transformations, 1998

1997
Contextual Grammars and Formal Languages.
Proceedings of the Handbook of Formal Languages, 1997

Invariants of Inversive 2-Structures on Groups of Labels.
Math. Struct. Comput. Sci., 1997

Semantics of Nonsequential Tree-Based Computation Schemes.
Fundam. Informaticae, 1997

2-Structures - A Framework For Decomposition And Transformation Of Graphs.
Proceedings of the Handbook of Graph Grammars and Computing by Graph Transformations, 1997

1996
A Note on Binary Grammatical Codes of Trees.
Theor. Comput. Sci., 1996

Finite Languages for the Representation of Finite Graphs.
J. Comput. Syst. Sci., 1996

On Representing RE Languages by One-Sided Internal Contextual Languages.
Acta Cybern., 1996

The Linear Landscape of External Contextual Languages.
Acta Informatica, 1996

A browsing system based on mul timedia cohesion.
Proceedings of WebNet 96, 1996

Forbidding, Enforcing.
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.
Fundam. Informaticae, 1995

The size of k-pseudotrees.
Discret. Math., 1995

Theory of 2-Structures.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

1994
Combinatorial Properties of Dependence Graphs
Inf. Comput., November, 1994

Properties of Grammatical Codes of Trees.
Theor. Comput. Sci., 1994

A k-Structure Generalization of the Theory of 2-Structures.
Theor. Comput. Sci., 1994

Clans and Regions in 2-Structures.
Theor. Comput. Sci., 1994

Hyperedge Channels are Abelian.
Theor. Comput. Sci., 1994

Semantics of Trees.
Math. Syst. Theory, 1994

Dynamic Labeled 2-Structures.
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.
J. Algorithms, 1994

Square Systems.
Fundam. Informaticae, 1994

Incremental construction of 2-structures.
Discret. Math., 1994

Context-free Text Grammars.
Acta Informatica, 1994

Group Based Graph Transformations and Hierarchical Representations of Graphs.
Proceedings of the Graph Gramars and Their Application to Computer Science, 1994

Dynamic Labeled 2-Structures with Variable Domains.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

Normal Forms for Contextual Grammars.
Proceedings of the Mathematical Aspects of Natural and Formal Languages, 1994

1993
T-structures, T-functions, and texts.
Theor. Comput. Sci., 1993

Efficient Detection of Quasiperiodicities in Strings.
Theor. Comput. Sci., 1993

Combinatorial Properties of Texts.
RAIRO Theor. Informatics Appl., 1993

On the Structure of Recognizable Languages of Dependence Graphs.
RAIRO Theor. Informatics Appl., 1993

An Introduction to Dynamic Labled 2-Structures.
Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

An Introduction to Context-free Text Grammars.
Proceedings of the Developments in Language Theory, 1993

1992
Angular 2-Structures.
Theor. Comput. Sci., 1992

A representation of partial Boolean algebras.
Fundam. Informaticae, 1992

1991
Grammatical codes of trees.
Discret. Appl. Math., 1991

1990
Primitivity is Hereditary for 2-Structures.
Theor. Comput. Sci., 1990

Theory of 2-Structures, Part II: Representation Through Labeled Tree Families.
Theor. Comput. Sci., 1990

Theory of 2-Structures, Part I: Clans, Basic Subclasses, and Morphisms.
Theor. Comput. Sci., 1990

A Characterization of Set Representable Labeled Partial 2-Structures Through Decompositions.
Acta Informatica, 1990

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

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

1989
A General Lower Bound on the Number of Examples Needed for Learning
Inf. Comput., September, 1989

Learning Decision Trees from Random Examples
Inf. Comput., September, 1989

Clans and the Complexity of Dependence graphs.
Proceedings of the A Perspective in Theoretical Computer Science, 1989

Learnability and the Vapnik-Chervonenkis dimension.
J. ACM, 1989

Average sizes of suffix trees and DAWGs.
Discret. Appl. Math., 1989

1988
A new distance metric on strings computable in linear time.
Discret. Appl. Math., 1988

Recording the Use of Memory in Right-Boundary Grammars and Push-Down Automata.
Acta Informatica, 1988

Textual and visual access to a computer by people who know nothing about it.
Proceedings of the 6th Annual International Conference on Systems Documentation, 1988

1987
Complete inverted files for efficient text retrieval and analysis.
J. ACM, 1987

Occam's Razor.
Inf. Process. Lett., 1987

1986
On the Active and Full Use of Memory in Right-Boundary Grammars and Push-Down Automata.
Theor. Comput. Sci., 1986

Addendum to the paper "On the dependence of functions on their variables".
J. Comb. Theory A, 1986

Each Regular Code Is Included in A Maximal Regular Code.
RAIRO Theor. Informatics Appl., 1986

Coordinated Pair Systems; Part II: Sparse Structure of Dyck Words and Ogden's Lemma.
RAIRO Theor. Informatics Appl., 1986

Coordinated Pair Systems; Part I: Dyck Works and Classical Pumping.
RAIRO Theor. Informatics Appl., 1986

On the membership problem for regular DNLC grammars.
Discret. Appl. Math., 1986

Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985
Adding Global Forbidding Context to Context-Free Grammars.
Theor. Comput. Sci., 1985

On Total Regulators Generated by Derivation Relations.
Theor. Comput. Sci., 1985

The Smallest Automaton Recognizing the Subwords of a Text.
Theor. Comput. Sci., 1985

A Combinatorial Property of EOL Languages.
Math. Syst. Theory, 1985

Strong Iterative Pairs and The Regularity of Context-Free Languages.
RAIRO Theor. Informatics Appl., 1985

A morphic representation of EOL languages and other ETOL languages.
Discret. Appl. Math., 1985

On coordinated rewriting.
Proceedings of the Fundamentals of Computation Theory, 1985

1984
An Easy Proof of Greibach Normal Form
Inf. Control., December, 1984

On Inherently Ambiguous E0L Languages.
Theor. Comput. Sci., 1984

Restrictions on NLC Graph Grammars.
Theor. Comput. Sci., 1984

On Ambiguity in Dos Systems.
RAIRO Theor. Informatics Appl., 1984

A new method of proving theorems on chromatic index.
Discret. Math., 1984

On regularity of languages generated by copying systems.
Discret. Appl. Math., 1984

Building a Complete Inverted File for a Set of Text Files in Linear Time
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.
Proceedings of the Automata, 1984

1983
On Regularity of Context-Free Languages.
Theor. Comput. Sci., 1983

Context Free Normal Systems and ETOL Systems.
J. Comput. Syst. Sci., 1983

On the Separating Power of Eol Systems.
RAIRO Theor. Informatics Appl., 1983

On the Subword Complexity of m-Free D0L Languages.
Inf. Process. Lett., 1983

On the Subword Complexity of Locally Catenative D0L Languages.
Inf. Process. Lett., 1983

Repetition of Subwords in DOL Languages
Inf. Control., 1983

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

1982
Representation Theorems Using DOS Languages.
Theor. Comput. Sci., 1982

The (Generalized) Post Correspondence Problem with Lists Consisting of two Words is Decidable.
Theor. Comput. Sci., 1982

On the Dependence of Functions on Their Variables.
J. Comb. Theory A, 1982

On Subword Complexities of Homomorphic Images of Languages.
RAIRO Theor. Informatics Appl., 1982

Basic formulas and languages: PART II.Applications to E0L systems and forms.
Discret. Appl. Math., 1982

Compositional complexity of Boolean functions.
Discret. Appl. Math., 1982

Repetitions in Homomorphisms and Languages.
Proceedings of the Automata, 1982

Conditions Enforcing Regularity of Context-Free Languages.
Proceedings of the Automata, 1982

1981
On the Subword Complexity of Square-Free D0L Languages.
Theor. Comput. Sci., 1981

On ET0L Systems with Finite Tree-Rank.
SIAM J. Comput., 1981

Pumping Lemmas for Regular Sets.
SIAM J. Comput., 1981

A Morphic Representation of Complements of Recursively Enumerable Sets.
J. ACM, 1981

FPOL Systems Generating Counting Languages.
RAIRO Theor. Informatics Appl., 1981

On the Subword Complexity of D0L Languages with a Constant Distribution.
Inf. Process. Lett., 1981

Basic formulas and languages Part I. The theory.
Discret. Appl. Math., 1981

On the Subword Complexity and Square-Freeness of Formal Languages.
Proceedings of the Theoretical Computer Science, 1981

On the (Generalized) Post Correspondence Problem with Lists of Length 2.
Proceedings of the Automata, 1981

1980
On Basic Properties of DOS Systems and Languages
Inf. Control., November, 1980

Continuous Grammars
Inf. Control., July, 1980

On a Bound for the D0L Sequence Equivalence Problem.
Theor. Comput. Sci., 1980

On Ambiguity in E0L Systems.
Theor. Comput. Sci., 1980

Every Two Equivalent D0L Systems have a Regular True Envelope.
Theor. Comput. Sci., 1980

The Sequence Equivalence Problem is Decidable for 0S Systems.
J. ACM, 1980

On the Emptiness of the Intersection of Two D0S Languages Problem.
Inf. Process. Lett., 1980

Many-to-one simulation in E0L forms is decidable.
Discret. Appl. Math., 1980

DOS Systems and Languages.
Proceedings of the Automata, 1980

1979
On k-Stable Functions.
J. Comb. Theory A, 1979

On ET0L Systems with Rank.
J. Comput. Syst. Sci., 1979

Finding a Homomorphism Between Two Words is NP-Complete.
Inf. Process. Lett., 1979

An Observation on Scattered Grammars.
Inf. Process. Lett., 1979

Periodicity and unbordered segments of words.
Discret. Math., 1979

1978
Simplifications of Homomorphisms
Inf. Control., September, 1978

Elementary Homomorphisms and a Solution of the D0L Sequence Equivalence Problem.
Theor. Comput. Sci., 1978

E0L Languages are not Codings of FP0L Languages.
Theor. Comput. Sci., 1978

On the Structure of Derivations in Deterministic ET0L Systems.
J. Comput. Syst. Sci., 1978

A note on DOL length sets.
Discret. Math., 1978

1977
On Some Context Free Languages That Are Not Deterministic ETOL Languages.
RAIRO Theor. Informatics Appl., 1977

1976
A Relationship between ET0L and EDT0L Languages.
Theor. Comput. Sci., 1976

Complexity Measures for Regular Expressions.
J. Comput. Syst. Sci., 1976

On the number of subwords of everywhere growing DTOL languages.
Discret. Math., 1976

On Proving that Certain Languages are not ETOL.
Acta Informatica, 1976

1975
Subword Complexities of Various Classes of Deterministic Developmental Languages without Interactions.
Theor. Comput. Sci., 1975

Practical Decidability.
J. Comput. Syst. Sci., 1975

A Pumping Theorem for Deterministic Etol Languages.
RAIRO Theor. Informatics Appl., 1975

Subword complexities of various classes of deterministic developmental languages with interactions.
Int. J. Parallel Program., 1975

On the (Combinatorial) Structure of L Languages without Interactions
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On (Un)predictability of Formal Languages (Extended Abstract)
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On Θ-Determined E0L Languages.
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.
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
Inf. Control., November, 1974

On Families of Intersecting Sets.
J. Comb. Theory A, 1974

Nonterminals Versus Homomorphisms in Defining Languages for Some Classes of Rewriting Systems.
Acta Informatica, 1974

Trade-off between the Use of Nonterminals, Codings and Homomorphisms in Defining Languages for Some Classes of Rewriting Systems.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, Germany, July 29, 1974

D0L Systems With Rank.
Proceedings of the L Systems, 1974

Three Useful Results Concerning L Languages Without Interactions.
Proceedings of the L Systems, 1974

Generatively Deterministic L Languages. Subword Point of View.
Proceedings of the L Systems, 1974

1973
Discernible Elements in Models for Peano Arithmetic.
J. Symb. Log., 1973

A Limit Theorem for Sets of Subwords in Deterministic T0L Languages.
Inf. Process. Lett., 1973

1957
Two Theories with Axioms Built by Means of Pleonasms.
J. Symb. Log., 1957


  Loading...