Sheng Yu

Affiliations:
  • University of Western Ontario, London, ON, Canada
  • University of Waterloo, ON, Canada (PhD 1986)


According to our database1, Sheng Yu authored at least 155 papers between 1984 and 2017.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2017
A Survey on Operational State Complexity.
J. Autom. Lang. Comb., 2017

2014
State Complexity of Combined Operations for Prefix-Free Regular Languages.
Proceedings of the Discrete Mathematics and Computer Science. In Memoriam Alexandru Mateescu (1952-2005)., 2014

2013
Undecidability of state complexity.
Int. J. Comput. Math., 2013

2012
Statecharts.
Proceedings of the Handbook of Finite State Based Models and Applications., 2012

State complexity of union and intersection of square and reversal on k regular languages.
Theor. Comput. Sci., 2012

State complexity of union and intersection of star on k regular languages.
Theor. Comput. Sci., 2012

State complexity of combined operations with two basic operations.
Theor. Comput. Sci., 2012

State Complexity and Approximation.
Int. J. Found. Comput. Sci., 2012

State Complexity of Two Combined Operations: Catenation-Star and Catenation-Reversal.
Int. J. Found. Comput. Sci., 2012

State Complexity of Combined Operations with Union, Intersection, Star and Reversal.
Fundam. Informaticae, 2012

Derivatives of Regular Expressions and an Application.
Proceedings of the Computation, Physics and Beyond, 2012

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

State Complexity of Two Combined Operations: Catenation-Union and Catenation-Intersection.
Int. J. Found. Comput. Sci., 2011

Transition Complexity of Incomplete DFAs.
Fundam. Informaticae, 2011

Derick Wood: Always in Our Hearts.
Proceedings of the Implementation and Application of Automata, 2011

Undecidability of the State Complexity of Composed Regular Operations.
Proceedings of the Language and Automata Theory and Applications, 2011

State Complexity Research and Approximation.
Proceedings of the Developments in Language Theory - 15th International Conference, 2011

State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal.
Proceedings of the Descriptional Complexity of Formal Systems, 2011

2010
Seventy Years Derick Wood.
J. Univers. Comput. Sci., 2010

Subword Occurrences, Parikh Matrices and Lyndon Images.
Int. J. Found. Comput. Sci., 2010

On implementing recognizable transductions.
Int. J. Comput. Math., 2010

State Complexity of Catenation Combined with Star and Reversal
Proceedings of the Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, 2010

State Complexity of Two Combined Operations: Reversal-Catenation and Star-Catenation
CoRR, 2010

State complexity of union and intersection combined with star and reversal
CoRR, 2010

State Complexity of Catenation Combined with Union and Intersection.
Proceedings of the Implementation and Application of Automata, 2010

2009
Deciding determinism of caterpillar expressions.
Theor. Comput. Sci., 2009

Hierarchy and equivalence of multi-letter quantum finite automata.
Theor. Comput. Sci., 2009

Estimation of state complexity of combined operations.
Theor. Comput. Sci., 2009

Variants of codes and indecomposable languages.
Inf. Comput., 2009

State Complexity Approximation
Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009

Are Statecharts Finite Automata?
Proceedings of the Implementation and Application of Automata, 2009

State Complexity of Combined Operations for Prefix-Free Regular Languages.
Proceedings of the Language and Automata Theory and Applications, 2009

2008
State complexity of basic language operations combined with reversal.
Inf. Comput., 2008

The State Complexity of Two Combined Operations: Star of Catenation and Star of Reversal.
Fundam. Informaticae, 2008

Length Codes, Products of Languages and Primality.
Proceedings of the Language and Automata Theory and Applications, 2008

2007
State complexity of combined operations.
Theor. Comput. Sci., 2007

On the existence of prime decompositions.
Theor. Comput. Sci., 2007

A Family of NFAs Free of State Reductions.
J. Autom. Lang. Comb., 2007

Sc-Expressions in Object-Oriented Languages.
Int. J. Found. Comput. Sci., 2007

On the State Complexity of Combined Operations and their Estimation.
Int. J. Found. Comput. Sci., 2007

Fuzzification of Rational and Recognizable Sets.
Fundam. Informaticae, 2007

Cover Automata for Finite Language.
Bull. EATCS, 2007

Representation and uniformization of algebraic transductions.
Acta Informatica, 2007

Deterministic Caterpillar Expressions.
Proceedings of the Implementation and Application of Automata, 2007

State Complexity of Basic Operations Combined with Reversal.
Proceedings of the LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications., 2007

2006
Subword conditions and subword histories.
Inf. Comput., 2006

Nondeterministic Bimachines and Rational Relations with Finite Codomain.
Fundam. Informaticae, 2006

On the State Complexity of Combined Operations.
Proceedings of the Implementation and Application of Automata, 2006

On Weakly Ambiguous Finite Transducers.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

State Complexity of Catenation and Reversal Combined with Star.
Proceedings of the 8th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2006, Las Cruces, New Mexico, USA, June 21, 2006

2005
Mergible states in large NFA.
Theor. Comput. Sci., 2005

Preface.
Int. J. Found. Comput. Sci., 2005

State Complexity: Recent Results and Open Problems.
Fundam. Informaticae, 2005

Type Theory and Language Constructs for Objects with States.
Proceedings of the First International Workshop on Developments in Computational Models, 2005

Adding States into Object Types.
Proceedings of The 2005 International Conference on Programming Languages and Compilers, 2005

Large NFA Without Mergeable States.
Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30, 2005

Reducing the Size of NFAs by Using Equivalences and Preorders.
Proceedings of the Combinatorial Pattern Matching, 16th Annual Symposium, 2005

2004
On the state complexity of reversals of regular languages.
Theor. Comput. Sci., 2004

Subword histories and Parikh matrices.
J. Comput. Syst. Sci., 2004

Pattern expressions and pattern automata.
Inf. Process. Lett., 2004

Word Complexity And Repetitions In Words.
Int. J. Found. Comput. Sci., 2004

Process Traces With the Option Operation.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 2004

On NFA Reductions.
Proceedings of the Theory Is Forever, 2004

2003
Reducing NFAs by invariant equivalences.
Theor. Comput. Sci., 2003

A Formal Study Of Practical Regular Expressions.
Int. J. Found. Comput. Sci., 2003

Follow automata.
Inf. Comput., 2003

Fast Algorithms for Extended Regular Expression Matching and Searching.
Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Introduction to Process Traces.
Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, 2003

2002
Decidability of EDT0L structural equivalence.
Theor. Comput. Sci., 2002

Additive Distances and Quasi-Distances Between Words.
J. Univers. Comput. Sci., 2002

Advances and Trends in Automata and Formal Languages A Collection of Papers in Honour of the 60th Birthday of Helmut Jürgensen - J.UCS Special Issue.
J. Univers. Comput. Sci., 2002

Tight Lower Bound for the State Complexity of Shuffle of Regular Languages.
J. Autom. Lang. Comb., 2002

Implementation and Application of Automata - Editor's Foreword.
Int. J. Found. Comput. Sci., 2002

An Efficient Algorithm for Constructing Minimal Cover Automata for Finite Languages.
Int. J. Found. Comput. Sci., 2002

State Complexity of Finite and Infinite Regular Languages.
Bull. EATCS, 2002

On the robustness of primitive words.
Discret. Appl. Math., 2002

Factorizations of Languages and Commutativity Conditions.
Acta Cybern., 2002

Regex and Extended Regex.
Proceedings of the Implementation and Application of Automata, 2002

Algorithms for Computing Small NFAs.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Repetition Complexity of Words.
Proceedings of the Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21, 2002

Constructing NFA s by Optimal Use of Positions in Regular Expressions.
Proceedings of the Combinatorial Pattern Matching, 13th Annual Symposium, 2002

2001
Minimal cover-automata for finite languages.
Theor. Comput. Sci., 2001

Class-is-type is inadequate for object reuse.
ACM SIGPLAN Notices, 2001

State Complexity of Regular Languages.
J. Autom. Lang. Comb., 2001

On the State Complexity of k-Entry Deterministic Finite Automata.
J. Autom. Lang. Comb., 2001

A sharpening of the Parikh mapping.
RAIRO Theor. Informatics Appl., 2001

Tree-systems of morphisms.
Acta Informatica, 2001

Minimal Covers of Formal Languages.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

The time dimension of computation models.
Proceedings of the Where Mathematics, 2001

2000
Alternating finite automata and star-free languages.
Theor. Comput. Sci., 2000

Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata.
Theor. Comput. Sci., 2000

Using DNA to solve the Bounded Post Correspondence Problem.
Theor. Comput. Sci., 2000

On Fairness of Many-Dimensional Trajectories.
J. Autom. Lang. Comb., 2000

An O(n<sup>2</sup>) Algorithm for Constructing Minimal Cover Automata for Finite Languages.
Proceedings of the Implementation and Application of Automata, 2000

State Complexity of Regular Languages: Finite versus Infinite.
Proceedings of the Finite Versus Infinite, 2000

1999
Synchronization Expressions and Languages.
J. Univers. Comput. Sci., 1999

Towards a DNA Solution to the Shortest Common Superstring Problem.
Int. J. Artif. Intell. Tools, 1999

On Synchronization in P Systems.
Fundam. Informaticae, 1999

Generalized Fairness and Context-Free Languages.
Acta Cybern., 1999

State Complexity of Basic Operations on Finite Languages.
Proceedings of the Automata Implementation, 1999

Metric Lexical Analysis.
Proceedings of the Automata Implementation, 1999

On the decomposition of finite languages.
Proceedings of the Developments in Language Theory, 1999

Synchronization Expressions: Characterization Results and Implementation.
Proceedings of the Jewels are Forever, 1999

1998
Synchronization Expressions with Extended Join Operation.
Theor. Comput. Sci., 1998

DNA Computing, Sticker Systems, and Universality.
Acta Informatica, 1998

Implementing Reversed Alternating Finite Automaton (r-AFA) Operations.
Proceedings of the Automata Implementation, 1998

Practical Rules for Reduction on the Number of States of a State Diagram.
Proceedings of the TOOLS 1998: 26th International Conference on Technology of Object-Oriented Languages and Systems, 1998

1997
Regular Languages.
Proceedings of the Handbook of Formal Languages, Volume 1: Word, Language, Grammar., 1997

NFA to DFA Transformation for Finite Languages over Arbitrary Alphabets.
J. Autom. Lang. Comb., 1997

Language-theoretic Complexity of Disjunctive Sequences.
Discret. Appl. Math., 1997

Efficient Implementation of Regular Languages Using R-AFA.
Proceedings of the Automata Implementation, 1997

Decidability of fairness for context-free languages.
Proceedings of the 3rd International Conference Developments in Language Theory, 1997

At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems.
Proceedings of the DNA Based Computers, 1997

Rewriting Rules for Synchronization Languages.
Proceedings of the Structures in Logic and Computer Science, 1997

1996
Structural Equivalence and ET0L Grammars.
Theor. Comput. Sci., 1996

On Synchronization Languages.
Fundam. Informaticae, 1996

NFA to DFA Transformation for Finite Languages.
Proceedings of the Automata Implementation, 1996

EDTOL Structural Equivalence is Decidable.
Proceedings of the First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, 1996

1995
P, NP and the Post Correspondence Problem
Inf. Comput., September, 1995

Lexical Analysis with a Simple Finite-Fuzzy-Automaton Model.
J. Univers. Comput. Sci., 1995

Decision Problems for Patterns.
J. Comput. Syst. Sci., 1995

Complexity of E0L Structural Equivalence.
RAIRO Theor. Informatics Appl., 1995

Nondeterminism Degrees for Context-Free Languages.
Proceedings of the Developments in Language Theory II, 1995

1994
The State Complexities of Some Basic Operations on Regular Languages.
Theor. Comput. Sci., 1994

Transducers and the Decidability of Independence in Free Monoids.
Theor. Comput. Sci., 1994

Measures of Nondeterminism for Pushdown Automata.
J. Comput. Syst. Sci., 1994

Pumping and Pushdown Machines.
RAIRO Theor. Informatics Appl., 1994

on Sparse Languages L such that LL = Sigma.
Discret. Appl. Math., 1994

Synchronization expressions and languages.
Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing, 1994

Rediscovering Pushdown Machines.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993
Decidability of the Intercode Property.
J. Inf. Process. Cybern., 1993

Morphisms and rational tranducers.
Bull. EATCS, 1993

Inclusion is Undecidable for Pattern Languages.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Structural Equivalences and ET0L Grammars (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 9th International Symposium, 1993

1992
Attempting guards in parallel: A data flow approach to execute generalized guarded commands.
Int. J. Parallel Program., 1992

Iterative tree automata, alternating Turing machines, and uniform Boolean circuits: relationships and characterization.
Proceedings of the 1992 ACM/SIGAPP Symposium on Applied Computing: Technological Challenges of the 1990's, 1992

Characterizing Regular Languages with Polynomial Densities.
Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Obtaining Tight Upper Bounds for the State Complexities of DFA Operations.
Proceedings of the Computing and Information, 1992

1991
Decidability of Structural Equivalence of E0L Grammars.
Theor. Comput. Sci., 1991

On the state complexity of intersection of regular languages.
SIGACT News, 1991

Primary Types of Instances of the Post Correspondence Problem.
Bull. EATCS, 1991

Cellular automata, omegaomega-regular sets, and sofic systems.
Discret. Appl. Math., 1991

Data Flow Implementation of Generalized Guarded Commands.
Proceedings of the PARLE '91: Parallel Architectures and Languages Europe, 1991

Degrees of Nondeterminism for Pushdown Automata.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

ParC project: practical constructs for parallel programming languages.
Proceedings of the Fifteenth Annual International Computer Software and Applications Conference, 1991

1990
The Immortality Problem for LAG Systems.
Inf. Process. Lett., 1990

Constructions for alternating finite automata.
Int. J. Comput. Math., 1990

1989
On the Limit Sets of Cellular Automata.
SIAM J. Comput., 1989

1988
Can the catenation of two weakly sparse languages be dense?
Discret. Appl. Math., 1988

Undecidability of CA Classification Schemes.
Complex Syst., 1988

1986
Real-Time, Pseudo Real-Time, and Linear-Time ITA.
Theor. Comput. Sci., 1986

On the equivalence of grammars inferred from derivation.
Bull. EATCS, 1986

A property of real-time trellis automata.
Discret. Appl. Math., 1986

1985
Translation of Systolic Algorithms between Systems of Different Topology.
Proceedings of the International Conference on Parallel Processing, 1985

1984
Iterative Tree Automata.
Theor. Comput. Sci., 1984


  Loading...