A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES

A remark on middle space bounded alternating Turing machines

An optimal lower bound for nonregular languages

article by Alberto Bertoni et al published June 1994 in Information Processing Letters

Asynchronous automata versus asynchronous cellular automata

Complementing two-way finite automata

Complementing unary nondeterministic automata

Converting Nondeterministic Automata and Context-Free Grammars into Parikh Equivalent Deterministic Automata

Converting Self-verifying Automata into Deterministic Automata

Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata

Converting nondeterministic two-way automata into small deterministic linear-time machines

artículo científico publicado en 2022

Converting two-way nondeterministic unary automata into simpler automata

article published in 2003

DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES

Descriptional complexity of bounded context-free languages

Deterministic Pushdown Automata and Unary Languages

Distances between languages and reflexivity of relations

How Hard Is Computing the Edit Distance?

LIMITED AUTOMATA AND REGULAR LANGUAGES

Limited Automata and Context-Free Languages

artículo científico publicado en 2015

Limited Automata and Regular Languages

Normal forms for unary probabilistic automata

Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

Oblivious Two-Way Finite Automata: Decidability and Complexity

Oblivious two-way finite automata: Decidability and complexity

On Inverse Operations and Their Descriptional Complexity

On the Size of Unary Probabilistic and Nondeterministic Automata

artículo científico publicado en 2011

One Pebble Versus ϵ · log n Bits

artículo científico publicado en 2010

Operational State Complexity under Parikh Equivalence

Optimal simulation of self-verifying automata by deterministic automata

Optimal simulations between unary automata

Optimal state reductions of automata with partially specified behaviors

PREFACE

PREFACE

Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata

article published in 2010

Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata

Parikh’s Theorem and Descriptional Complexity

Preface

Preface

Preface

Preface to Martin Kutrib Festschrift

artículo científico publicado en 2021

Pushdown automata and constant height: decidability and bounds

artículo científico publicado en 2022

Reversal Hierarchies for Small 2DFAs

Simulating finite automata with context-free grammars

article published in 2002

String distances and intrusion detection: Bridging the gap between formal languages and computer security

The complexity of computing maximal word functions

Two-Way Automata Characterizations of L/poly Versus NL

Two-Way Automata Characterizations of L/poly versus NL

Two-Way Automata Making Choices Only at the Endmarkers

Two-Way Finite Automata: Old and Recent Results

artículo científico publicado en 2013

Two-Way Unary Automata versus Logarithmic Space

Two-way automata making choices only at the endmarkers

Two-way unary automata versus logarithmic space

Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds

Unary language operations, state complexity and Jacobsthal’s function

Usefulness of Information and Unary Languages

artículo científico publicado en 2021