Juraj Hromkovic

According to our database1, Juraj Hromkovic
  • authored at least 201 papers between 1981 and 2017.
  • has a "Dijkstra number"2 of four.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Algorithmic Thinking from the Start.
Bulletin of the EATCS, 2017

What One Has to Know When Attacking P vs. NP (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016
Advice Complexity of the Online Search Problem.
CoRR, 2016

The Complexity of Paging Against a Probabilistic Adversary.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Online Graph Coloring with Advice and Randomized Adversary - (Extended Abstract).
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

On the Power of Laconic Advice in Communication Complexity.
Proceedings of the SOFSEM 2016: Theory and Practice of Computer Science, 2016

Advice Complexity of the Online Search Problem.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Combining the Power of Python with the Simplicity of Logo for a Sustainable Computer Science Education.
Proceedings of the Informatics in Schools: Improvement of Informatics Knowledge and Perception, 2016

2015
Corrigendum to "On the approximability and hardness of minimum topic connected overlay and its special instances" [Theoret. Comput. Sci. 429(2012) 144-154].
Theor. Comput. Sci., 2015

Why the Concept of Computational Complexity is Hard for Verifiable Mathematics.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Homo Informaticus.
Bulletin of the EATCS, 2015

On the Size of Two-Way Reasonable Automata for the Liveness Problem.
Proceedings of the Developments in Language Theory - 19th International Conference, 2015

2014
The string guessing problem as a method to prove lower bounds on the advice complexity.
Theor. Comput. Sci., 2014

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

Online Coloring of Bipartite Graphs with and without Advice.
Algorithmica, 2014

On the Power of Advice and Randomization for the Disjoint Path Allocation Problem.
Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

A Technique to Obtain Hardness Results for Randomized Online Algorithms - A Survey.
Proceedings of the Computing with New Resources, 2014

2013
Determinism vs. Nondeterminism for Two-Way Automata: Representing the Meaning of States by Logical Formulæ.
Int. J. Found. Comput. Sci., 2013

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

On the Advice Complexity of the Online L(2, 1)-Coloring Problem on Paths and Cycles.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

2012
On the approximability and hardness of minimum topic connected overlay and its special instances.
Theor. Comput. Sci., 2012

Steiner tree reoptimization in graphs with sharpened triangle inequality.
J. Discrete Algorithms, 2012

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Determinism vs. Nondeterminism for Two-Way Automata - Representing the Meaning of States by Logical Formulæ.
Proceedings of the Developments in Language Theory - 16th International Conference, 2012

Online Coloring of Bipartite Graphs with and without Advice.
Proceedings of the Computing and Combinatorics - 18th Annual International Conference, 2012

On the Power of Randomness versus Advice in Online Computation.
Proceedings of the Languages Alive, 2012

Einführung in die Programmierung mit LOGO - Lehrbuch für Unterricht und Selbststudium (2. Aufl.).
Vieweg+Teubner, ISBN: 978-3-8348-2266-6, 2012

2011
Ambiguity and Communication.
Theory Comput. Syst., 2011

Fehlerkorrigierende Codes - Ein Unterrichtsbeispiel zum gelenkten entdeckenden Lernen.
LOG IN, 2011

Editorial.
Journal of Interconnection Networks, 2011

On the Hardness of Reoptimization with Multiple Given Solutions.
Fundam. Inform., 2011

On the Approximability and Hardness of Minimum Topic Connected Overlay and Its Special Instances
CoRR, 2011

On the Approximability of Minimum Topic Connected Overlay and Its Special Instances.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Why Teaching Informatics in Schools Is as Important as Teaching Mathematics and Natural Sciences.
Proceedings of the Informatics in Schools. Contributing to 21st Century Education, 2011

Knowing All Optimal Solutions Does Not Help for TSP Reoptimization.
Proceedings of the Computation, 2011

Improved Approximations for Hard Optimization Problems via Problem Instance Classification.
Proceedings of the Rainbow of Computer Science, 2011

2010
On probabilistic pushdown automata.
Inf. Comput., 2010

Preface.
Fundam. Inform., 2010

Information Complexity of Online Problems.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Algorithmics - Is There Hope for a Unified Theory?
Proceedings of the Computer Science, 2010

The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality.
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.
Theor. Comput. Sci., 2009

Reoptimization of Steiner trees: Changing the terminal set.
Theor. Comput. Sci., 2009

On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks.
SIAM J. Discrete Math., 2009

Lower Bounds on the Size of Sweeping Automata.
Journal of Automata, Languages and Combinatorics, 2009

Ambiguity and Communication
CoRR, 2009

Ambiguity and Communication.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Sieben Wunder der Informatik - Eine Reise an die Grenze des Machbaren mit Aufgaben und Lösungen (2. Aufl.).
Teubner, ISBN: 978-3-8351-0172-2, 2009

Algorithmic Adventures - From Knowledge to Magic.
Springer, ISBN: 978-3-540-85985-7, 2009

2008
On k-connectivity problems with sharpened triangle inequality.
J. Discrete Algorithms, 2008

Reoptimization of Steiner Trees.
Proceedings of the Algorithm Theory, 2008

On the Hardness of Reoptimization.
Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Creating and Testing Textbooks for Secondary Schools.
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.
Proceedings of the Developments in Language Theory, 12th International Conference, 2008

Lehrbuch Informatik - Vorkurs Programmieren, Geschichte und Begriffsbildung, Automatenentwurf.
Vieweg, ISBN: 978-3-8348-0620-8, 2008

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

Comparing the size of NFAs with and without epsilon-transitions.
Theor. Comput. Sci., 2007

The Parameterized Approximability of TSP with Deadlines.
Theory Comput. Syst., 2007

Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms.
Algorithmic Operations Research, 2007

On the Approximability of TSP on Local Modifications of Optimally Solved Instances.
Algorithmic Operations Research, 2007

Efficient Algorithms for the Spoonerism Problem.
Proceedings of the Fun with Algorithms, 4th International Conference, 2007

2006
On the Stability of Approximation for Hamiltonian Path Problems.
Algorithmic Operations Research, 2006

On the Approximation Hardness of Some Generalizations of TSP.
Proceedings of the Algorithm Theory, 2006

Contributing to General Education by Teaching Informatics.
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.
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.
Teubner, ISBN: 978-3-8351-0078-7, 2006

2005
Design and Analysis of Randomized Algorithms - Introduction to Design Paradigms
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-27903-7, 2005

On the power of randomized multicounter machines.
Theor. Comput. Sci., 2005

On the Stability of Approximation for Hamiltonian Path Problems.
Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

NFAs With and Without epsilon-Transitions.
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.
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
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
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.
Theor. Comput. Sci., 2004

On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata.
J. Comput. Syst. Sci., 2004

On multi-partition communication complexity.
Inf. Comput., 2004

Stability of Approximation in Discrete Optimization.
Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

2003
Nondeterministic Communication with a Limited Number of Advice Bits.
SIAM J. Comput., 2003

The Power of Nondeterminism and Randomness for Oblivious Branching Programs.
Theory Comput. Syst., 2003

Nondeterminism versus Determinism for Two-Way Finite Automata: Generalizations of Sipser's Separation.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Pushdown Automata and Multicounter Machines, a Comparison of Computation Modes.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

On k-Edge-Connectivity Problems with Sharpened Triangle Inequality.
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.
Theor. Comput. Sci., 2002

Descriptional Complexity of Finite Automata: Concepts and Open Problems.
Journal of Automata, Languages and Combinatorics, 2002

Communication Complexity Method for Measuring Nondeterminism in Finite Automata.
Inf. Comput., 2002

On the Hardness of Constructing Minimal 2-Connected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality.
Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

2001
Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics
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.
Theor. Comput. Sci., 2001

Foreword.
Theor. Comput. Sci., 2001

Zufall und zufallsgesteuerte Algorithmen.
LOG IN, 2001

Translating Regular Expressions into Small -Free Nondeterministic Finite Automata.
J. Comput. Syst. Sci., 2001

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

On Multipartition Communication Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2001

Preface.
Discrete Applied Mathematics, 2001

On Multipartition Communication Complexity.
Proceedings of the STACS 2001, 2001

Randomized Communication Protocols (A Survey).
Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms.
Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

On the Power of Randomized Pushdown Automata.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

Descriptional Complexity of Regular Languages (Concepts and Open Problems).
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
Teubner, ISBN: 3-519-00332-5, 2001

Algorithmics for hard problems - introduction to combinatorial optimization, randomization, approximation, and heuristics.
Springer, ISBN: 978-3-540-66860-2, 2001

2000
Approximation algorithms for the TSP with sharpened triangle inequality.
Inf. Process. Lett., 2000

Measures of Nondeterminism in Finite Automata
Electronic Colloquium on Computational Complexity (ECCC), 2000

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition
Electronic Colloquium on Computational Complexity (ECCC), 2000

Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs.
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.
Proceedings of the STACS 2000, 2000

Introduction: Workshop on Boolean Functions and Applications.
ICALP Satellite Workshops, 2000

Measures of Nondeterminism in Finite Automata.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem.
Proceedings of the Algorithms and Complexity, 4th Italian Conference, 2000

1999
Communication complexity and lower bounds on multilective computations.
ITA, 1999

Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem
Electronic Colloquium on Computational Complexity (ECCC), 1999

On the Power of Las Vegas II: Two-Way Finite Automata
Electronic Colloquium on Computational Complexity (ECCC), 1999

Some Constributions of the Study of Abstract Communication Complexity to Other Areas of Computer Science.
ACM Comput. Surv., 1999

Stability of Approximation Algorithms for Hard Optimization Problems.
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

On the Power of Las Vegas II. Two-Way Finite Automata.
Proceedings of the Automata, 1999

Stability of Approximation Algorithms and the Knapsack Problem.
Proceedings of the Jewels are Forever, 1999

1998
Effective Systolic Algorithms for Gossiping in Cycles.
Parallel Processing Letters, 1998

Communication Complexity and Lower Bounds on Multilective Computations.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

1997
Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes.
Inf. Comput., 1997

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations
Electronic Colloquium on Computational Complexity (ECCC), 1997

Translating Regular Expressions into Small epsilon-Free Nondeterministic Finite Automata.
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.
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.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Two Lower Bounds on Computational Complexity of Infinite Words.
Proceedings of the New Trends in Formal Languages, 1997

Communication Complexity and Parallel Computing.
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.
Theor. Comput. Sci., 1996

Two Lower Bounds on Distributive Generation of Languages.
Fundam. Inform., 1996

Dissemination of Information in Vertex-Disjoint Paths Mode.
Computers and Artificial Intelligence, 1996

Nondeterministic Communication with a Limited Number of Advice Bits.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
On Embeddings in Cycles
Inf. Comput., May, 1995

A Nonlinear Lower Bound on the Practical Combinational Complexity.
Theor. Comput. Sci., 1995

Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs.
Inf. Comput., 1995

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

Effective Systolic Algorithms for Gossiping in Cycles and Two-Dimensional Grids (Extended Abstract).
Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

On the Communication Complexity of Distributive Language Generation.
Proceedings of the Developments in Language Theory II, 1995

1994
Deterministic versus Nondeterministic Space in Terms of Synchronized Alternating Machines.
Theor. Comput. Sci., 1994

Some Hierarchies for the Communication Complexity Measures of Cooperating Grammar Systems.
Theor. Comput. Sci., 1994

Note on Optimal Gossiping in Some Weak-Connected Graphs.
Theor. Comput. Sci., 1994

The Complexity of Systolic Dissemination of Information in Interconnection Networks.
ITA, 1994

Optimal algorithms for dissemination of information in generalized communication modes.
Discrete Applied Mathematics, 1994

Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes (Extended Abstract).
Proceedings of the Algorithm Theory, 1994

Two Lower Bounds on Distributive Generation of Languages.
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

A Comparison of Two Lower Bound Methods for Communication Complexity.
Proceedings of the Mathematical Foundations of Computer Science 1994, 1994

Two Lower Bounds on Computational Complexity of Infinite Word Generation.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

The Complexity of Systolic Dissemination of Information in Interconnection Networks.
Proceedings of the Parallel and Distributed Computing, 1994

Comparing Descriptional and Computational Complexity of Infinite Words.
Proceedings of the Results and Trends in Theoretical Computer Science, 1994

1993
A Note on Realtime One-Way Synchronized Alternating One-Counter Automata.
Theor. Comput. Sci., 1993

Optimal Algorithms for Dissemination of Information in Some Interconnection Networks.
Algorithmica, 1993

Gossiping in Vertex-Disjoint Path Mode in Interconnection Networks.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

Some Hierarchies for the Communication Complexity Measures of Cooperating Grammar Systems.
Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

Gossiping in Vertex-Disjoint Paths Mode in d-Dimensional Grids and Planar Graphs.
Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

Deterministic Versus Nondeterministic Space in Terms of Synchronized Alternating Machines.
Proceedings of the Developments in Language Theory, 1993

1992
Branching Programs Provide Lower Bounds on the Areas of Multilective Deterministic and Nondeterministic VLSI-Circuits
Inf. Comput., February, 1992

Lower Bounds on the Area Complexity of Boolean Circuits.
Theor. Comput. Sci., 1992

Abstract symbol systems - an exercise of the bottom-up approach in artificial intelligence.
J. Exp. Theor. Artif. Intell., 1992

On the Power of One-Way Synchronized Alternating Machines with Small Space.
Int. J. Found. Comput. Sci., 1992

Topology of Parallel Networks and Computational Complexity (Extended Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

A Nonlinear Lower Bound on the Practical Combinational Complexity.
Proceedings of the STACS 92, 1992

On Embedding Interconnection Networks into Rings of Processors.
Proceedings of the PARLE '92: Parallel Architectures and Languages Europe, 1992

Optimal Algorithms for Disemination of Information in Generalized Communication Modes.
Proceedings of the PARLE '92: Parallel Architectures and Languages Europe, 1992

1991
Nonlinear Lower Bounds on the Number of Processors of Circuits with Sublinear Separators
Inf. Comput., December, 1991

On Problems for Which no Oracle Can Help.
Mathematical Systems Theory, 1991

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

On the power of two-dimensional synchronized alternating finite automata.
Fundam. Inform., 1991

Variable Multihead Machines.
Elektronische Informationsverarbeitung und Kybernetik, 1991

On the power of synchronization in parallel computations.
Discrete Applied Mathematics, 1991

The Bisection Problem for Graphs of Degree 4 (Configuring Transputer Systems).
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).
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990
Optimal Algorithms for Dissemination of Information in Some Interconnection Networks (Extended Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989
A Leaf-Size Hierarchy of Two-Dimensional Alternating Turing Machines.
Theor. Comput. Sci., 1989

Tradeoffs for Language Recognition on Alternating Machines.
Theor. Comput. Sci., 1989

Lower Bounds for Language Recognition on Two-Dimensional Alternating Multihead Machines.
J. Comput. Syst. Sci., 1989

The knowledge on information content of problems provides much useful information to circuit designers.
Bulletin of the EATCS, 1989

On the Power of Synchronization in Parallel Computations.
Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

1988
The Advantages of a New Approach to Defining the Communication Complexity for VLSI.
Theor. Comput. Sci., 1988

Graph Controlled Table Lindenmayer Systems.
Elektronische Informationsverarbeitung und Kybernetik, 1988

A candidate for nonlinear lower bound on the combinatorial complexity.
Bulletin of the EATCS, 1988

Branching Programs as a Tool for Proving Lower Bounds on VLSI Computations and Optimal Algorithms for Systolic Arrays.
Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1987
Reversal-Bounded Nondeterministic Multicounter Machines and Complementation.
Theor. Comput. Sci., 1987

Zerotesting bounded one-way multicounter machines.
Kybernetika, 1987

Reversal Complexity of Multicounter and Multihead Machines.
Proceedings of the STACS 87, 1987

1986
Communication Complexity Hierarchy.
Theor. Comput. Sci., 1986

Hierarchy of reversal bounded one-way multicounter machines.
Kybernetika, 1986

A New Approach to Defining the Complexity for VLSI.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

Lower bound techniques for VLSI algorithms.
Proceedings of the Trends, 1986

Tradeoffs for Language Recognition on Parallel Computing Models.
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.
Kybernetika, 1985

On the Power of Alternation in Automata Theory.
J. Comput. Syst. Sci., 1985

Linear Lower Bounds on Unbounded Fan-In Boolean Circuits.
Inf. Process. Lett., 1985

Alternating Multicounter Machines with Constant Number of Reversals.
Inf. Process. Lett., 1985

Fooling a Two-Way Nondeterministic Multihead Automaton with Reversal Number Restriction.
Acta Inf., 1985

1984
A note on the "Comuunication Complexity" paper by Papadimitriou and Sipser.
Bulletin of the EATCS, 1984

On the power of Yao-Rivest technique.
Bulletin of the EATCS, 1984

On the Power of Alternation in Finite Automata.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Hierarchy of Reversal and Zerotesting Bounded Multicounter Machines.
Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

Communication Complexity.
Proceedings of the Automata, 1984

1983
One-Way Simple Multihead Finite Automata are not Closed Under Concatenation.
Theor. Comput. Sci., 1983

On-Way Multihead Deterministic Finite Automata.
Acta Inf., 1983

1982
Multihead Finite State Automata and Concatenation.
Proceedings of the Automata, 1982

1981
Closure Properties of the Family of Languages Recognized by One-Way Two-Head Deterministic Finite State Automata.
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981


  Loading...