Distinguished Professor Emeritus Janusz (John) A. Brzozowski passed away on Thursday, October 24, 2019 at age 84. Please see the in memoriam for our tribute to him and details about his personal and academic life.
His research profile has been preserved for historical interest.
Research interests
Professor
Brzozowski’s research
interests
were
in
the
theory
of
automata
and
formal
languages,
particularly
in
complexity
of
regular
languages
and
finite
automata.
Finite
automata
and
regular
languages
are
the
simplest
models
of
computation,
and
appear
in
many
applications.
State
complexity
is
a
frequently
used
measure
of
complexity
of
regular
language
operations.
It
is
the
maximal
number
of
states
in
a
minimal
deterministic
finite
automaton
(DFA)
of
the
language
resulting
from
the
operation
as
a
function
of
the
state
complexities
of
minimal
DFAs
of
the
operands.
Professor
Brzozowski
generalized
the
concept
of
convex
languages
and
unified
many
diverse
regular
language
classes
under
the
same
convex
umbrella.
He
proved
that
star-free
languages,
a
proper
subclass
of
regular
languages,
meet
all
the
complexity
bounds
of
regular
languages
with
one
very
small
exception.
He
proposed
syntactic
complexity
of
a
regular
language
as
another
complexity
measure;
this
is
the
size
of
the
syntactic
semigroup
of
the
language,
and
is
the
same
as
the
size
of
the
transition
semigroup
of
a
minimal
DFA
of
that
language.
(The
transition
semigroup
of
a
DFA
is
the
set
of
transformations
of
the
states
of
the
DFA
induced
by
its
inputs.)
He
studied
the
state
and
syntactic
complexities
in
many
subclasses
of
convex
and
star-free
languages.
He
introduced
and
studied
a
nondeterministic
finite
automaton
(NFA),
called
a'tomaton,
uniquely
defined
by
every
regular
language,
and
studied
complexity
issues
associated
with
that
NFA.
He
developed
methods
of
reducing
non-determinism
in
NFAs
by
using
look-ahead
information.
Previously,
he
applied
ideas
from
the
theory
of
automata
to
the
“trace-assertion”
specification
method
of
software
modules.
Professor
Brzozowski
worked
for
many
years
in
the
area
of
asynchronous
circuit
theory.
He
wrote
the
monograph
“Asynchronous
Circuits”,
Springer,
1995
(with C.-J.
Seger),
and
many
papers
on
this
topic.
He
developed
efficient
methods
for
detecting
hazards
(erroneous
signals)
in
VLSI
circuits
using
multi-valued
algebras.
In
the
past,
he
also
worked
on
circuit
testing
for
a
number
of
years.
This work
involved
finding
formal
models
for
circuit
faults,
and
the
derivation
of
short
test
sequences.
Most
of
this
work
was
oriented
towards
faults
in
random-access
memories.
Degrees and awards
- Canadian Pioneer in Computing, IBM, 2005
- Medal of Merit, Catholic University of Lublin, Poland, 2001
- Distinguished Professor Emeritus, University of Waterloo, 1996
- Japan Society for the Promotion of Science Research Fellowship, 1984
-
NSERC
Scientific
Exchange
Award
to
France,
1974-1975
Industrial and sabbatical experience
Professor Brzozowski held visiting appointments at University of California, Berkeley, CA (1965-66); Istituto Nazionale di Alta Matematica, Rome, Italy (1972); Institut de Programmation, Universite' Paris VI and VII, Paris, France (1974-75); Gesellschaft für Mathematik und Datenverarbeitung Bonn, Germany (1975); Instituto de Matemática e Estatística da Universidade de São Paulo, São Paulo, Brazil (1983); Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan (1984); Department of Mathematics and Computing Science, Technische Universiteit Eindhoven, Eindhoven, The Netherlands (1989-90).
Representative publications
J.
Brzozowski,
H.
Tamm.
Theory
of
A'tomata.
Theoret.
Comput.
Sc.
539:
13-27,
2014.
J.
Brzozowski.
In
Search
of
Most
Complex
Regular
Languages.
Internat.
J.
Found.
Comput.
Sc.
24(6):
691-708,
2013.
J.
Brzozowski,
B.
Liu.
Quotient
Complexity
of
Star-Free
Languages.
Internat.
J.
Found.
Comput.
Sc.
23(6):
1261-1276,
2012.
J.
Brzozowski,
B.
Li,
Y.
Ye.
Syntactic
Complexity
of
Prefix-,
Suffix-,
Bifix-,
and
Factor-Free
Regular
Languages.
Theoret.
Comput.
Sc.
449:
37-53,
2012.
J.
Brzozowski,
E.
Grant,
J.
Shallit.
Closures
in
Formal
Languages
and
Kuratowski's
Theorem.
Internat.
J.
Found.
Comput.
Sc.
22(2):
310-321,
2011.