Alexander Okhotin

Available identifiers

zbMath Open okhotin.alexanderWikidataQ29032931 ScholiaQ29032931MaRDI QIDQ248926

List of research outcomes

Publication	Date of Publication	Type
\(\mathrm{GF}(2)\)-operations on basic families of formal languages	2024-03-28	Paper
A time to cast away stones	2024-02-28	Paper
On hardest languages for one-dimensional cellular automata	2024-02-02	Paper
On the transformation of two-way finite automata to unambiguous finite automata	2024-02-02	Paper
On the rank of the communication matrix for deterministic two-way finite automata	2023-12-10	Paper
https://portal.mardi4nfdi.de/entity/Q6070606	2023-11-23	Paper
Homomorphisms and inverse homomorphisms on graph-walking automata	2023-10-26	Paper
Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound	2023-08-17	Paper
The Hardest LL(k) Language	2023-08-15	Paper
Non-closure under complementation for unambiguous linear grammars	2023-05-19	Paper
The hardest language for grammars with context operators	2023-05-02	Paper
On the transformation of LL\((k)\)-linear to LL(1)-linear grammars	2023-05-02	Paper
State complexity of transforming graph-walking automata to halting, returning and reversible	2023-03-07	Paper
On the determinization of event-clock input-driven pushdown automata	2022-11-11	Paper
Deterministic one-way simulation of two-way deterministic finite automata over small alphabets	2022-11-09	Paper
State complexity of union and intersection on graph-walking automata	2022-11-09	Paper
On the Transformation of LL(k)-linear Grammars to LL(1)-linear	2022-10-19	Paper
Homomorphisms on graph-walking automata	2022-08-16	Paper
Rational index of languages with bounded dimension of parse trees	2022-08-11	Paper
The hardest \(\operatorname{LL}(k)\) language	2022-03-25	Paper
Input-driven pushdown automata on well-nested infinite strings	2022-03-21	Paper
Computational and Proof Complexity of Partial String Avoidability	2022-03-14	Paper
Formal languages over GF(2)	2022-03-14	Paper
State complexity of GF(2)-operations on unary languages	2022-03-14	Paper
Language equations	2022-02-04	Paper
On the Length of Shortest Strings Accepted by Two-way Finite Automata	2021-10-25	Paper
On the transformation of two-way deterministic finite automata to unambiguous finite automata	2021-10-04	Paper
On hardest languages for one-dimensional cellular automata	2021-10-04	Paper
Longer shortest strings in two-way finite automata	2021-07-14	Paper
State complexity of GF(2)-inverse and GF(2)-star on binary languages	2021-07-14	Paper
https://portal.mardi4nfdi.de/entity/Q4994937	2021-06-22	Paper
https://portal.mardi4nfdi.de/entity/Q5146525	2021-01-26	Paper
https://portal.mardi4nfdi.de/entity/Q5145160	2021-01-20	Paper
Reversibility of computations in graph-walking automata	2020-12-15	Paper
Extensions of unification modulo ACUI	2020-12-08	Paper
On the expressive power of GF(2)-grammars	2020-10-22	Paper
Cyclic shift on multi-component grammars	2020-07-27	Paper
Further closure properties of input-driven pushdown automata	2020-06-30	Paper
State complexity of unambiguous operations on deterministic finite automata	2020-06-30	Paper
State complexity of GF(2)-concatenation and GF(2)-inverse on unary languages	2020-05-12	Paper
Graph-walking automata: from whence they come, and whither they are bound	2020-05-06	Paper
State Complexity of the Quotient Operation on Input-Driven Pushdown Automata	2019-12-10	Paper
Further closure properties of input-driven pushdown automata	2019-11-07	Paper
State complexity of unambiguous operations on finite automata	2019-11-07	Paper
On the length of shortest strings accepted by two-way finite automata	2019-10-15	Paper
Edit distance neighbourhoods of input-driven pushdown automata	2019-06-18	Paper
Hardest languages for conjunctive and Boolean grammars	2019-05-02	Paper
A tale of conjunctive grammars	2018-11-22	Paper
Towards exact state complexity bounds for input-driven pushdown automata	2018-11-22	Paper
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars	2018-10-02	Paper
Formal languages over GF(2)	2018-06-26	Paper
Underlying principles and recurring ideas of formal grammars	2018-06-26	Paper
https://portal.mardi4nfdi.de/entity/Q4608614	2018-03-21	Paper
Linear-space recognition for grammars with contexts	2018-03-12	Paper
https://portal.mardi4nfdi.de/entity/Q4599225	2017-12-18	Paper
Generalized LR parsing algorithm for grammars with one-sided contexts	2017-10-20	Paper
The quotient operation on input-driven pushdown automata	2017-08-31	Paper
Edit distance neighbourhoods of input-driven pushdown automata	2017-08-22	Paper
State complexity of operations on input-driven pushdown automata	2017-05-26	Paper
On the state complexity of operations on two-way finite automata	2017-03-16	Paper
Unambiguous conjunctive grammars over a one-symbol alphabet	2017-02-06	Paper
Approximate Unification in the Description Logic $$\mathcal {FL}_0$$	2016-11-30	Paper
https://portal.mardi4nfdi.de/entity/Q2819384	2016-09-29	Paper
The Hardest Language for Conjunctive Grammars	2016-07-25	Paper
Equations over sets of integers with addition only	2016-06-13	Paper
Least and greatest solutions of equations over sets of integers	2016-02-26	Paper
Input-driven languages are linear conjunctive	2016-02-18	Paper
On language equations with concatenation and various sets of Boolean operations	2016-01-22	Paper
Generalized LR Parsing for Grammars with Contexts	2015-10-20	Paper
On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages	2015-09-08	Paper
Linear grammars with one-sided contexts and their automaton representation	2015-08-14	Paper
Two-sided context specifications in formal grammars	2015-07-13	Paper
Improved normal form for grammars with one-sided contexts	2015-06-11	Paper
Descriptional complexity of unambiguous input-driven pushdown automata	2015-01-06	Paper
Input-Driven Pushdown Automata with Limited Nondeterminism	2014-10-14	Paper
Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata	2014-10-14	Paper
HOMOMORPHISMS PRESERVING DETERMINISTIC CONTEXT-FREE LANGUAGES	2014-08-04	Paper
Computational completeness of equations over sets of natural numbers	2014-07-18	Paper
An extension of context-free grammars with one-sided context specifications	2014-07-18	Paper
Linear Grammars with One-Sided Contexts and Their Automaton Representation	2014-03-31	Paper
https://portal.mardi4nfdi.de/entity/Q5747087	2014-02-11	Paper
Conjunctive and Boolean grammars: the true general case of the context-free grammars	2014-01-28	Paper
Parsing by matrix multiplication generalized to Boolean grammars	2013-12-13	Paper
Reversibility of Computations in Graph-Walking Automata	2013-09-20	Paper
Improved Normal Form for Grammars with One-Sided Contexts	2013-08-09	Paper
Unambiguous Conjunctive Grammars over a One-Letter Alphabet	2013-06-28	Paper
https://portal.mardi4nfdi.de/entity/Q4910734	2013-03-19	Paper
Representing hyper-arithmetical sets by equations over sets of integers	2012-12-07	Paper
Non-erasing Variants of the Chomsky–Schützenberger Theorem	2012-11-02	Paper
Homomorphisms Preserving Deterministic Context-Free Languages	2012-11-02	Paper
On the Number of Nonterminal Symbols in Unambiguous Conjunctive Grammars	2012-11-02	Paper
Descriptional Complexity of Input-Driven Pushdown Automata	2012-11-01	Paper
Parsing Boolean grammars over a one-letter alphabet using online convolution	2012-10-11	Paper
State complexity of operations on two-way finite automata over a unary alphabet	2012-08-13	Paper
On the State Complexity of Star of Union and Star of Intersection	2012-07-04	Paper
https://portal.mardi4nfdi.de/entity/Q2893311	2012-06-20	Paper
Solving Language Equations and Disequations with Applications to Disunification in Description Logics and Monadic Set Constraints	2012-06-15	Paper
Defining Contexts in Context-Free Grammars	2012-06-08	Paper
On the expressive power of univariate equations over sets of natural numbers	2012-05-24	Paper
Unambiguous finite automata over a unary alphabet	2012-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q5390009	2012-04-24	Paper
Language equations with complementation: expressive power	2012-03-13	Paper
https://portal.mardi4nfdi.de/entity/Q3113773	2012-01-23	Paper
State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata	2011-11-22	Paper
One-nonterminal conjunctive grammars over a unary alphabet	2011-10-11	Paper
Expressive power of \(\text{LL}(k)\) Boolean grammars	2011-10-10	Paper
State Complexity of Operations on Input-Driven Pushdown Automata	2011-08-17	Paper
Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups	2011-07-29	Paper
State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet	2011-07-29	Paper
https://portal.mardi4nfdi.de/entity/Q3005912	2011-06-10	Paper
Descriptional Complexity of Unambiguous Nested Word Automata	2011-06-03	Paper
Complexity of equations over sets of natural numbers	2011-03-30	Paper
ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS	2011-03-30	Paper
Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages	2011-02-15	Paper
A simple P-complete problem and its language-theoretic representations	2011-01-10	Paper
BOOLEAN GRAMMARS AND GSM MAPPINGS	2010-11-11	Paper
Computational power of two stacks with restricted communication	2010-10-07	Paper
On the State Complexity of Scattered Substrings and Superstrings	2010-10-01	Paper
Least and Greatest Solutions of Equations over Sets of Integers	2010-09-03	Paper
Unambiguous Finite Automata over a Unary Alphabet	2010-09-03	Paper
On Language Equations XXK = XXL and XM = N over a Unary Alphabet	2010-08-31	Paper
Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm	2010-08-31	Paper
Conjunctive grammars with restricted disjunction	2010-06-07	Paper
Decision problems for language equations	2010-05-25	Paper
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth	2010-03-05	Paper
On stateless multihead automata: hierarchies and the emptiness problem	2010-02-05	Paper
NOTES ON DUAL CONCATENATION	2010-01-29	Paper
https://portal.mardi4nfdi.de/entity/Q3396606	2009-09-19	Paper
https://portal.mardi4nfdi.de/entity/Q3395960	2009-09-15	Paper
One-Nonterminal Conjunctive Grammars over a Unary Alphabet	2009-08-18	Paper
https://portal.mardi4nfdi.de/entity/Q5192986	2009-08-10	Paper
On Equations over Sets of Numbers and Their Limitations	2009-07-07	Paper
State complexity of power	2009-06-04	Paper
Language Equations with Complementation	2009-03-26	Paper
The hardest linear conjunctive language	2009-03-23	Paper
A Simple P-Complete Problem and Its Representations by Language Equations	2009-03-05	Paper
Conjunctive Grammars with Restricted Disjunction	2009-02-03	Paper
On the State Complexity of Operations on Two-Way Finite Automata	2008-10-30	Paper
Unambiguous Boolean grammars	2008-10-08	Paper
On the Computational Completeness of Equations over Sets of Natural Numbers	2008-08-19	Paper
https://portal.mardi4nfdi.de/entity/Q3517096	2008-08-12	Paper
State complexity of cyclic shift	2008-07-29	Paper
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth	2008-06-03	Paper
On Stateless Multihead Automata: Hierarchies and the Emptiness Problem	2008-04-15	Paper
Expressive Power of LL(k) Boolean Grammars	2008-02-26	Paper
Communication of Two Stacks and Rewriting	2007-09-11	Paper
Recursive descent parsing for Boolean grammars	2007-08-17	Paper
Language equations with complementation: decision problems	2007-05-11	Paper
Language Equations with Symmetric Difference	2007-05-02	Paper
https://portal.mardi4nfdi.de/entity/Q3416097	2007-01-19	Paper
Mathematical Foundations of Computer Science 2005	2006-10-20	Paper
GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS	2006-08-14	Paper
Developments in Language Theory	2006-06-23	Paper
Computing by commuting.	2006-05-18	Paper
Unresolved systems of language equations: expressive power and decision problems	2006-03-20	Paper
Machines, Computations, and Universality	2005-12-08	Paper
The dual of concatenation	2005-12-06	Paper
A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS	2005-11-14	Paper
EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES	2005-10-19	Paper
https://portal.mardi4nfdi.de/entity/Q5313800	2005-09-01	Paper
Mathematical Foundations of Computer Science 2004	2005-08-22	Paper
https://portal.mardi4nfdi.de/entity/Q4681310	2005-06-23	Paper
https://portal.mardi4nfdi.de/entity/Q4665747	2005-04-11	Paper
Boolean grammars	2004-11-12	Paper
On the equivalence of linear conjunctive grammars and trellis automata	2004-10-28	Paper
On the complexity of the string generation problem	2004-08-30	Paper
On the number of nonterminals in linear conjunctive grammars	2004-08-10	Paper
Representing recursively enumerable languages by iterated deletion	2004-08-06	Paper
https://portal.mardi4nfdi.de/entity/Q4452079	2004-02-11	Paper
https://portal.mardi4nfdi.de/entity/Q4449179	2004-02-08	Paper
Conjunctive grammars and systems of language equations	2003-09-01	Paper
A recognition and parsing algorithm for arbitrary conjunctive grammars.	2003-08-17	Paper
https://portal.mardi4nfdi.de/entity/Q4418613	2003-08-11	Paper
https://portal.mardi4nfdi.de/entity/Q4418617	2003-08-11	Paper
https://portal.mardi4nfdi.de/entity/Q4412133	2003-07-13	Paper
On the closure properties of linear conjunctive languages.	2003-05-25	Paper
https://portal.mardi4nfdi.de/entity/Q4799361	2003-04-23	Paper
LR parsing for conjunctive grammars	2002-12-15	Paper
https://portal.mardi4nfdi.de/entity/Q4531380	2002-12-01	Paper
Top-down parsing of conjunctive languages	2002-07-09	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Alexander Okhotin