Alexander Okhotin
According to our database^{1},
Alexander Okhotin
authored at least 154 papers
between 2001 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at zbmath.org

at orcid.org

at users.utu.fi

at dl.acm.org
On csauthors.net:
Bibliography
2019
Hardest languages for conjunctive and Boolean grammars.
Inf. Comput., 2019
On the Expressive Power of GF(2)Grammars.
Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019
2018
Linearspace recognition for grammars with contexts.
Theor. Comput. Sci., 2018
Preface.
Int. J. Found. Comput. Sci., 2018
Preface.
Inf. Comput., 2018
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars.
Fundam. Inform., 2018
Underlying Principles and Recurring Ideas of Formal Grammars.
Proceedings of the Language and Automata Theory and Applications, 2018
Formal Languages over GF(2).
Proceedings of the Language and Automata Theory and Applications, 2018
A Tale of Conjunctive Grammars.
Proceedings of the Developments in Language Theory  22nd International Conference, 2018
Towards Exact State Complexity Bounds for InputDriven Pushdown Automata.
Proceedings of the Developments in Language Theory  22nd International Conference, 2018
Further Closure Properties of InputDriven Pushdown Automata.
Proceedings of the Descriptional Complexity of Formal Systems, 2018
State Complexity of Unambiguous Operations on Deterministic Finite Automata.
Proceedings of the Descriptional Complexity of Formal Systems, 2018
2017
Unambiguous conjunctive grammars over a onesymbol alphabet.
Theor. Comput. Sci., 2017
Generalized LR Parsing Algorithm for Grammars with OneSided Contexts.
Theory Comput. Syst., 2017
State complexity of operations on inputdriven pushdown automata.
J. Comput. Syst. Sci., 2017
On the state complexity of operations on twoway finite automata.
Inf. Comput., 2017
Conjunctive Categorial Grammars.
Proceedings of the 15th Meeting on the Mathematics of Language, 2017
The Quotient Operation on InputDriven Pushdown Automata.
Proceedings of the Descriptional Complexity of Formal Systems, 2017
Edit Distance Neighbourhoods of InputDriven Pushdown Automata.
Proceedings of the Computer Science  Theory and Applications, 2017
2016
Inputdriven 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 inputdriven pushdown automata.
Theor. Comput. Sci., 2015
Improved normal form for grammars with onesided contexts.
Theor. Comput. Sci., 2015
Twosided 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 onesided 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 inputdriven pushdown automata.
SIGACT News, 2014
Computational completeness of equations over sets of natural numbers.
Inf. Comput., 2014
An extension of contextfree grammars with onesided context specifications.
Inf. Comput., 2014
Grammars with twosided contexts.
Proceedings of the Proceedings 14th International Conference on Automata and Formal Languages, 2014
Transforming TwoWay Alternating Finite Automata to OneWay Nondeterministic Automata.
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014
Linear Grammars with OneSided Contexts and Their Automaton Representation.
Proceedings of the LATIN 2014: Theoretical Informatics  11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014
InputDriven 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 EqualLength Languages.
Proceedings of the Computing with New Resources, 2014
2013
Homomorphisms Preserving Deterministic ContextFree Languages.
Int. J. Found. Comput. Sci., 2013
On Language Equations with Onesided Concatenation.
Fundam. Inform., 2013
Conjunctive and Boolean grammars: The true general case of the contextfree grammars.
Computer Science Review, 2013
Inputdriven pushdown automata: nondeterminism and unambiguity.
Proceedings of the Fifth Workshop on NonClassical Models for Automata and Applications  NCMA 2013, Umeå, Sweden, August 13, 2013
Oneway simulation of twoway finite automata over small alphabets.
Proceedings of the Fifth Workshop on NonClassical Models for Automata and Applications  NCMA 2013, Umeå, Sweden, August 13, 2013
Reversibility of Computations in GraphWalking Automata.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013
Unambiguous Conjunctive Grammars over a OneLetter Alphabet.
Proceedings of the Developments in Language Theory  17th International Conference, 2013
Improved Normal Form for Grammars with OneSided 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 oneletter alphabet using online convolution.
Theor. Comput. Sci., 2012
State complexity of operations on twoway finite automata over a unary alphabet.
Theor. Comput. Sci., 2012
Representing Hyperarithmetical 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 ContextFree Grammars.
Proceedings of the Language and Automata Theory and Applications, 2012
Nonerasing Variants of the ChomskySchützenberger Theorem.
Proceedings of the Developments in Language Theory  16th International Conference, 2012
Homomorphisms Preserving Deterministic ContextFree 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 InputDriven Pushdown Automata.
Proceedings of the Languages Alive, 2012
2011
Expressive power of LL(k) Boolean grammars.
Theor. Comput. Sci., 2011
A simple Pcomplete problem and its languagetheoretic representations.
Theor. Comput. Sci., 2011
OneNonterminal 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 Twoway 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 ContextFree Languages.
Proceedings of the SOFSEM 2011: Theory and Practice of Computer Science, 2011
State Complexity of Operations on InputDriven 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 TwoWay Deterministic Finite Automata Using Transformation Semigroups.
Proceedings of the Developments in Language Theory  15th International Conference, 2011
State Complexity of Operations on TwoWay 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
OneNonterminal 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 Pcomplete 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 TwoWay 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 ContextFree 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 PComplete 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 Onevariable 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 ContextFree 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 Languages.
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 AutomatonBased 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
TopDown Parsing of Conjunctive Languages.
Grammars, 2002
OneVisit Caterpillar Tree Automata.
Fundam. Inform., 2002
Whale Calf, a Parser Generator for Conjunctive Grammars.
Proceedings of the Implementation and Application of Automata, 2002
Efficient AutomatonBased 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