Alexander Okhotin

Theor. Comput. Sci., November, 2023

Non-closure under complementation for unambiguous linear grammars.

[BibT_eX]

[DOI]

Inf. Comput., June, 2023

The hardest language for grammars with context operators.

[BibT_eX]

[DOI]

Mikhail Mrykhin

Theor. Comput. Sci., May, 2023

Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars.

[BibT_eX]

[DOI]

Theory Comput. Syst., April, 2023

On the Transformation of LL(k)-linear to LL(1)-linear Grammars.

[BibT_eX]

[DOI]

Theory Comput. Syst., April, 2023

State complexity of transforming graph-walking automata to halting, returning and reversible.

[BibT_eX]

[DOI]

Inf. Comput., March, 2023

State Complexity of GF(2)-Inverse and GF(2)-Star on Binary Languages.

[BibT_eX]

[DOI]

Elizaveta Sazhneva

J. Autom. Lang. Comb., 2023

The Hardest LL(k) Language.

[BibT_eX]

[DOI]

Mikhail Mrykhin

Int. J. Found. Comput. Sci., 2023

On the rank of the communication matrix for deterministic two-way finite automata.

[BibT_eX]

[DOI]

Semyon Petrov

Fedor Petrov

CoRR, 2023

Sweeping Permutation Automata.

[BibT_eX]

[DOI]

Maria Radionova

Proceedings of the 13th International Workshop on Non-Classical Models of Automata and Applications, 2023

A Time to Cast Away Stones.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2023

Probabilistic Input-Driven Pushdown Automata.

[BibT_eX]

[DOI]

Alex Rose

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Parallel Enumeration of Parse Trees.

[BibT_eX]

[DOI]

Margarita Mikhelson

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Shortest Accepted Strings for Two-Way Finite Automata: Approaching the 2n Lower Bound.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2023

2022

State complexity of GF(2)-operations on unary languages.

[BibT_eX]

[DOI]

Elizaveta Sazhneva

Inf. Comput., 2022

Formal languages over GF(2).

[BibT_eX]

[DOI]

Inf. Comput., 2022

The maximum length of shortest accepted strings for direction-determinate two-way finite automata.

[BibT_eX]

[DOI]

CoRR, 2022

Homomorphisms on Graph-Walking Automata.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2022

Rational Index of Languages with Bounded Dimension of Parse Trees.

[BibT_eX]

[DOI]

Ekaterina N. Shemetova

Semyon V. Grigorev

Proceedings of the Developments in Language Theory - 26th International Conference, 2022

On the Determinization of Event-Clock Input-Driven Pushdown Automata.

[BibT_eX]

[DOI]

Mizuhito Ogawa

Proceedings of the Computer Science - Theory and Applications, 2022

2021

On the Length of Shortest Strings Accepted by Two-way Finite Automata.

[BibT_eX]

[DOI]

Egor Dobronravov

Nikita Dobronravov

Fundam. Informaticae, 2021

On LL(k) linear conjunctive grammars.

[BibT_eX]

[DOI]

CoRR, 2021

Lower Bounds for Graph-Walking Automata.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous Finite Automata.

[BibT_eX]

[DOI]

Semyon Petrov

Proceedings of the Language and Automata Theory and Applications, 2021

On Hardest Languages for One-Dimensional Cellular Automata.

[BibT_eX]

[DOI]

Mikhail Mrykhin

Proceedings of the Language and Automata Theory and Applications, 2021

State Complexity of Union and Intersection on Graph-Walking Automata.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2021

Deterministic One-Way Simulation of Two-Way Deterministic Finite Automata over Small Alphabets.

[BibT_eX]

[DOI]

Viliam Geffert

Proceedings of the Descriptional Complexity of Formal Systems, 2021

Input-Driven Pushdown Automata on Well-Nested Infinite Strings.

[BibT_eX]

[DOI]

Victor L. Selivanov

Proceedings of the Computer Science - Theory and Applications, 2021

Language equations.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Automata Theory., 2021

2020

Extensions of unification modulo ACUI.

[BibT_eX]

[DOI]

Math. Struct. Comput. Sci., 2020

Reversibility of computations in graph-walking automata.

[BibT_eX]

[DOI]

Inf. Comput., 2020

Computational and proof complexity of partial string avoidability.

[BibT_eX]

[DOI]

Dmitry Itsykson

Vsevolod Oparin

Electron. Colloquium Comput. Complex., 2020

Rational index of bounded-oscillation languages.

[BibT_eX]

[DOI]

Ekaterina N. Shemetova

Semyon V. Grigorev

CoRR, 2020

Describing the syntax of programming languages using conjunctive and Boolean grammars.

[BibT_eX]

[DOI]

CoRR, 2020

Input-driven automata on well-nested infinite strings: automata-theoretic and topological properties.

[BibT_eX]

[DOI]

Victor L. Selivanov

CoRR, 2020

State complexity of halting, returning and reversible graph-walking automata.

[BibT_eX]

[DOI]

CoRR, 2020

Cyclic Shift on Multi-component Grammars.

[BibT_eX]

[DOI]

Alexey Sorokin

Proceedings of the Language and Automata Theory and Applications, 2020

Longer Shortest Strings in Two-Way Finite Automata.

[BibT_eX]

[DOI]

Stanislav Krymski

Proceedings of the Descriptional Complexity of Formal Systems, 2020

On the Transformation of LL(k)-linear Grammars to LL(1)-linear.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2020

2019

Further closure properties of input-driven pushdown automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Edit distance neighbourhoods of input-driven pushdown automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

State complexity of unambiguous operations on finite automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

State Complexity of the Quotient Operation on Input-Driven Pushdown Automata.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2019

Hardest languages for conjunctive and Boolean grammars.

[BibT_eX]

[DOI]

Inf. Comput., 2019

Graph-Walking Automata: From Whence They Come, and Whither They are Bound.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2019

On the Expressive Power of GF(2)-Grammars.

[BibT_eX]

[DOI]

Vladislav Makarov

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

State Complexity of GF(2)-Concatenation and GF(2)-Inverse on Unary Languages.

[BibT_eX]

[DOI]

Elizaveta Sazhneva

Proceedings of the Descriptional Complexity of Formal Systems, 2019

2018

Linear-space recognition for grammars with contexts.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Preface.

[BibT_eX]

[DOI]

Jarkko Kari

Int. J. Found. Comput. Sci., 2018

Preface.

[BibT_eX]

[DOI]

Jeffrey O. Shallit

Inf. Comput., 2018

On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2018

Underlying Principles and Recurring Ideas of Formal Grammars.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2018

A Tale of Conjunctive Grammars.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

Towards Exact State Complexity Bounds for Input-Driven Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

State Complexity of Unambiguous Operations on Deterministic Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2018

2017

Unambiguous conjunctive grammars over a one-symbol alphabet.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

State complexity of operations on input-driven pushdown automata.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

On the state complexity of operations on two-way finite automata.

[BibT_eX]

[DOI]

Inf. Comput., 2017

Conjunctive Categorial Grammars.

[BibT_eX]

[DOI]

Stepan L. Kuznetsov

Proceedings of the 15th Meeting on the Mathematics of Language, 2017

The Quotient Operation on Input-Driven Pushdown Automata.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2017

2016

Input-driven languages are linear conjunctive.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Descriptional Complexity of Formal Systems.

[BibT_eX]

[DOI]

Helmut Jürgensen

Theor. Comput. Sci., 2016

Least and greatest solutions of equations over sets of integers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Equations over sets of integers with addition only.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Approximately Solving Set Equations.

[BibT_eX]

[DOI]

Pavlos Marantidis

Proceedings of the 30th International Workshop on Unification, 2016

Approximate Unification in the Description Logic FL_0.

[BibT_eX]

[DOI]

Pavlos Marantidis

Proceedings of the Logics in Artificial Intelligence - 15th European Conference, 2016

The Hardest Language for Conjunctive Grammars.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2016

2015

Descriptional complexity of unambiguous input-driven pushdown automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Improved normal form for grammars with one-sided contexts.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Two-sided context specifications in formal grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

On language equations with concatenation and various sets of Boolean operations.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2015

Linear grammars with one-sided contexts and their automaton representation.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2015

Generalized LR Parsing for Grammars with Contexts.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2015

2014

Parsing by matrix multiplication generalized to Boolean grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Complexity of input-driven pushdown automata.

[BibT_eX]

[DOI]

SIGACT News, 2014

Computational completeness of equations over sets of natural numbers.

[BibT_eX]

[DOI]

Inf. Comput., 2014

An extension of context-free grammars with one-sided context specifications.

[BibT_eX]

[DOI]

Inf. Comput., 2014

Grammars with two-sided contexts.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 14th International Conference on Automata and Formal Languages, 2014

Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata.

[BibT_eX]

[DOI]

Viliam Geffert

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Input-Driven Pushdown Automata with Limited Nondeterminism - (Invited Paper).

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 18th International Conference, 2014

On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages.

[BibT_eX]

[DOI]

Proceedings of the Computing with New Resources, 2014

2013

Homomorphisms Preserving Deterministic Context-Free Languages.

[BibT_eX]

[DOI]

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

On Language Equations with One-sided Concatenation.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2013

Conjunctive and Boolean grammars: The true general case of the context-free grammars.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2013

Input-driven pushdown automata: nondeterminism and unambiguity.

[BibT_eX]

Proceedings of the Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13, 2013

One-way simulation of two-way finite automata over small alphabets.

[BibT_eX]

Viliam Geffert

Proceedings of the Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13, 2013

Unambiguous Conjunctive Grammars over a One-Letter Alphabet.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 17th International Conference, 2013

2012

Language equations with complementation: Expressive power.

[BibT_eX]

[DOI]

Oksana Yakimova

Theor. Comput. Sci., 2012

Parsing Boolean grammars over a one-letter alphabet using online convolution.

[BibT_eX]

[DOI]

Christian Reitwießner

Theor. Comput. Sci., 2012

State complexity of operations on two-way finite automata over a unary alphabet.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

Representing Hyper-arithmetical Sets by Equations over Sets of Integers.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2012

On the expressive power of univariate equations over sets of natural numbers.

[BibT_eX]

[DOI]

Panos Rondogiannis

Inf. Comput., 2012

Unambiguous finite automata over a unary alphabet.

[BibT_eX]

[DOI]

Inf. Comput., 2012

Language Equations with Symmetric Difference.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2012

Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints.

[BibT_eX]

[DOI]

Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2012

Defining Contexts in Context-Free Grammars.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2012

Non-erasing Variants of the Chomsky-Schützenberger Theorem.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

Descriptional Complexity of Input-Driven Pushdown Automata.

[BibT_eX]

[DOI]

Xiaoxue Piao

Proceedings of the Languages Alive, 2012

2011

Expressive power of LL(k) Boolean grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

A simple P-complete problem and its language-theoretic representations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

One-Nonterminal Conjunctive Grammars over a Unary Alphabet.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Complexity of Equations over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

On Equations over Sets of Numbers and their Limitations.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2011

State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2011

On the State Complexity of Star of Union and Star of Intersection.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2011

Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages.

[BibT_eX]

[DOI]

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

Descriptional Complexity of Unambiguous Nested Word Automata.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2011

Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 15th International Conference, 2011

State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2011

2010

Conjunctive grammars with restricted disjunction.

[BibT_eX]

[DOI]

Christian Reitwießner

Theor. Comput. Sci., 2010

On stateless multihead automata: Hierarchies and the emptiness problem.

[BibT_eX]

[DOI]

Oscar H. Ibarra

Theor. Comput. Sci., 2010

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Decision problems for language equations.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

Nondeterministic State Complexity of Positional Addition.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2010

Boolean Grammars and GSM Mappings.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2010

Computational power of two stacks with restricted communication.

[BibT_eX]

[DOI]

Inf. Comput., 2010

On the State Complexity of Scattered Substrings and Superstrings.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2010

Univariate Equations Over Sets of Natural Numbers.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2010

On Equations over Sets of Integers.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

On Language Equations XXK = XXL and XM = N over a Unary Alphabet.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 14th International Conference, 2010

Parsing Unary Boolean Grammars Using Online Convolution.

[BibT_eX]

[DOI]

Christian Reitwießner

Proceedings of the Advances and Applications of Automata on Words and Trees, 12.12., 2010

2009

State complexity of power.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Equations over Sets of Natural Numbers with Addition Only.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008

Homomorphisms Preserving Linear Conjunctive Languages.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2008

State complexity of cyclic shift.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2008

Unambiguous Boolean grammars.

[BibT_eX]

[DOI]

Inf. Comput., 2008

Representing a P-complete problem by small trellis automata

[BibT_eX]

[DOI]

Proceedings of the Proceedings International Workshop on The Complexity of Simple Programs, 2008

Complexity of solutions of equations over sets of natural numbers.

[BibT_eX]

[DOI]

Proceedings of the STACS 2008, 2008

2007

Language equations with complementation: Decision problems.

[BibT_eX]

[DOI]

Oksana Yakimova

Theor. Comput. Sci., 2007

Enumeration of Context-Free Languages and Related Structures.

[BibT_eX]

[DOI]

Jeffrey O. Shallit

J. Autom. Lang. Comb., 2007

Notes on Dual Concatenation.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2007

Nine Open Problems on Conjunctive and Boolean Grammars.

[BibT_eX]

Bull. EATCS, 2007

Recursive descent parsing for Boolean grammars.

[BibT_eX]

[DOI]

Acta Informatica, 2007

A Simple P-Complete Problem and Its Representations by Language Equations.

[BibT_eX]

[DOI]

Proceedings of the Machines, Computations, and Universality, 5th International Conference, 2007

2006

Computing by commuting.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Generalized Lr Parsing Algorithm for Boolean Grammars.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2006

Computational Universality in One-variable Language Equations.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2006

Communication of Two Stacks and Rewriting.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Language Equations with Complementation.

[BibT_eX]

[DOI]

Oksana Yakimova

Proceedings of the Developments in Language Theory, 10th International Conference, 2006

2005

Unresolved systems of language equations: Expressive power and decision problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

The dual of concatenation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

A characterization of the arithmetical hierarchy by language equations.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2005

Contextual Grammars with Uniform Sets of Trajectories.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2005

Strict Language Inequalities and Their Decision Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

LR Parsing for Boolean Grammars.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 9th International Conference, 2005

2004

On the number of nonterminals in linear conjunctive grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Representing recursively enumerable languages by iterated deletion.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

State Complexity of Linear Conjunctive Languages.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2004

On the equivalence of linear conjunctive grammars and trellis automata.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 2004

Boolean grammars.

[BibT_eX]

[DOI]

Inf. Comput., 2004

On Computational Universality in Language Equations.

[BibT_eX]

[DOI]

Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004

2003

On the closure properties of linear conjunctive languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

A recognition and parsing algorithm for arbitrary conjunctive grammars.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

The hardest linear conjunctive language.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

Efficient Automaton-Based Recognition For Linear Conjunctive Languages.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2003

An overview of conjunctive grammars, Formal Language Theory Column.

[BibT_eX]

Bull. EATCS, 2003

Decision Problems for Language Equations with Boolean Operations.

[BibT_eX]

[DOI]

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

2002

Conjunctive Grammars and Systems of Language Equations.

[BibT_eX]

[DOI]

Program. Comput. Softw., 2002

LR Parsing for Conjunctive Grammars.

[BibT_eX]

[DOI]

Grammars, 2002

Top-Down Parsing of Conjunctive Languages.

[BibT_eX]

[DOI]

Grammars, 2002

One-Visit Caterpillar Tree Automata.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2002

Whale Calf, a Parser Generator for Conjunctive Grammars.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2002

Automaton Representation of Linear Conjunctive Languages.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 6th International Conference, 2002

2001

Conjunctive Grammars.

[BibT_eX]

[DOI]