Alexander Okhotin

According to our database1, Alexander Okhotin
  • authored at least 142 papers between 2001 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
Unambiguous conjunctive grammars over a one-symbol alphabet.
Theor. Comput. Sci., 2017

Generalized LR Parsing Algorithm for Grammars with One-Sided Contexts.
Theory Comput. Syst., 2017

State complexity of operations on input-driven pushdown automata.
J. Comput. Syst. Sci., 2017

On the state complexity of operations on two-way finite automata.
Inf. Comput., 2017

Conjunctive Categorial Grammars.
Proceedings of the 15th Meeting on the Mathematics of Language, 2017

The Quotient Operation on Input-Driven Pushdown Automata.
Proceedings of the Descriptional Complexity of Formal Systems, 2017

Edit Distance Neighbourhoods of Input-Driven Pushdown Automata.
Proceedings of the Computer Science - Theory and Applications, 2017

2016
Input-driven languages are linear conjunctive.
Theor. Comput. Sci., 2016

Descriptional Complexity of Formal Systems.
Theor. Comput. Sci., 2016

Least and greatest solutions of equations over sets of integers.
Theor. Comput. Sci., 2016

Equations over sets of integers with addition only.
J. Comput. Syst. Sci., 2016

Computational and Proof Complexity of Partial String Avoidability.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Approximate Unification in the Description Logic FL_0.
Proceedings of the Logics in Artificial Intelligence - 15th European Conference, 2016

The Hardest Language for Conjunctive Grammars.
Proceedings of the Computer Science - Theory and Applications, 2016

2015
Descriptional complexity of unambiguous input-driven pushdown automata.
Theor. Comput. Sci., 2015

Improved normal form for grammars with one-sided contexts.
Theor. Comput. Sci., 2015

Two-sided context specifications in formal grammars.
Theor. Comput. Sci., 2015

On language equations with concatenation and various sets of Boolean operations.
RAIRO - Theor. Inf. and Applic., 2015

Linear grammars with one-sided contexts and their automaton representation.
RAIRO - Theor. Inf. and Applic., 2015

Generalized LR Parsing for Grammars with Contexts.
Proceedings of the Computer Science - Theory and Applications, 2015

2014
Parsing by matrix multiplication generalized to Boolean grammars.
Theor. Comput. Sci., 2014

Complexity of input-driven pushdown automata.
SIGACT News, 2014

Computational completeness of equations over sets of natural numbers.
Inf. Comput., 2014

An extension of context-free grammars with one-sided context specifications.
Inf. Comput., 2014

Grammars with two-sided contexts.
Proceedings of the Proceedings 14th International Conference on Automata and Formal Languages, 2014

Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Linear Grammars with One-Sided Contexts and Their Automaton Representation.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Input-Driven Pushdown Automata with Limited Nondeterminism - (Invited Paper).
Proceedings of the Developments in Language Theory - 18th International Conference, 2014

On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages.
Proceedings of the Computing with New Resources, 2014

2013
Homomorphisms Preserving Deterministic Context-Free Languages.
Int. J. Found. Comput. Sci., 2013

On Language Equations with One-sided Concatenation.
Fundam. Inform., 2013

Conjunctive and Boolean grammars: The true general case of the context-free grammars.
Computer Science Review, 2013

Input-driven pushdown automata: nondeterminism and unambiguity.
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.
Proceedings of the Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13, 2013

Reversibility of Computations in Graph-Walking Automata.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Unambiguous Conjunctive Grammars over a One-Letter Alphabet.
Proceedings of the Developments in Language Theory - 17th International Conference, 2013

Improved Normal Form for Grammars with One-Sided Contexts.
Proceedings of the Descriptional Complexity of Formal Systems, 2013

2012
Language equations with complementation: Expressive power.
Theor. Comput. Sci., 2012

Parsing Boolean grammars over a one-letter alphabet using online convolution.
Theor. Comput. Sci., 2012

State complexity of operations on two-way finite automata over a unary alphabet.
Theor. Comput. Sci., 2012

Representing Hyper-arithmetical Sets by Equations over Sets of Integers.
Theory Comput. Syst., 2012

On the expressive power of univariate equations over sets of natural numbers.
Inf. Comput., 2012

Unambiguous finite automata over a unary alphabet.
Inf. Comput., 2012

Language Equations with Symmetric Difference.
Fundam. Inform., 2012

Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints.
Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2012

Defining Contexts in Context-Free Grammars.
Proceedings of the Language and Automata Theory and Applications, 2012

Non-erasing Variants of the Chomsky-Schützenberger Theorem.
Proceedings of the Developments in Language Theory - 16th International Conference, 2012

Homomorphisms Preserving Deterministic Context-Free Languages.
Proceedings of the Developments in Language Theory - 16th International Conference, 2012

On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.
Proceedings of the Descriptional Complexity of Formal Systems, 2012

Descriptional Complexity of Input-Driven Pushdown Automata.
Proceedings of the Languages Alive, 2012

2011
Expressive power of LL(k) Boolean grammars.
Theor. Comput. Sci., 2011

A simple P-complete problem and its language-theoretic representations.
Theor. Comput. Sci., 2011

One-Nonterminal Conjunctive Grammars over a Unary Alphabet.
Theory Comput. Syst., 2011

Complexity of Equations over Sets of Natural Numbers.
Theory Comput. Syst., 2011

On Equations over Sets of Numbers and their Limitations.
Int. J. Found. Comput. Sci., 2011

State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata.
Fundam. Inform., 2011

On the State Complexity of Star of Union and Star of Intersection.
Fundam. Inform., 2011

Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011

State Complexity of Operations on Input-Driven Pushdown Automata.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Descriptional Complexity of Unambiguous Nested Word Automata.
Proceedings of the Language and Automata Theory and Applications, 2011

Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups.
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.
Proceedings of the Descriptional Complexity of Formal Systems, 2011

2010
Conjunctive grammars with restricted disjunction.
Theor. Comput. Sci., 2010

On stateless multihead automata: Hierarchies and the emptiness problem.
Theor. Comput. Sci., 2010

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.
Theory Comput. Syst., 2010

Decision problems for language equations.
J. Comput. Syst. Sci., 2010

Nondeterministic State Complexity of Positional Addition.
Journal of Automata, Languages and Combinatorics, 2010

Boolean Grammars and GSM Mappings.
Int. J. Found. Comput. Sci., 2010

Computational power of two stacks with restricted communication.
Inf. Comput., 2010

On the State Complexity of Scattered Substrings and Superstrings.
Fundam. Inform., 2010

Univariate Equations Over Sets of Natural Numbers.
Fundam. Inform., 2010

On equations over sets of integers
CoRR, 2010

On Equations over Sets of Integers.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Unambiguous Finite Automata over a Unary Alphabet.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Least and Greatest Solutions of Equations over Sets of Integers.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Fast Parsing for Boolean Grammars: A Generalization of Valiant's Algorithm.
Proceedings of the Developments in Language Theory, 14th International Conference, 2010

On Language Equations XXK = XXL and XM = N over a Unary Alphabet.
Proceedings of the Developments in Language Theory, 14th International Conference, 2010

Parsing Unary Boolean Grammars Using Online Convolution.
Proceedings of the Advances and Applications of Automata on Words and Trees, 12.12., 2010

2009
State complexity of power.
Theor. Comput. Sci., 2009

Nondeterministic State Complexity of Positional Addition
Proceedings of the Proceedings Eleventh International Workshop on Descriptional Complexity of Formal Systems, 2009

Equations over Sets of Natural Numbers with Addition Only.
Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Conjunctive Grammars with Restricted Disjunction.
Proceedings of the SOFSEM 2009: Theory and Practice of Computer Science, 2009

On Equations over Sets of Numbers and Their Limitations.
Proceedings of the Developments in Language Theory, 13th International Conference, 2009

One-Nonterminal Conjunctive Grammars over a Unary Alphabet.
Proceedings of the Computer Science, 2009

2008
Homomorphisms Preserving Linear Conjunctive Languages.
Journal of Automata, Languages and Combinatorics, 2008

State complexity of cyclic shift.
ITA, 2008

Unambiguous Boolean grammars.
Inf. Comput., 2008

Representing a P-complete problem by small trellis automata
Proceedings of the Proceedings International Workshop on The Complexity of Simple Programs, 2008

Complexity of solutions of equations over sets of natural numbers.
Proceedings of the STACS 2008, 2008

On Stateless Multihead Automata: Hierarchies and the Emptiness Problem.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

On the expressive power of univariate equations over sets of natural numbers.
Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

On the Computational Completeness of Equations over Sets of Natural Numbers.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

On the State Complexity of Operations on Two-Way Finite Automata.
Proceedings of the Developments in Language Theory, 12th International Conference, 2008

Boolean grammars and gsm mappings.
Proceedings of the Automata and Formal Languages, 12th International Conference, 2008

2007
Language equations with complementation: Decision problems.
Theor. Comput. Sci., 2007

Enumeration of Context-Free Languages and Related Structures.
Journal of Automata, Languages and Combinatorics, 2007

Notes on Dual Concatenation.
Int. J. Found. Comput. Sci., 2007

Nine Open Problems on Conjunctive and Boolean Grammars.
Bulletin of the EATCS, 2007

Recursive descent parsing for Boolean grammars.
Acta Inf., 2007

A Simple P-Complete Problem and Its Representations by Language Equations.
Proceedings of the Machines, Computations, and Universality, 5th International Conference, 2007

Unambiguous Boolean grammars.
Proceedings of the LATA 2007. Proceedings of the 1st International Conference on Language and Automata Theory and Applications., 2007

Expressive Power of LL(k) Boolean Grammars.
Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.
Proceedings of the Computer Science, 2007

2006
Computing by commuting.
Theor. Comput. Sci., 2006

Generalized Lr Parsing Algorithm for Boolean Grammars.
Int. J. Found. Comput. Sci., 2006

Computational Universality in One-variable Language Equations.
Fundam. Inform., 2006

Communication of Two Stacks and Rewriting.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Language Equations with Complementation.
Proceedings of the Developments in Language Theory, 10th International Conference, 2006

Language Equations with Symmetric Difference.
Proceedings of the Computer Science, 2006

2005
Unresolved systems of language equations: Expressive power and decision problems.
Theor. Comput. Sci., 2005

The dual of concatenation.
Theor. Comput. Sci., 2005

A characterization of the arithmetical hierarchy by language equations.
Int. J. Found. Comput. Sci., 2005

Contextual Grammars with Uniform Sets of Trajectories.
Fundam. Inform., 2005

Strict Language Inequalities and Their Decision Problems.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

LR Parsing for Boolean Grammars.
Proceedings of the Developments in Language Theory, 9th International Conference, 2005

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

Enumeration of Context-Free Languages and Related Structures.
Proceedings of the 7th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2005, Como, Italy, June 30, 2005

2004
On the number of nonterminals in linear conjunctive grammars.
Theor. Comput. Sci., 2004

Representing recursively enumerable languages by iterated deletion.
Theor. Comput. Sci., 2004

State Complexity of Linear Conjunctive Grammars.
Journal of Automata, Languages and Combinatorics, 2004

On the equivalence of linear conjunctive grammars and trellis automata.
ITA, 2004

Boolean grammars.
Inf. Comput., 2004

The Dual of Concatenation.
Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

On Computational Universality in Language Equations.
Proceedings of the Machines, Computations, and Universality, 4th International Conference, 2004

A characterization of the arithmetical hierarchy by language equations.
Proceedings of the 6th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2004, London, Ontario, Canada, July 26, 2004

2003
On the closure properties of linear conjunctive languages.
Theor. Comput. Sci., 2003

A recognition and parsing algorithm for arbitrary conjunctive grammars.
Theor. Comput. Sci., 2003

The hardest linear conjunctive language.
Inf. Process. Lett., 2003

Efficient Automaton-Based Recognition For Linear Conjunctive Languages.
Int. J. Found. Comput. Sci., 2003

An overview of conjunctive grammars, Formal Language Theory Column.
Bulletin of the EATCS, 2003

Decision Problems for Language Equations with Boolean Operations.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Boolean Grammars.
Proceedings of the Developments in Language Theory, 7th International Conference, 2003

On the Number of Nonterminals in Linear Conjunctive Grammars.
Proceedings of the 5th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2003, Budapest, Hungary, July 12, 2003

2002
Conjunctive Grammars and Systems of Language Equations.
Programming and Computer Software, 2002

LR Parsing for Conjunctive Grammars.
Grammars, 2002

Top-Down Parsing of Conjunctive Languages.
Grammars, 2002

One-Visit Caterpillar Tree Automata.
Fundam. Inform., 2002

Whale Calf, a Parser Generator for Conjunctive Grammars.
Proceedings of the Implementation and Application of Automata, 2002

Efficient Automaton-Based Recognition for Linear Conjunctive Languages.
Proceedings of the Implementation and Application of Automata, 2002

Automaton Representation of Linear Conjunctive Languages.
Proceedings of the Developments in Language Theory, 6th International Conference, 2002

State complexity of linear conjunctive languages.
Proceedings of the Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21, 2002

2001
Conjunctive Grammars.
Journal of Automata, Languages and Combinatorics, 2001


  Loading...