2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
See also
Maveric Group Publications for older papers.
List of papers on
Asynchronous Circuit Theory
(pdf)
Last updated August 30, 2010
The list below is in a different format and the papers are not yet
available on line.
Theses
Books
Contributions to Books
Journal Papers 2001 -
Journal Papers 1991 -
Journal Papers 1981 - 1990
Journal Papers 1971 - 1980
Journal Papers 1962 - 1970
Conference Papers 1991 -
Conference Papers 1981 - 1990
Conference Papers 1971 - 1980
Conference Papers 1962 - 1970
Go back to J. Brzozowski's home page .
To appear.
Quotient Complexity of Star-Free Languages
Internat. J. Found. Comput. Sci.
To appear.
Quotient Complexity of Closed Languages
Theory Comput. Syst.
Go to the top of this document.
Go to the top of this document.
Syntactic Complexity of R- and J-Trivial Regular Languages
23 August 2012.
arXiv
Quotient Complexities of Atoms of Regular Languages.
16th International Conference on Developments in Language Theory,
DLT 2012,
Taipei, Taiwan, August 14-17, 2012.
H.-C. Yen, O. H. Ibarra, eds.,
LNCS 7410, 50-61,2012.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at www.springerlink.com
Syntactic Complexities of Some Classes of Star-Free Languages.
14th International Workshop on Descriptional Complexity of Formal Systems,
DCFS 2012,
Braga, Portugal, July 23-25, 2012.
M. Kutrib, N. Moreira, R. Reis, eds.,
LNCS 7386, 117-129, 2012.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at www.springerlink.com
In Search of Most Complex Regular Languages.
17th International Conference on Implementation and Application of Automata,
CIAA 2012,
Porto, Portugal, July 17-25, 2012.
N. Moreira, R. Reis, eds.,
LNCS 7381, 5-24, 2012.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at www.springerlink.com
ERRATA:
1. The following reference should be added:
G. Liu, C. Martin-Vide, C. Salomaa, S. Yu.
State complexity of basic language operations combined with reversal,
Inform. and Comput. 206 (2008) 1178-1186.
2. The statement before Conjecture 3 on p. 17 should cite the reference above, and should state that ternary witnesses were used.
The conjecture is false for m=n=4, but true when the final states are changed as follows:
For K let the set of final states be {0, 2}, and for L, {1, 3}, except when n=3; then use {1}.
See the arxiv paper under CONJECTURES below.
3. The sentence before Conjecture 4 should be removed.
4. The paragraph on p. 21 after Conjecture 17 should correct the authors of [7] to Cui, Gao, Kari and Yu, and state that
ternary witnesses were used.
CONJECTURES 7, 9, 10, 12, 15, and 17 have now been proved. See
arxiv.org/abs/1207.1982
CONJECTURES 1, 2, 3, 4, 8, 11 and 14 have now been proved. See
arxiv.org/abs/1207.0535
Universal Witnesses for State Complexity of Boolean Operations Combined with Star
9 July 2012.
arXiv
Universal Witnesses for State Complexity of Basic Operations Combined with Reversal
2 July 2012.
arXiv
Syntactic Complexity of Prefix-, Suffix-, Bifix-, and Factor-Free Regular Languages
Theoretical Computer Science,
449, 37-53, 2012.
pdf
Syntactic Complexity of Finite/Cofinite, Definite, and Reverse Definite Languages
13 March 2012.
arXiv
Quotient Complexity of Atoms of Regular Languages
Revised
9 March 2012.
arXiv
On the Complexity of the Evaluation of Transient Extensions of Boolean Functions.
Internat. J. Found. Comput. Sci.
23 (1), 21-35, 2012.
pdf
Quotient Complexity of Atoms of Regular Languages
31 December 2011.
arXiv
Syntactic Complexity of Star-Free Languages
15 September 2011.
arXiv
Quotient Complexity of Star-Free Languages.
13th International Conference on Automata and Formal Languages,
AFL 2011,
Debrecen, Hungary, August 17-22, 2011.
P. Domosi, I. Szabolcs, eds.,
Institute of Mathematics and Informatics
College of Nyiregyhaza, Nyiregyhaza, Hungary, 138-152, 2011.
pdf
Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages.
13th International Conference on Automata and Formal Languages,
AFL 2011,
Debrecen, Hungary, August 17-22, 2011.
P. Domosi, I. Szabolcs, eds.,
Institute of Mathematics and Informatics
College of Nyiregyhaza, Nyiregyhaza, Hungary, 123-137, 2011.
pdf
Syntactic Complexity of Prefix-, Suffix-, and Bifix-Free Regular Languages.
13th International Workshop on Descriptional Complexity of Formal Systems,
DCFS 2011,
Limburg, Germany, July 25-27, 2011.
M. Holzer, M. Kutrib, G. Pighizzini, eds.,
LNCS 6808, 93-106, 2011.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Theory of Atomata.
15th International Conference on Developments in Language Theory,
DLT 2011,
Milan, Italy, July 19-22, 2011.
G. Mauri, A. Leporati, eds.,
LNCS 6795, 105-116, 2011.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Syntactic Complexity of Ideal and Closed Languages.
15th International Conference on Developments in Language Theory,
DLT 2011,
Milan, Italy, July 19-22, 2011.
G. Mauri, A. Leporati, eds.,
LNCS 6795, 117-128, 2011.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Quotient Complexity of Bifix-, Factor-, and Subword-Free Regular Languages.
11 May, 2011.
arXiv, Re-revised version with several new results
Closures in Formal Languages and Kuratowski's Theorem.
Internat. J. Found. Comput. Sci.
22, (2), 310-321, 2011.
pdf
Decision Problems for Convex Langages.
Inform. and Comput.
209, 353-367, 2011.
pdf
pdf
Quotient Complexity of Regular Languages.
Journal of Automata, Languages and Combinatorics
15 (1/2), 71-89, 2010.
pdf
Quotient Complexity of Star-Free Languages
17 December 2010.
arXiv
Quotient Complexity of Bifix-, Factor-, and Subword-Free Languages.
6 December, 2010.
arXiv, Revised Version
Syntactic Complexity of Ideal and Closed Languages.
15 October 2010.
arXiv
Quotient Complexity of Bifix-, Factor-, and Subword-Free Languages.
June 24, 2010.
arXiv
On the Complexity of the Evaluation of Transient Extensions of Boolean Functions.
12th International Workshop on Descriptional Complexity of Formal Systems,
DCFS 2010,
Saskatoon, SK, Canada, August 8-10, 2010.
I. McQuillan, G. Pighizzini, eds.,
Technical Report 2010-02,
Department of Computer Science, University of Saskatchewan, pp. 38-49.
pdf
EPTCS
Quotient Complexity of Closed Languages.
5th International Computer Science Symposium in Russia,
CSR 2010,
Kazan, Russia, June 16-20, 2010.
F. Ablayev, E. W. Mayr, eds.,
LNCS 6072, 84-95, 2010.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Complexity in Convex Languages.
4th International Conference on Language and Automata Theory and Applications,
LATA 2010,
Trier, Germany, May 24-28, 2010.
A.-H. Dediu, H. Fernau, C. Martin-Vide, eds.,
LNCS 6031, 1-15, 2010.
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Quotient Complexity of Ideal Languages.
9th Latin American Theoretical Informatics Symposium,
LATIN 2010,
Oaxaca, Mexico, April 19-23, 2010.
A. Lopez-Ortiz. ed.,
LNCS 6034, 208-221, 2010.
Copyright Springer-Verlag GmbH Berlin Heidelberg
Full paper at arXiv
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
Go to the top of this document.
J. Brzozowski.
Go to the top of this document.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Go to the top of this document.
Go back to J. Brzozowski's home page.
Quotient Complexity of Closed Languages.
December 5, 2009.
arXiv
Quotient Complexity of Ideal Languages.
August 14, 2009. Full paper:
arXiv
Quotient Complexity of Regular Languages.
Descriptional Complexity of Formal Systems, DCFS 2009
Magdeburg, Germany, July 6-9, 2009.
J. Dassow, G. Pighizzini, B. Truthe, eds.,
Otto-von-Guericke-Universit"at Magdeburg, 25-42, 2009.
pdf
Extended Abstract
arXiv
Languages Convex with Respect to Binary Relations and Their Closure Properties.
Acta Cybernetica,
19, 445-464, 2009.
pdf
Corrected version posted 24 February 2011
Predictable Semiautomata.
Theoretical Computer Science,
410, 3236-3249, 2009.
pdf
State Complexity Hierarchies of Uniform Languages of Alphabet-Size Length.
Theoretical Computer Science,
410, 3223-3235, 2009.
pdf
Closures in Formal Languages and Kuratowski's Theorem.
Developments in Language Theory, DLT 2009,
Stuttgart, Germany, June 30-July 3, 2009.
V. Diekert, D. Nowotka, eds.,
LNCS 5583, 125-144, 2009.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Decision Problems for Convex Languages.
Language and Automata Theory and Applications, LATA 2009,
Tarragona, Spain, April 2-8, 2009.
A. Dediu, A. Ionescu, C. Martin-Vide, eds.,
LNCS 5457, 247-258, 2009.
pdf
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Determinism without Determinization.
Descriptional Complexity of Formal Systems, DCFS 2008
Charlottetown, Prince Edward Island, July 16-18, 2008.
C. Campeanu, G. Pighizzini, eds.,
University of Prince Edward Island,
109-120, 2008.
pdf
State-Complexity Hierarchies of Uniform Languages of Alphabet-Size Length.
Descriptional Complexity of Formal Systems, DCFS 2008
Charlottetown, Prince Edward Island, July 16-18, 2008.
C. Campeanu, G. Pighizzini, eds.,
University of Prince Edward Island,
97-108, 2008.
pdf
Continuous Languages.
Automata and Formal Languages, AFL 2008
Balatonf"ured, Hungary, May 27-30, 2008.
E. Csuhaj-Varju and Z. Esik, eds.,
Computer and Information Research Institute,
Hungarian Academy of Sciences,
74-85, 2008.
pdf
Representations of Semiautomata by Canonical Words and Equivalences.
Part II: Specification of Software Modules,
Int. J. Foundations of Computer Science
18, 1065-1087, 2007.
pdf
Simulation of Gate Circuits with Feedback in Multi-Valued Algebras.
International Symposium on Multiple-Valued Logic, ISMVL 2004
Oslo, Norway, May 14-15, 2007.
IEEE Computer Society,
paper 46, 6 pp., 2007.
pdf
Covering of Transient Simulation of Feedback-Free Circuits by Binary Analysis.
Int. J. Foundations of Computer Science
17, 949-973, 2006.
pdf
Topics in Asynchronous Circuit Theory.
In
Recent Advances in Formal Languages and Applications
Studies in Computational Intelligence 25.
Z. Esik, C. Martin-Vide, and V. Mitrana, eds.,
Springer, 11-42,
2006.
pdf
Representation of a Class of Nondeterministic Semiautomata by Canonical Words.
Theoretical Computer Science
356, 46-57, 2006.
pdf
Representation of Semiautomata by Canonical Words and Equivalences.
Int. J. Foundations of Computer Science
16, 831-850, 2005.
pdf
(Corrected after publication)
Gate Circuits in the Algebra of Transients.
Theoretical Informatics and Applications
39, 67-91, 2005.
pdf
Duality for Three: Ternary Symmetry in Process Spaces.
In:
Theory is Forever
Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday.
J. Karhumaki, H. Maurer, G. Paun, G. Rozenberg, eds.,
LNCS 3113, Springer, 1-14, 2004.
pdf
Involuted Semilattices and Uncertainty in Ternary Algebras.
International Journal of Algebra and Computation
14, 295-310, 2004.
pdf
Representation of Semiautomata by Canonical Words and Equivalences.
Descriptional Complexity of Formal Systems, DCFS 2004
London, ON, July 26-28, 2005.
L. Ilie, D. Wotschke, eds.,
Report No. 619, Department of Computer Science,
University of Western Ontario, London, ON, Canada, 13-27, 2004.
pdf
J.-M. Champarnaud, D. Maurel, eds.,
Decomposition of Boolean Functions Specified by Cubes.
Journal of Multiple-Valued Logic and Soft Computing,
9, 377-417, 2003.
pdf
Simulation of Feedback-Free Circuits in the Algebra of Transients.
Int. J. Foundations of Computer Science,
14, 1033-1054, 2003.
pdf
Hazard Algebras.
Formal Methods in System Design,
23, 223-256, 2003.
pdf
True Concurrency in Models of Asynchronous Circuit Behavior.
Formal Methods in System Design,
22, 183-203, 2003.
pdf
Algebras for Hazard Detection. In
Beyond Two - Theory and Applications of Multiple-Valued Logic,
M. Fitting and E. Orlowska, eds.,
Physica-Verlag, Heidelberg, 3-24, 2003.
pdf
(Reprinted from ISMVL 2001)
Feedback-Free Circuits in the Algebra of Transients. In
Implementation and Application of Automata,
(Revised papers from CIAA 2002, Tours, France, July 2002)
LNCS 2608, 106-116, 2003.
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
Simulation of Gate Circuits in the Algebra of Transients. In
Implementation and Application of Automata,
J.-M. Champarnaud, D. Maurel, eds.,
(Revised papers from CIAA 2002, Tours, France, July 2002)
LNCS 2608, 57-66, 2003.
Copyright Springer-Verlag GmbH Berlin Heidelberg
The publication is available at
www.springerlink.com
A Framework for Testing Special-Purpose Memories.
IEEE Transactions on Computer-Aided Design,
21, 1459-1468, 2002.
pdf
Feedback-Free Circuits in the Algebra of Transients.
7th Int. Conf. on Implementation and Application of Automata CIAA 2003,
Tours, France, July 3 - 5, 2002.
See 2003.
Simulation of Gate Circuits in the Algebra of Transients.
7th Int. Conf. on Implementation and Application of Automata CIAA 2003,
Tours, France, July 3 - 5, 2002.
See 2003.
Partially Ordered Structures for Hazard Detection.
Special Session: The Many Lives of Lattice Theory,
Joint Mathematics Meetings,
San Diego, CA, January 6-9, 2002. (Invited Paper)
ps.gz
Hazard Algebras. In
Half Century of Automata Theory.
A. Salomaa, D. Wood, and S. Yu, eds.,
World Scientific, Singapore, 1-19, 2001.
ps.gz
A Characterization of De Morgan Algebras.
International Journal of Algebra and Computation,
11, 525-527, 2001.
pdf
Algebras for Hazard Detection,
31st IEEE International Symposium on Multiple-Valued Logic, ISMVL 2001,
Warsaw, Poland, May 22 - 24, 2001,
IEEE Computer Society, 3-12, 2001.
ps.gz
Sequential Machines. In
Encyclopedia of Computer Science, Fourth Edition.
A. Ralston, E. D. Reilly, D. Hemminger, eds.,
Grove's Dictionaries, Inc.,
New York, 1565-1569, 2000.
Delay-Insensitivity and Ternary Simulation.
Theoretical Computer Science,
45, 3-25, 2000.
pdf
Delay-Insensitivity and Semi-Modularity.
Formal Methods in System Design,
16, 187-214, 2000.
pdf
Automata of Asynchronous Behaviors.
Theoretical Computer Science,
231, 113-128, 2000.
pdf
Hazard Algebras (extended abstract).
Half Century of Automata Theory,
London, ON, July 26, 2000. See 2001.
De Morgan Bisemilattices.
30th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2000,
Portland, Oregon, May 23 - 25, 2000.
IEEE Computer Society, 173-178, 2000.
pdf
PhD Dissertation, Department of Electrical Engineering
Princeton University, Princeton, NJ, June 1962
Thesis supervisor:
E. J. McCluskey
PDF 27.8 MB
MASc Thesis, Department of Electrical Engineering
University of Toronto, Toronto, Ontario, March 1959
Thesis supervisors:
J. M. Ham and R. J. Kavanagh
Asynchronous Circuits
Springer-Verlag, New York, NY, 1995
Digital Networks
Prentice Hall, Englewood Cliffs, NJ, 1976
Topics in Asynchronous Circuit Theory,
in
Recent Advances in Formal Languages and Applications,
Studies in Computational Intelligence, Vol. 25,
Z. Esik, C. Martin-Vide, and V. Mitrana, eds.,
Springer,
2006.
Duality for Three: Ternary Symmetry in Process Spaces,
pp. 1-14 in
Theory is Forever,
Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday,
J. Karhumaki, H. Maurer, G. Paun, and G. Rozenberg, eds.,
LNCS 3113, Springer, 2004.
Algebras for Hazard Detection,
Beyond Two - Theory and Applications of Multiple-Valued Logic,
M. Fitting and E. Orlowska, eds.,
Physica-Verlag, Heidelberg
pp. 3-24, 2003.
(Reprinted from ISMVL 2001)
Hazard Algebras, pp. 1-19 in
Half Century of Automata Theory,
A. Salomaa, D. Wood, and S. Yu, eds.,
World Scientific, Singapore, 2001.
Semilattices of Fault Semiautomata,
pp. 3-15 in
Jewels are Forever,
J. Karhumaki, H. Maurer, G. Paun and G. Rozenberg, eds.,
Springer-Verlag, Berlin,
1999.
Blanket Algebra for Multiple-Valued Function Decomposition,
pp. 262-276 in
Algebraic Engineering ,
C. L. Nehaniv and M. Ito, eds.,
World Scientific Publishing Co. Pte. Ltd.,
1999.
"Component Automata and RAM Faults"
in Words, Languages and Combinatorics II
M. Ito and H. Jurgensen, eds.
World Scientific Publishing Co. Pte. Ltd., Singapore, pp. 49-67, 1994
"Sequential Machines"
in Encyclopedia of Computer Science, Third Edition
A. Ralston and E. D. Reilly, eds.
Van Nostrand Reinhold, New York, NY, pp. 1191-1195, 1993
also in
Encyclopedia of Computer Science and Engineering, Second Edition
A. Ralston, ed.
Van Nostrand Reinhold, New York, NY, pp. 1311-1316, 1983
and in
Encyclopedia of Computer Science,
A. Ralston and C.L. Meek, eds.
Petrocelli/Charter, New York, NY, pp. 1243-1248, 1976
in "Testability of Combinational Networks of CMOS Cells"
Developments in Integrated Circuit Testing
D. M. Miller, ed.
Academic Press, New York, NY, pp. 315-357, 1987
"Open Problems About Regular Languages"
in Formal Language Theory - Perspectives and Open Problems
R. V. Book, ed.
Academic Press, New York, NY, pp. 23-47, 1980
"Ternary Simulation of Binary Gate Networks"
in Modern Uses of Multiple-Valued Logic
J. M. Dunn and G. Epstein, eds.
D. Reidel Publishing Company, Dordrecht, Holland, pp. 39-50, 1977
"Synthesis of Sequential Machines"
in Systems and Computer Science
J. F. Hart and S. Takasu, eds.
University of Toronto Press, Toronto, Ontario, pp. 14-26, 1967
"Theoretical Considerations on Reliability Properties of Recursive
Triangular Switching Networks"
in Redundancy Techniques for Computing Systems
R. H. Wilcox and W. C. Mann, eds.
Spartan Books, Washington, DC, pp. 70-128, 1962
Representation of a Class of Nondeterministic Semiautomata by Canonical Words,
Theoretical Computer Science,
Vol. 356, pp. 46-57, 2006.
Representation of Semiautomata by Canonical Words and Equivalences,
Int. J. Foundations of Computer Science,
Vol. 16, No. 5, pp. 831-850, 2005.
Gate Circuits in the Algebra of Transients,
Theoretical Informatics and Applications,
Vol. 39, No. 1, pp. 67-91, January - March, 2005.
Involuted Semilattices and Uncertainty in Ternary Algebras,
International Journal of Algebra and Computation,
Vol. 14, No. 3, pp. 295-310, 2004.
Decomposition of Boolean Functions Specified by Cubes,
Journal of Multiple-Valued Logic and Soft Computing
vol. 9, pp. 377-417, 2003.
Simulation of Feedback-Free Circuits in the Algebra of Transients,
Int. J. Foundations of Computer Science,
vol. 14, no. 6, pp. 1033-1054, December 2003.
Hazard Algebras,
Formal Methods in System Design,
vol. 23, issue 3, pp. 223-256, November 2003.
True Concurrency in Models of Asynchronous Circuit Behavior,
Formal Methods in System Design,
vol. 22, issue 3, pp. 183-203, May 2003.
A Characterization of De Morgan Algebras,
International Journal of Algebra and Computation,
Vol. 11, No. 5, pp. 525-527, October 2001.
Delay-Insensitivity and Semi-Modularity,
Formal Methods in System Design,
Vol. 16, Issue 2, pp. 187-214, March 2000.
Download this report (compressed postscript).
Automata of Asynchronous Behaviors,
Theoretical Computer Science,
Vol. 231, Issue 1, pp. 113-128, 17 January 2000.
See also 1997 Conference Papers.
Delay-Insensitivity and Ternary Simulation,
Theoretical Computer Science,
Vol. 245, Issue 1, pp. 3-25, 17 August 2000.
Read the abstract
Download this report (compressed postscript)
REVISED January 30, 1998
Some Applications of Ternary Algebras,
Publicationes Mathematicae (Debrecen).
Vol. 54, Supplement, pp. 583-589, 1999.
Read the abstract
Download this report (compressed postscript).
A Characterization of Signed Hypergraphs and
Its Applications
to VLSI Minimization and Logic Synthesis,
Discrete Applied Mathematics,
Vol. 89, No. 1-3, December 1998.
Cluster-Cover: A Theoretical Framework for a Class
of VLSI-CAD Optimization Problems,
ACM Trans. on Design Automation of Electronic Systems,
Vol. 3, No. 1, pp. 76-107, January 1998.
Relative Liveness: From Intuition to Automated Verification
Formal Methods in System Design,
Vol. 12, No. 1, pp. 73-115, January 1998.
A Characterization of Finite Ternary Algebras,
International Journal of Algebra and Computation,
Vol. 7, No. 6,
pp. 713-721,
1997.
Testing for Bounded Faults in RAMs,
Journal of Electronic Testing: Theory and Applications,
Vol. 10, No. 3,
pp. 197-214,
June 1997.
An Algebra of Multiple Faults in RAMs,
Journal of Electronic Testing: Theory and Applications,
Vol. 8, No. 2,
pp. 129-142, April 1996.
"Applications of Automata and Languages to Testing"
Publicationes Mathematicae (Debrecen)
Vol. 48, No. 3-4, pp. 201-215, 1996
AMS Review
"Generalized Ternary Simulation of Sequential Circuits"
Theoretical Informatics and Applications
Vol. 28, No. 3-4, pp. 159-186, 1994
"An Efficient Algorithm for Constrained Encoding and Its Applications"
IEEE Transactions on Computer-Aided Design
Vol. 12, No. 12, pp. 1813-1826, December 1993
"On the Delay-Sensitivity of Gate Networks"
IEEE Transactions on Computers
Vol. 41, No. 10, pp. 1349-1360, November 1992
AMS Review
"Near-Optimal Tests for Classes of Write-Triggered Coupling Faults in RAMs"
J. Electronic Testing: Theory and Applications
Vol. 3, No. 3, pp. 251-264, August 1992
"A Model for Sequential Machine Testing and Diagnosis"
J. Electronic Testing: Theory and Applications
Vol. 3, No. 3, pp. 219-234, August 1992
"Consistency and Satisfiability of Waveform Timing Specifications"
Networks
Vol. 21, No. 1, pp. 91-107, January 1991
AMS Review
"Detection of Coupling Faults in RAMs"
J. Electronic Testing: Theory and Applications
Vol. 1, No. 2, pp. 151-162, May 1990
"Switch-Level Testability of the Dynamic CMOS PLA"
Integration, The VLSI Journal
Vol. 9, No. 1, pp. 49-80, February 1990
"A Unified Framework for Race Analysis of Asynchronous Networks"
J. Assoc. Comp. Mach.
Vol. 36, No. 1, pp. 20-45, January 1989
AMS Review
"An Optimistic Ternary Simulation of Gate Races"
Theoretical Computer Science
Vol. 61, No. 1, pp. 49-66, October 1988
AMS Review
"A Characterization of Ternary Simulation of Gate Networks"
IEEE Transactions on Computers
Vol. C-36, No. 11, pp. 1318-1327, November 1987
"Detection of Timing Problems in VLSI Circuits"
Congressus Numerantium
Vol. 56, pp. 7-18, March 1987
"Combinational Static CMOS Networks"
Integration, The VLSI Journal
Vol. 5, pp. 103-122, 1987
"Graph Congruences and Pair Testing"
Informatique Theorique et Applications
Vol. 20, No. 2, pp. 129-147, 1986
AMS Review
"On Serializability"
Int. J. Computer and Information Sc.
Vol. 14, No. 6, pp. 387-403, 1985
"On Generalized Locally Testable Languages"
Discrete Mathematics
Vol. 50, pp. 153-169, 1984
AMS Review
" Languages of R-Trivial Monoids"
J. Computer and System Sc.
Vol. 20, No. 1, pp. 32-49, February 1980
AMS Review
"On Equations for Regular Languages, Finite Automata, and
Sequential Networks"
Theoretical Computer Science
Vol. 10, pp. 19-35, 1980
AMS Review
"On a Ternary Model of Gate Networks"
IEEE Trans. on Computers
Vol. C-28, No. 3, pp. 178-184, March 1979
AMS Review
"The Dot-Depth Hierarchy of Star-Free Languages is Infinite"
J. Computer and System Sc.
Vol. 16, No. 1, pp. 37-55, February 1978
AMS Review
"A Generalization of Finiteness"
Semigroup Forum
Vol. 13, No. 3, pp. 239-251, 1977
"Run Languages"
Discrete Mathematics
Vol. 16, No. 4, pp. 299-307, December 1976
AMS Review
"Hierarchies of Aperiodic Languages"
Revue Francaise d'Automatique, Informatique et
Recherche Operationnelle
Vol. 10, No. 8, pp. 33-49, August 1976
AMS Review
"Practical Approach to Asynchronous Gate Networks"
Proc. IEE
Vol. 123, No. 6, pp. 495-498, June 1976
"Characterizations of Locally Testable Events"
Discrete Mathematics
Vol. 4, No. 3, pp. 243-271, March 1973
AMS Review
"On Translation Algorithms in Residue Number Systems"
IEEE Trans. on Computers
Vol. C-21, No. 12, pp. 1281-1285, December 1972
AMS Review
"Classification on Noncounting Events"
J. Computer and System Sc.
Vol. 5, No. 1, pp. 41-53, February 1971
AMS Review
"Dot-Depth of Star-Free Events"
J. Computer and System Sc.
Vol. 5, No. 1, pp. 1-16, February 1971
AMS Review
"General Properties of Star Height of Regular Events"
J. Computer and System Sc.
Vol. 4, No. 3, pp. 260-280, June 1970
AMS Review
"Sign Detection in Residue Number Systems"
IEEE Trans. on Computers
Vol. C-18, No. 4, pp. 313-320, April 1969
AMS Review
"On Decompositions of Regular Events"
J. Assoc. Comp. Mach.
Vol. 16, No. 1, pp. 132-144, January 1969
AMS Review
"Definite Asynchronous Sequential Circuits"
IEEE Trans. on Computers
Vol. C-17, No. 1, pp. 18-26, January 1968
"Roots of Star Events"
J. Assoc. Comp. Mach.
Vol. 14, No. 3, pp. 466-477, July 1967
AMS Review
"On Single-Loop Realizations of Sequential Machines"
Information and Control
Vol. 10, No. 3, pp. 292-314, March 1967
"An Approximate Method for Computing Blocking Probability in
Switching Networks"
IEEE Trans. on Communications Technology
Vol. COM-14, No. 2, pp. 85-93, April 1966
"On the Linearity of Sequential Machines"
IEEE Trans. on Electronic Computers
Vol. EC-15, No. 1, pp. 21-29, February 1966
"Some Problems in Relay Circuit Design"
IEEE Trans. on Electronic Computers
Vol. EC-14, No. 4, pp. 630-634, August 1965
"Regular Expressions for Linear Sequential Circuits"
IEEE Trans. on Electronic Computers
Vol. EC-14, No. 2, pp. 148-156, April 1965
"Regular Expressions from Sequential Circuits"
IEEE Trans. on Electronic Computers
Vol. EC-13, No. 6, pp. 741-744, December 1964
"On the Linearity of Autonomous Sequential Machines"
IEEE Trans. on Electronic Computers
Vol. EC-13, No. 6, pp. 673-679, December 1964
AMS Review
"Derivatives of Regular Expressions"
J. Assoc. Comp. Mach.
Vol. 11, No. 4, pp. 481-494, October 1964
AMS Review
"On the Construction of Sequential Machines from Regular Expressions"
IEEE Trans. on Electronic Computers
Vol. EC-12, No. 4, pp. 402-403, August 1963
"Signal Flow Graph Techniques for Sequential Circuit State Diagrams"
IEEE Trans. on Electronic Computers
Vol. EC-12, No. 2, pp. 67-76, April 1963
"A Survey of Regular Expressions and Their Applications"
IRE Trans. on Electronic Computers
Vol. EC-11, No. 3, pp. 324-335, June 1962
AMS Review
A Generalization of Shestakov's Function Decomposition Method,
29th IEEE International Symposium on Multiple-Valued Logic,
Freiburg, Germany, May 20 - 22, 1999.
Verification of CAM Tests for Input Stuck-at Faults,
1998 IEEE International Workshop on Memory Technology,
Design and Testing,
San Jose, CA, August 24 - 25, 1998.
An Approach to Modeling and Testing Memories and its Application to CAMs,
16th IEEE VLSI Test Symposium ,
Monterey, CA, April 27 - 30, 1998.
Read the abstract.
Download this paper.
Automata of Asynchronous Behaviors,
pp. 29-45 in D. Wood and S. Yu, eds.,
"Automata Implementation",
(Second International Workshop on Implementing Automata (WIA97)
London, Ontario, Canada, September 18-20, 1997: REVISED PAPERS)
Lecture Notes in Computer Science, LNCS 1436
Springer, Berlin, 1998.
Delay-Insensitivity and Ternary Simulation,
First International Conference on
Semigroups
and Algebraic Engineering,
Aizu-Wakamatsu City, Japan, March 24-28, 1997.
(invited paper, to be published in Theoretical Computer Science)
Read the abstract
Download this report (compressed postscript).
Blanket Algebra for Multiple-Valued Function Decomposition,
Proceedings of the International Workshop on Formal Languages
and Computer Systems,
Kyoto, Japan, March 18-21, 1997.
(to be published by World Scientific)
Read the abstract
Download this report (compressed postscript)
REVISED February 12, 1998).
"Some Applications of Ternary Algebras"
8th International Conference on
Automata and Formal Languages
Salgotarjan, Hungary, July 29 - August 2, 1996
Proceedings to be published in
Publicationes Mathematicae (Debrecen).
"A Framework for the Analysis and Design of Algorithms for a Class
of VLSI Optimization Problems"
Proceedings of the
Asia and South Pacific Design Automation Conference
Chiba, Japan, August 29-September 1, 1995
IEEE Computer Society Press, Los Alamitos, CA
pp. 67-74, 1995
"Composition of Multiple Faults in RAMs"
Records of the 1995 IEEE International Workshop on
Memory Technology, Design and Testing
San Jose, CA, August 7-8, 1995
IEEE Computer Society Press, Los Alamitos, CA
pp. 123-128, 1995
"Testing C-Elements Is Not Elementary"
Proceedings of the Second Working Conference on
Asynchronous Design Methodologies
London, England, May 30-31, 1995
IEEE Computer Society Press, Los Alamitos, CA
pp. 150-159, 1995
"Relative Liveness: From Intuition to Automated Verification"
Proceedings of the Second Working Conference on
Asynchronous Design Methodologies
London, England, May 30-31, 1995
IEEE Computer Society Press, Los Alamitos, CA
pp. 108-117, 1995
"An Automaton Theoretic Approach to Circuit Testing"
Abstracts of the Seventh Conference on
Automata and Formal Languages
Salgotarjan, Hungary, May 18-21, 1993
"Random Test Length for Bounded Faults in RAMs"
Proceedings of the
European Test Conference
Rotterdam, The Netherlands, April 19-24, 1993
IEEE Computer Society Press, Los Alamitos, CA
pp. 149-158, 1993
"Asynchronous Behaviours and Fundamental-Mode Realizations"
Seminar Report of the Seminar on
Automata Theory: Distributed Models
Dagstuhl, Germany, January 11-15, 1993
Dagstuhl Seminar Report 54
pp. 4-5, 1993
"Automaton-Theoretic Considerations in Circuit Testing"
Proceedings of the Second
Theoriedag
Kiel, Germany, October 2-3, 1992
4 pp.
"Efficient Constrained Encoding for VLSI Sequential Logic Synthesis"
Proceedings of the
European Design Automation Conference
Hamburg, Germany, September 7-10, 1992
IEEE Computer Society Press, Los Alamitos, CA
pp. 266-271, 1992
"Component Automata and RAM Faults"
Abstracts of the Second International Colloquium on
Words, Languages and Combinatorics
Kyoto, Japan, August 25-28, 1992
pp. 6-10, 1992
"Near-Optimal Tests for Classes of Coupling Faults in RAMs"
Poster Paper
International Test Conference
Nashville, TN, October 28 - November 1, 1991
"Near-Optimal Tests for Classes of Coupling Faults in RAMs"
Proceedings of the Fifth Technical Workshop on
New Directions in IC Testing
Ottawa, Ontario, August 1-2, 1991
"Recent Developments in the Design of Asynchronous Circuits"
Proceedings of the International Conference on
Fundamentals of Computation Theory
Szeged, Hungary, August 21-25, 1989
J. Csirik, J. Demetrovics, and F. Gecseg, eds.
Lecture Notes in Computer Science, Vol. 380
Springer-Verlag, Berlin
pp. 78-94, 1989
AMS Review
33.
B. F. Cockburn and J. A. Brzozowski
"Switch-Level Testability of the Dynamic CMOS PLA"
Proceedings of the Third Technical Workshop on
New Directions in IC Testing
Halifax, Nova Scotia, October 26-27, 1988
32.
J. A. Brzozowski and H. Jurgensen
"Probabilistic Diagnosis of Sequential Machines"
Proceedings of the Third Technical Workshop on
New Directions in IC Testing
Halifax, Nova Scotia, October 26-27, 1988
15 pp., 1988
31.
J. A. Brzozowski and H. Jurgensen
"Deterministic Diagnosis of Sequential Machines"
Proceedings of the Third Technical Workshop on
New Directions in IC Testing
Halifax, Nova Scotia, October 26-27, 1988
14 pp., 1988
"Probabilistic Diagnosis of Sequential Machines"
Proceedings of the Second Conference on
Automata Languages and Programming Systems
Salgotarjan, Hungary, May 23-26, 1988
F. Gecseg and I. Peak, eds.
Department of Mathematics, Karl Marx University of Economics
Budapest, Hungary
pp. 51-66, 1988
AMS Review
"Deterministic Diagnosis of Sequential Machines"
Proceedings of the Second Conference on
Automata Languages and Programming Systems
Salgotarjan, Hungary, May 23-26, 1988
F. Gecseg and I. Peak, eds.
Department of Mathematics, Karl Marx University of Economics
Budapest, Hungary
pp. 35-49, 1988
AMS Review
"A Model for Sequential Machine Testing"
Proceedings of the International Workshop on
New Directions in IC Testing
Winnipeg, Manitoba, April 8-10, 1987
17 pp., 1987
"On the Testability of Static CMOS Latches"
Technical Digest of the
Canadian Conference on VLSI
Montreal, Quebec, October 27-28, 1986
pp. 153-158, 1986
"An Optimistic Ternary Simulation of Gate Races"
Technical Digest of the
Canadian Conference on VLSI
Montreal, Quebec, October 27-28, 1986
pp. 67-72, 1986
"Detection of Timing Problems in VLSI Circuits"
Proceedings of the Sixteenth Manitoba Conference on
Numerical Mathematics and Computing
Winnipeg, Manitoba, October 2-4, 1986
Published in
Congressus Numerantium, Vol. 56
pp. 7-18, 1987
"Correspondence between Ternary Simulation and Binary Race
Analysis in Gate Networks"
Proceedings of the 13th International Colloquium on
Automata, Languages, and Programming
Rennes, France, July 15-19, 1986
L. Kott, ed.
Lecture Notes in Computer Science Vol. 226
Springer-Verlag, Berlin
pp. 69-78, 1986
"Combinational Static CMOS Networks"
Proceedings of the 1986
Aegean Workshop on Computing: VLSI Algorithms and Architectures
Loutraki, Greece, July 8-11, 1986
F. Makedon, K. Mehlhorn, T. Papatheodorou and P. Spirakis, eds.
Lecture Notes in Computer Science, Vol. 227
Springer-Verlag, Berlin
pp. 271-282, 1986
"Testability of Combinational Networks of CMOS Cells"
Poster Paper at the Ninth Annual IEEE Workshop on
Design for Testability
Vail, CO, April, 1986
"Testability of Combinational Networks of CMOS Cells"
Extended Version of Presentation at International Workshop on
New Directions in IC Testing
Victoria, British Columbia, March 18-20, 1986
Published in
Developments in Integrated Circuit Testing
D. M. Miller, ed.
Academic Press, New York, NY
pp. 315-357, 1987
"Design of Testable CMOS Cells"
Technical Digest of the
Canadian Conference on VLSI
Toronto, Ontario, November 4-5, 1985
pp. 225-228, 1985
"A Mathematical Model of Digital CMOS Networks"
Technical Digest of the
Canadian Conference on VLSI
Toronto, Ontario, November 4-5, 1985
pp. 117-120, 1985
"Developments in the Theory of Regular Languages"
Proceedings of the
IFIP Congress 80
Tokyo, Japan, October 6-9; Melbourne, Australia, October 14-17, 1980
S. Lavington, ed.
North Holland, Amsterdam
pp. 29-40, 1980
AMS Review
"Open Problems About Regular Languages"
Invited papers from a Symposium on Formal Language Theory
Santa Barbara, CA, December 10-14, 1979
Formal Language Theory - Perspectives and Open Problems
R. V. Book, ed.
Academic Press, New York, NY
pp. 23-47, 1980
"A Characterization of a Dot-Depth Two Analogue of
Generalized
Definite Languages"
Proceedings of the Sixth Colloquium on
Automata, Languages and Programming
Graz, Austria, July 16-20, 1979
H. Maurer, ed.
Lecture Notes in Computer Science, Vol. 71
Springer-Verlag, Berlin
pp. 230-244, 1979
AMS Review
"Ternary Simulation of Binary Gate Networks"
Invited Papers of the Fifth International Symposium on
Multiple-Valued Logic
Bloomington, IN, May 13-16, 1975
Modern Uses of Multiple-Valued Logic
J. M. Dunn and G. Epstein, eds.
D. Reidel Publishing Company, Dordrecht, Holland
pp. 39-50, 1977
"Models for Analysis of Races in Sequential Networks"
Proceedings of the Third Symposium on
Mathematical Foundations of Computer Science
Jadwisin, Poland, June 17-24, 1974
A. Blikle, ed.
Lecture Notes in Computer Science, Vol. 28
Springer-Verlag, Berlin
pp. 26-32, 1975
"Characterizations of Locally Testable Events"
IEEE Conference Record of the Twelfth Annual Symposium on
Switching and Automata Theory
East Lansing, MI, October 15-18, 1971
IEEE, New York, NY
pp. 166-176, 1971
"Regular-Like Expressions for Some Irregular Languages"
IEEE Conference Record of the Ninth Annual Symposium on
Switching and Automata Theory
Schenectady, NY, October 15-18, 1968
IEEE, New York, NY
pp. 278-286, 1968
"On Star-Free Events"
Proceedings of the
Hawaii International Conference on System Sciences
Honolulu, HI, January 29-31, 1968
B. K. Kinariwala and F. F. Kuo, eds.
University of Hawaii Press, Honolulu, HI
pp. 1-4, 1968
"On the Star Height of Regular Events"
IEEE Conference Record of the Eighth Annual Symposium on
Switching and Automata Theory
Austin, TX, October 18-20, 1967
IEEE, New York, NY
pp. 265-279, 1967
"On Decompositions of Regular Events"
IEEE Conference Record of the Eighth Annual Symposium on
Switching and Automata Theory
Austin, TX, October 18-20, 1967
IEEE, New York, NY
pp. 255-264, 1967
"Roots of Star Events"
IEEE Conference Record of the Seventh Annual Symposium on
Switching Circuit Theory and Logical Design
Berkeley, CA, October 26-28, 1966
IEEE, New York, NY
pp. 88-95, 1966
"An Approximate Method for Computing Blocking Probability in
Switching Networks"
IEEE International Convention Record of
1966 IEEE Communication Conference
New York, NY, March 21-24, 1966
IEEE, New York, NY
paper CP 66-101, 1966
"On Single-Loop Realizations of Automata"
IEEE Conference Record of the Sixth Annual Symposium on
Switching Circuit Theory and Logical Design
Ann Arbor, MI, October 6-8, 1965
IEEE, New York, NY
pp. 84-93, 1965
"Synthesis of Sequential Machines"
Proceedings of a Conference on
Systems and Computer Science
London, Ontario, September 10-11, 1965
J. F. Hart and S. Takasu, eds.
University of Toronto Press, Toronto, Ontario
pp. 14-26, 1967
AMS Review
"On the Linearity of Sequential Machines"
Proceedings of the Fifth Annual Symposium on
Switching Circuit Theory and Logical Design
Princeton, NJ, November 11-13, 1964
IEEE, New York, NY
pp. 197-208, 1964
"Regular Expressions for Linear Sequential Circuits"
Proceedings of the First Allerton Conference on
Circuit and System Theory
Monticello, IL, November 15-17, 1963
J. B. Cruz and J. C. Hofer, eds.
University of Illinois, Urbana, IL
pp. 406-426, 1963
"Canonical Regular Expressions and Minimal
State Graphs for Definite Events"
Proceedings of the Symposium on
Mathematical Theory of Automata
New York, NY, April 24-26, 1962
J. Fox, ed., MRI Symposia Series, Vol. 12
Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, NY
pp. 529-561, 1963
AMS Review
"Theoretical Considerations on Reliability Properties of Recursive
Triangular Switching Networks"
Proceedings of the Symposium on
Redundancy Techniques for Computing Systems
Washington, DC, February 6-7, 1962
R. H. Wilcox and W. C. Mann, eds.
Spartan Books, Washington, DC
pp. 70-128, 1962