Juraj Hromkovic

Theor. Comput. Sci., 2015

Why the Concept of Computational Complexity is Hard for Verifiable Mathematics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Homo Informaticus.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

2014

The string guessing problem as a method to prove lower bounds on the advice complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

On the advice complexity of the online L(2, 1)-coloring problem on paths and cycles.

[BibT_eX]

[DOI]

Maria Paola Bianchi

Sacha Krug

Theor. Comput. Sci., 2014

Online Coloring of Bipartite Graphs with and without Advice.

[BibT_eX]

[DOI]

Maria Paola Bianchi

Lucia Keller

Algorithmica, 2014

On the Power of Advice and Randomization for the Disjoint Path Allocation Problem.

[BibT_eX]

[DOI]

Kfir Barhum

Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

A Technique to Obtain Hardness Results for Randomized Online Algorithms - A Survey.

[BibT_eX]

[DOI]

Dennis Komm

Proceedings of the Computing with New Resources, 2014

2013

Determinism vs. Nondeterminism for Two-Way Automata: Representing the Meaning of States by Logical Formulæ.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2013

On the Advice Complexity of the Online <i>L</i>(2, 1)-Coloring Problem on Paths and Cycles.

[BibT_eX]

[DOI]

Maria Paola Bianchi

Sacha Krug

Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

Konzepte und Inhalte eines Fachs Informatik.

[BibT_eX]

Jürg Kohlas

Carl August Zehnder

Proceedings of the informatik@gymnasium - Ein Entwurf für die Schweiz., 2013

Die Bildungsziele.

[BibT_eX]

Jürg Kohlas

Proceedings of the informatik@gymnasium - Ein Entwurf für die Schweiz., 2013

Was ist Informatik?

[BibT_eX]

Jürg Kohlas

Proceedings of the informatik@gymnasium - Ein Entwurf für die Schweiz., 2013

2012

On the approximability and hardness of minimum topic connected overlay and its special instances.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Steiner tree reoptimization in graphs with sharpened triangle inequality.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2012

On the Power of Randomness versus Advice in Online Computation.

[BibT_eX]

[DOI]

Proceedings of the Languages Alive, 2012

Einführung in die Programmierung mit LOGO - Lehrbuch für Unterricht und Selbststudium (2. Aufl.).

[BibT_eX]

[DOI]

Vieweg+Teubner, ISBN: 978-3-8348-2266-6, 2012

2011

Ambiguity and Communication.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Theory Comput. Syst., 2011

Fehlerkorrigierende Codes - Ein Unterrichtsbeispiel zum gelenkten entdeckenden Lernen.

[BibT_eX]

Editorial.

[BibT_eX]

[DOI]

J. Interconnect. Networks, 2011

On the Hardness of Reoptimization with Multiple Given Solutions.

[BibT_eX]

[DOI]

Andreas Sprock

Fundam. Informaticae, 2011

On the Approximability of Minimum Topic Connected Overlay and Its Special Instances.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Why Teaching Informatics in Schools Is as Important as Teaching Mathematics and Natural Sciences.

[BibT_eX]

[DOI]

Proceedings of the Informatics in Schools. Contributing to 21st Century Education, 2011

Knowing All Optimal Solutions Does Not Help for TSP Reoptimization.

[BibT_eX]

[DOI]

Andreas Sprock

Proceedings of the Computation, 2011

Improved Approximations for Hard Optimization Problems via Problem Instance Classification.

[BibT_eX]

[DOI]

Tobias Mömke

Proceedings of the Rainbow of Computer Science, 2011

2010

On probabilistic pushdown automata.

[BibT_eX]

[DOI]

Inf. Comput., 2010

Preface.

[BibT_eX]

[DOI]

Borislav Suster

Eduard Toman

Fundam. Informaticae, 2010

Information Complexity of Online Problems.

[BibT_eX]

[DOI]

Rastislav Královic

Richard Královic

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Algorithmics - Is There Hope for a Unified Theory?

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2010

The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

2009

On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's.

[BibT_eX]

[DOI]

Holger Petersen

Theor. Comput. Sci., 2009

Reoptimization of Steiner trees: Changing the terminal set.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Lower Bounds on the Size of Sweeping Automata.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2009

Sieben Wunder der Informatik - Eine Reise an die Grenze des Machbaren mit Aufgaben und Lösungen (2. Aufl.).

[BibT_eX]

[DOI]

Teubner, ISBN: 978-3-8351-0172-2, 2009

Algorithmic Adventures - From Knowledge to Magic.

[BibT_eX]

[DOI]

Springer, ISBN: 978-3-540-85985-7, 2009

2008

On k-connectivity problems with sharpened triangle inequality.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2008

Reoptimization of Steiner Trees.

[BibT_eX]

[DOI]

Davide Bilò

Proceedings of the Algorithm Theory, 2008

On the Hardness of Reoptimization.

[BibT_eX]

[DOI]

Tobias Mömke

Peter Widmayer

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Creating and Testing Textbooks for Secondary Schools.

[BibT_eX]

[DOI]

Karin Freiermuth

Proceedings of the Informatics Education - Supporting Computational Thinking, Third International Conference on Informatics in Secondary Schools, 2008

On the Hardness of Determining Small NFA's and of Proving Lower Bounds on Their Sizes.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 12th International Conference, 2008

Lehrbuch Informatik - Vorkurs Programmieren, Geschichte und Begriffsbildung, Automatenentwurf.

[BibT_eX]

[DOI]

Vieweg, ISBN: 978-3-8348-0620-8, 2008

2007

Stability of Approximation.

[BibT_eX]

[DOI]

Sebastian Seibert

Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Comparing the size of NFAs with and without epsilon-transitions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

The Parameterized Approximability of TSP with Deadlines.

[BibT_eX]

[DOI]

Joachim Kneis

Joachim Kupke

Theory Comput. Syst., 2007

Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 2007

On the Approximability of TSP on Local Modifications of Optimally Solved Instances.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 2007

Efficient Algorithms for the Spoonerism Problem.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms, 4th International Conference, 2007

Theoretische Informatik - formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie, 3. Auflage.

[BibT_eX]

Leitfäden der Informatik, Teubner, ISBN: 978-3-8351-0043-5, 2007

2006

On the Stability of Approximation for Hamiltonian Path Problems.

[BibT_eX]

[DOI]

Algorithmic Oper. Res., 2006

On the Approximation Hardness of Some Generalizations of TSP.

[BibT_eX]

[DOI]

Joachim Kneis

Joachim Kupke

Proceedings of the Algorithm Theory, 2006

Contributing to General Education by Teaching Informatics.

[BibT_eX]

[DOI]

Proceedings of the Informatics Education - The Bridge between Using and Understanding Computers, International Conference in Informatics in Secondary Schools, 2006

Reusing Optimal TSP Solutions for Locally Modified Input Instances.

[BibT_eX]

[DOI]

Proceedings of the Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), 2006

Sieben Wunder der Informatik - eine Reise an die Grenze des Machbaren mit Aufgaben und Lösungen.

[BibT_eX]

Teubner, ISBN: 978-3-8351-0078-7, 2006

2005

Design and Analysis of Randomized Algorithms - Introduction to Design Paradigms

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-27903-7, 2005

On the power of randomized multicounter machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

NFAs With and Without <i>epsilon</i>-Transitions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Communication Complexity Method for Proving Lower Bounds on Descriptional Complexity in Automata and Formal Language Theory.

[BibT_eX]

Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30, 2005

Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-26663-1, 2005

2004

Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, Second Edition

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-05269-3, 2004

On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

On multi-partition communication complexity.

[BibT_eX]

[DOI]

Inf. Comput., 2004

Stability of Approximation in Discrete Optimization.

[BibT_eX]

[DOI]

Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

2003

Nondeterministic Communication with a Limited Number of Advice Bits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

The Power of Nondeterminism and Randomness for Oblivious Branching Programs.

[BibT_eX]

[DOI]

Martin Sauerhoff

Theory Comput. Syst., 2003

Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

On k-Edge-Connectivity Problems with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002

Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Descriptional Complexity of Finite Automata: Concepts and Open Problems.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2002

Communication Complexity Method for Measuring Nondeterminism in Finite Automata.

[BibT_eX]

[DOI]

Inf. Comput., 2002

2001

Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-04616-6, 2001

On the power of Las Vegas II: Two-way finite automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Foreword.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Zufall und zufallsgesteuerte Algorithmen.

[BibT_eX]

Translating Regular Expressions into Small -Free Nondeterministic Finite Automata.

[BibT_eX]

[DOI]

Sebastian Seibert

Thomas Wilke

J. Comput. Syst. Sci., 2001

On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata.

[BibT_eX]

[DOI]

Inf. Comput., 2001

On Multipartition Communication Complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Preface.

[BibT_eX]

[DOI]

Ondrej Sýkora

Discret. Appl. Math., 2001

Randomized Communication Protocols (A Survey).

[BibT_eX]

[DOI]

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms.

[BibT_eX]

[DOI]

Kathleen Steinhöfel

Peter Widmayer

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

On the Power of Randomized Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

Descriptional Complexity of Regular Languages (Concepts and Open Problems).

[BibT_eX]

Proceedings of the Third International Workshop on Descriptional Complexity of Automata, Grammars and Related Structures - DCAGRS 2001, Vienna, Austria, July 20, 2001

Algorithmischen Konzepte der Informatik - Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie

[BibT_eX]

Teubner, ISBN: 3-519-00332-5, 2001

Algorithmics for hard problems - introduction to combinatorial optimization, randomization, approximation, and heuristics.

[BibT_eX]

Springer, ISBN: 978-3-540-66860-2, 2001

2000

Approximation algorithms for the TSP with sharpened triangle inequality.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Measures of Nondeterminism in Finite Automata

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs.

[BibT_eX]

[DOI]

Martin Sauerhoff

Proceedings of the STACS 2000, 2000

An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Introduction: Workshop on Boolean Functions and Applications.

[BibT_eX]

Ingo Wegener

Proceedings of the ICALP Workshops 2000, 2000

1999

Communication complexity and lower bounds on multilective computations.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1999

Some Constributions of the Study of Abstract Communication Complexity to Other Areas of Computer Science.

[BibT_eX]

[DOI]

ACM Comput. Surv., 1999

Stability of Approximation Algorithms for Hard Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM '99, Theory and Practice of Informatics, 26th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 27, 1999

Stability of Approximation Algorithms and the Knapsack Problem.

[BibT_eX]

Proceedings of the Jewels are Forever, 1999

1998

Effective Systolic Algorithms for Gossiping in Cycles.

[BibT_eX]

[DOI]

Parallel Process. Lett., 1998

1997

Complexity: A Language-Theoretic Point of View.

[BibT_eX]

[DOI]

Cristian Calude

Proceedings of the Handbook of Formal Languages, 1997

Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes.

[BibT_eX]

[DOI]

Inf. Comput., 1997

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Translating Regular Expressions into Small epsilon-Free Nondeterministic Finite Automata.

[BibT_eX]

[DOI]

Sebastian Seibert

Thomas Wilke

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Las Vegas Versus Determinism for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Communication Complexity and Sequential Compuation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Two Lower Bounds on Computational Complexity of Infinite Words.

[BibT_eX]

[DOI]

Juhani Karhumäki

Proceedings of the New Trends in Formal Languages, 1997

Communication Complexity and Parallel Computing.

[BibT_eX]

[DOI]

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-03442-2, 1997

1996

A Comparison of Two Lower-Bound Methods for Communication Complexity.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Theor. Comput. Sci., 1996

Two Lower Bounds on Distributive Generation of Languages.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1996

Dissemination of Information in Vertex-Disjoint Paths Mode.

[BibT_eX]

[DOI]

Ralf Klasing

Elena Stöhr

Comput. Artif. Intell., 1996

1995

On Embeddings in Cycles

[BibT_eX]

[DOI]

Inf. Comput., May, 1995

A Nonlinear Lower Bound on the Practical Combinational Complexity.

[BibT_eX]

[DOI]

Xaver Gubás

Juraj Waczulík

Theor. Comput. Sci., 1995

Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs.

[BibT_eX]

[DOI]

Inf. Comput., 1995

On the Sizes of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

Effective Systolic Algorithms for Gossiping in Cycles and Two-Dimensional Grids (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

On the Communication Complexity of Distributive Language Generation.

[BibT_eX]

Proceedings of the Developments in Language Theory II, 1995

1994

Deterministic versus Nondeterministic Space in Terms of Synchronized Alternating Machines.

[BibT_eX]

[DOI]

Branislav Rovan

Anna Slobodová

Theor. Comput. Sci., 1994

Some Hierarchies for the Communication Complexity Measures of Cooperating Grammar Systems.

[BibT_eX]

[DOI]

Jarkko Kari

Lila Kari

Theor. Comput. Sci., 1994

Note on Optimal Gossiping in Some Weak-Connected Graphs.

[BibT_eX]

[DOI]

Claus-Dieter Jeschke

Theor. Comput. Sci., 1994

The Complexity of Systolic Dissemination of Information in Interconnection Networks.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1994

Optimal algorithms for dissemination of information in generalized communication modes.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1994

Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1994

Two Lower Bounds on Computational Complexity of Infinite Word Generation.

[BibT_eX]

Juhani Karhumäki

Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

Comparing Descriptional and Computational Complexity of Infinite Words.

[BibT_eX]

[DOI]

Juhani Karhumäki

Arto Lepistö

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

Lower Bounds on Systolic Array Computations and the Optimality of Kung's Convolution Algorithm.

[BibT_eX]

[DOI]

Juraj Procházka

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

1993

A Note on Realtime One-Way Synchronized Alternating One-Counter Automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

Optimal Algorithms for Dissemination of Information in Some Interconnection Networks.

[BibT_eX]

[DOI]

Claus-Dieter Jeschke

Algorithmica, 1993

Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks.

[BibT_eX]

[DOI]

Ralf Klasing

Elena Stöhr

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

1992

Branching Programs Provide Lower Bounds on the Areas of Multilective Deterministic and Nondeterministic VLSI-Circuits

[BibT_eX]

[DOI]

Inf. Comput., February, 1992

Lower Bounds on the Area Complexity of Boolean Circuits.

[BibT_eX]

[DOI]

Sergej A. Lozkin

Andrej I. Rybko

Alexander A. Sapozhenko

Nadezda A. Skalikova

Theor. Comput. Sci., 1992

Abstract symbol systems - an exercise of the bottom-up approach in artificial intelligence.

[BibT_eX]

[DOI]

Jozef Kelemen

Juraj Waczulík

J. Exp. Theor. Artif. Intell., 1992

On the Power of One-Way Synchronized Alternating Machines with Small Space.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1992

Topology of Parallel Networks and Computational Complexity (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

On Embedding Interconnection Networks into Rings of Processors.

[BibT_eX]

[DOI]

Proceedings of the PARLE '92: Parallel Architectures and Languages Europe, 1992

Optimal Algorithms for Disemination of Information in Generalized Communication Modes.

[BibT_eX]

[DOI]

Proceedings of the PARLE '92: Parallel Architectures and Languages Europe, 1992

The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems).

[BibT_eX]

[DOI]

Proceedings of the Informatik, Festschrift zum 60. Geburtstag von Günter Hotz, 1992

1991

Nonlinear Lower Bounds on the Number of Processors of Circuits with Sublinear Separators

[BibT_eX]

[DOI]

Inf. Comput., December, 1991

On Problems for Which no Oracle Can Help.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1991

Branching programs provide lower bounds on the area of VLSI circuits.

[BibT_eX]

[DOI]

Kybernetika, 1991

On the power of two-dimensional synchronized alternating finite automata.

[BibT_eX]

Fundam. Informaticae, 1991

Variable Multihead Machines.

[BibT_eX]

Ladislav Janiga

Václav Koubek

J. Inf. Process. Cybern., 1991

On the power of synchronization in parallel computations.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1991

The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1991, 1991

Nonlinear Lower Bounds on the Number of Processors of Circuits with Sublinear Separators (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990

Optimal Algorithms for Dissemination of Information in Some Interconnection Networks (Extended Abstract).

[BibT_eX]

[DOI]

Claus-Dieter Jeschke

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989

A Leaf-Size Hierarchy of Two-Dimensional Alternating Turing Machines.

[BibT_eX]

[DOI]

Itsuo Takanami

Theor. Comput. Sci., 1989

Tradeoffs for Language Recognition on Alternating Machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

Lower Bounds for Language Recognition on Two-Dimensional Alternating Multihead Machines.

[BibT_eX]

[DOI]

Itsuo Takanami

J. Comput. Syst. Sci., 1989

The knowledge on information content of problems provides much useful information to circuit designers.

[BibT_eX]

Bull. EATCS, 1989

On the Power of Synchronization in Parallel Computations.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

1988

The Advantages of a New Approach to Defining the Communication Complexity for VLSI.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1988

Graph Controlled Table Lindenmayer Systems.

[BibT_eX]

Erika Kupková

J. Inf. Process. Cybern., 1988

A candidate for nonlinear lower bound on the combinatorial complexity.

[BibT_eX]

Bull. EATCS, 1988

Branching Programs as a Tool for Proving Lower Bounds on VLSI Computations and Optimal Algorithms for Systolic Arrays.

[BibT_eX]

[DOI]

Juraj Procházka

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1987

Reversal-Bounded Nondeterministic Multicounter Machines and Complementation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1987

Zerotesting bounded one-way multicounter machines.

[BibT_eX]

[DOI]

Kybernetika, 1987

Reversal Complexity of Multicounter and Multihead Machines.

[BibT_eX]

[DOI]

Proceedings of the STACS 87, 1987

1986

Communication Complexity Hierarchy.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

Hierarchy of reversal bounded one-way multicounter machines.

[BibT_eX]

[DOI]

Kybernetika, 1986

A New Approach to Defining the Complexity for VLSI.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Lower bound techniques for VLSI algorithms.

[BibT_eX]

[DOI]

Proceedings of the Trends, 1986

Tradeoffs for Language Recognition on Parallel Computing Models.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985

On the number of monotonic functions from two-valued logic to k-valued logic.

[BibT_eX]

[DOI]

Kybernetika, 1985

On the Power of Alternation in Automata Theory.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1985

Linear Lower Bounds on Unbounded Fan-In Boolean Circuits.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

Alternating Multicounter Machines with Constant Number of Reversals.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

Fooling a Two-Way Nondeterministic Multihead Automaton with Reversal Number Restriction.

[BibT_eX]

[DOI]

Acta Informatica, 1985

1984

A note on the "Comuunication Complexity" paper by Papadimitriou and Sipser.

[BibT_eX]

Bull. EATCS, 1984

On the power of Yao-Rivest technique.

[BibT_eX]

Bull. EATCS, 1984

On the Power of Alternation in Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Hierarchy of Reversal and Zerotesting Bounded Multicounter Machines.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1984

1983

One-Way Simple Multihead Finite Automata are not Closed Under Concatenation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1983

On-Way Multihead Deterministic Finite Automata.

[BibT_eX]

[DOI]

Acta Informatica, 1983

1982

Multihead Finite State Automata and Concatenation.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1982

1981

Closure Properties of the Family of Languages Recognized by One-Way Two-Head Deterministic Finite State Automata.

[BibT_eX]

[DOI]