| Publication | Date of Publication | Type |
|---|
| Lower bounds for graph-walking automata | 2026-04-21 | Paper |
Sweeping permutation automata
Acta Informatica | 2026-02-20 | Paper |
A time to cast away stones: on a family of pebble automata
International Journal of Foundations of Computer Science | 2026-02-17 | Paper |
| A hierarchy of reversible finite automata | 2026-02-10 | Paper |
| From regular expressions to deterministic finite automata: \(2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}\) states are necessary and sufficient | 2026-02-10 | Paper |
| Simulating two-way nondeterministic finite automata over small alphabets by one-way nondeterministic automata | 2026-02-10 | Paper |
| On the transformation of two-way nondeterministic finite automata to unambiguous finite automata | 2026-02-10 | Paper |
On the expressive power of categorial grammars with unique category assignment
Journal of Logic, Language and Information | 2025-12-29 | Paper |
Decision problems for systems of language equations and inequations
Information and Computation | 2025-12-15 | Paper |
| Sweeping permutation automata | 2025-08-19 | Paper |
Probabilistic input-driven pushdown automata
Information and Computation | 2025-06-27 | Paper |
A parallel algorithm for counting parse trees
Information and Computation | 2025-02-28 | Paper |
| Decision problems for reversible and permutation automata | 2025-01-20 | Paper |
| Parallel enumeration of parse trees | 2024-12-03 | Paper |
| Probabilistic input-driven pushdown automata | 2024-12-03 | Paper |
Rational index of languages defined by grammars with bounded dimension of parse trees
Theory of Computing Systems | 2024-07-29 | Paper |
\(\mathrm{GF}(2)\)-operations on basic families of formal languages
Theoretical Computer Science | 2024-03-28 | Paper |
A time to cast away stones
Implementation and Application of Automata | 2024-02-28 | Paper |
On hardest languages for one-dimensional cellular automata
Information and Computation | 2024-02-02 | Paper |
On the transformation of two-way finite automata to unambiguous finite automata
Information and Computation | 2024-02-02 | Paper |
| On the rank of the communication matrix for deterministic two-way finite automata | 2023-12-10 | Paper |
| scientific article; zbMATH DE number 7770054 (Why is no real title available?) | 2023-11-23 | Paper |
Homomorphisms and inverse homomorphisms on graph-walking automata
Theoretical Computer Science | 2023-10-26 | Paper |
Shortest accepted strings for two-way finite automata: approaching the \(2^n\) lower bound
Descriptional Complexity of Formal Systems | 2023-08-17 | Paper |
The Hardest LL(k) Language
International Journal of Foundations of Computer Science | 2023-08-15 | Paper |
Non-closure under complementation for unambiguous linear grammars
Information and Computation | 2023-05-19 | Paper |
On the transformation of LL(k)-linear to LL(1)-linear grammars
Theory of Computing Systems | 2023-05-02 | Paper |
The hardest language for grammars with context operators
Theoretical Computer Science | 2023-05-02 | Paper |
State complexity of transforming graph-walking automata to halting, returning and reversible
Information and Computation | 2023-03-07 | Paper |
On the determinization of event-clock input-driven pushdown automata
(available as arXiv preprint) | 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
Computer Science – Theory and Applications | 2022-10-19 | Paper |
Homomorphisms on graph-walking automata
(available as arXiv preprint) | 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
ACM Transactions on Computation Theory | 2022-03-14 | Paper |
State complexity of GF(2)-operations on unary languages
Information and Computation | 2022-03-14 | Paper |
Formal languages over GF(2)
Information and Computation | 2022-03-14 | Paper |
| Language equations | 2022-02-04 | Paper |
On the length of shortest strings accepted by two-way finite automata
Fundamenta Informaticae | 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 |
| Grammars with two-sided contexts | 2021-06-22 | Paper |
Grammars with two-sided contexts
(available as arXiv preprint) | 2021-06-22 | Paper |
| Nondeterministic state complexity of positional addition | 2021-01-26 | Paper |
| scientific article; zbMATH DE number 7298596 (Why is no real title available?) | 2021-01-20 | Paper |
scientific article; zbMATH DE number 7298596 (Why is no real title available?)
(available as arXiv preprint) | 2021-01-20 | Paper |
Reversibility of computations in graph-walking automata
Information and Computation | 2020-12-15 | Paper |
Extensions of unification modulo ACUI
Mathematical Structures in Computer Science | 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
Descriptional Complexity of Formal Systems | 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
International Journal of Foundations of Computer Science | 2019-12-10 | Paper |
State complexity of unambiguous operations on finite automata
Theoretical Computer Science | 2019-11-07 | Paper |
Further closure properties of input-driven pushdown automata
Theoretical Computer Science | 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
Theoretical Computer Science | 2019-06-18 | Paper |
Hardest languages for conjunctive and Boolean grammars
Information and Computation | 2019-05-02 | Paper |
| Towards exact state complexity bounds for input-driven pushdown automata | 2018-11-22 | Paper |
| A tale of conjunctive grammars | 2018-11-22 | Paper |
On the number of nonterminal symbols in unambiguous conjunctive grammars
Fundamenta Informaticae | 2018-10-02 | Paper |
| Underlying principles and recurring ideas of formal grammars | 2018-06-26 | Paper |
Formal languages over GF(2)
Language and Automata Theory and Applications | 2018-06-26 | Paper |
| scientific article; zbMATH DE number 6851884 (Why is no real title available?) | 2018-03-21 | Paper |
Linear-space recognition for grammars with contexts
Theoretical Computer Science | 2018-03-12 | Paper |
| Conjunctive categorial grammars | 2017-12-18 | Paper |
Generalized LR parsing algorithm for grammars with one-sided contexts
Theory of Computing Systems | 2017-10-20 | Paper |
| The quotient operation on input-driven pushdown automata | 2017-08-31 | Paper |
Edit distance neighbourhoods of input-driven pushdown automata
Computer Science – Theory and Applications | 2017-08-22 | Paper |
State complexity of operations on input-driven pushdown automata
Journal of Computer and System Sciences | 2017-05-26 | Paper |
On the state complexity of operations on two-way finite automata
Information and Computation | 2017-03-16 | Paper |
Unambiguous conjunctive grammars over a one-symbol alphabet
Theoretical Computer Science | 2017-02-06 | Paper |
Approximate unification in the description logic \(\mathcal {FL}_0\)
Logics in Artificial Intelligence | 2016-11-30 | Paper |
Nondeterministic state complexity of positional addition
Journal of Automata, Languages and Combinatorics | 2016-09-29 | Paper |
The hardest language for conjunctive grammars
Computer Science – Theory and Applications | 2016-07-25 | Paper |
Equations over sets of integers with addition only
Journal of Computer and System Sciences | 2016-06-13 | Paper |
Least and greatest solutions of equations over sets of integers
Theoretical Computer Science | 2016-02-26 | Paper |
Input-driven languages are linear conjunctive
Theoretical Computer Science | 2016-02-18 | Paper |
On language equations with concatenation and various sets of Boolean operations
RAIRO - Theoretical Informatics and Applications | 2016-01-22 | Paper |
Generalized LR parsing for grammars with contexts
Lecture Notes in Computer Science | 2015-10-20 | Paper |
On the determinization blowup for finite automata recognizing equal-length languages
Computing with New Resources | 2015-09-08 | Paper |
Linear grammars with one-sided contexts and their automaton representation
RAIRO - Theoretical Informatics and Applications | 2015-08-14 | Paper |
Two-sided context specifications in formal grammars
Theoretical Computer Science | 2015-07-13 | Paper |
Improved normal form for grammars with one-sided contexts
Theoretical Computer Science | 2015-06-11 | Paper |
Descriptional complexity of unambiguous input-driven pushdown automata
Theoretical Computer Science | 2015-01-06 | Paper |
Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Input-Driven Pushdown Automata with Limited Nondeterminism
Developments in Language Theory | 2014-10-14 | Paper |
Homomorphisms preserving deterministic context-free languages
International Journal of Foundations of Computer Science | 2014-08-04 | Paper |
Computational completeness of equations over sets of natural numbers
Information and Computation | 2014-07-18 | Paper |
An extension of context-free grammars with one-sided context specifications
Information and Computation | 2014-07-18 | Paper |
Linear grammars with one-sided contexts and their automaton representation
LATIN 2014: Theoretical Informatics | 2014-03-31 | Paper |
| On language equations with one-sided concatenation | 2014-02-11 | Paper |
Conjunctive and Boolean grammars: the true general case of the context-free grammars
Computer Science Review | 2014-01-28 | Paper |
Parsing by matrix multiplication generalized to Boolean grammars
Theoretical Computer Science | 2013-12-13 | Paper |
Reversibility of computations in graph-walking automata
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Improved normal form for grammars with one-sided contexts
Descriptional Complexity of Formal Systems | 2013-08-09 | Paper |
Unambiguous conjunctive grammars over a one-letter alphabet
Developments in Language Theory | 2013-06-28 | Paper |
| scientific article; zbMATH DE number 6146470 (Why is no real title available?) | 2013-03-19 | Paper |
Representing hyper-arithmetical sets by equations over sets of integers
Theory of Computing Systems | 2012-12-07 | Paper |
Homomorphisms Preserving Deterministic Context-Free Languages
Developments in Language Theory | 2012-11-02 | Paper |
On the number of nonterminal symbols in unambiguous conjunctive grammars
Descriptional Complexity of Formal Systems | 2012-11-02 | Paper |
Non-erasing Variants of the Chomsky–Schützenberger Theorem
Developments in Language Theory | 2012-11-02 | Paper |
Descriptional complexity of input-driven pushdown automata
Lecture Notes in Computer Science | 2012-11-01 | Paper |
Parsing Boolean grammars over a one-letter alphabet using online convolution
Theoretical Computer Science | 2012-10-11 | Paper |
State complexity of operations on two-way finite automata over a unary alphabet
Theoretical Computer Science | 2012-08-13 | Paper |
On the state complexity of star of union and star of intersection
Fundamenta Informaticae | 2012-07-04 | Paper |
Language equations with symmetric difference
Fundamenta Informaticae | 2012-06-20 | Paper |
Solving language equations and disequations with applications to disunification in description logics and monadic set constraints
Logic for Programming, Artificial Intelligence, and Reasoning | 2012-06-15 | Paper |
Defining contexts in context-free grammars
Language and Automata Theory and Applications | 2012-06-08 | Paper |
On the expressive power of univariate equations over sets of natural numbers
Information and Computation | 2012-05-24 | Paper |
Unambiguous finite automata over a unary alphabet
Information and Computation | 2012-05-24 | Paper |
| Equations over sets of natural numbers with addition only | 2012-04-24 | Paper |
Language equations with complementation: expressive power
Theoretical Computer Science | 2012-03-13 | Paper |
| On equations over sets of integers | 2012-01-23 | Paper |
State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
Fundamenta Informaticae | 2011-11-22 | Paper |
One-nonterminal conjunctive grammars over a unary alphabet
Theory of Computing Systems | 2011-10-11 | Paper |
Expressive power of \(\text{LL}(k)\) Boolean grammars
Theoretical Computer Science | 2011-10-10 | Paper |
State complexity of operations on input-driven pushdown automata
Mathematical Foundations of Computer Science 2011 | 2011-08-17 | Paper |
Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
Developments in Language Theory | 2011-07-29 | Paper |
State complexity of operations on two-way deterministic finite automata over a unary alphabet
Descriptional Complexity of Formal Systems | 2011-07-29 | Paper |
| scientific article; zbMATH DE number 5906488 (Why is no real title available?) | 2011-06-10 | Paper |
Descriptional complexity of unambiguous nested word automata
Language and Automata Theory and Applications | 2011-06-03 | Paper |
On equations over sets of numbers and their limitations
International Journal of Foundations of Computer Science | 2011-03-30 | Paper |
Complexity of equations over sets of natural numbers
Theory of Computing Systems | 2011-03-30 | Paper |
Comparing linear conjunctive languages to subfamilies of the context-free languages
SOFSEM 2011: Theory and Practice of Computer Science | 2011-02-15 | Paper |
A simple P-complete problem and its language-theoretic representations
Theoretical Computer Science | 2011-01-10 | Paper |
Boolean grammars and gsm mappings
International Journal of Foundations of Computer Science | 2010-11-11 | Paper |
Computational power of two stacks with restricted communication
Information and Computation | 2010-10-07 | Paper |
On the state complexity of scattered substrings and superstrings
Fundamenta Informaticae | 2010-10-01 | Paper |
Unambiguous finite automata over a unary alphabet
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
Least and greatest solutions of equations over sets of integers
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
On language equations \(XXK = XXL\) and \(XM = N\) over a unary alphabet
Developments in Language Theory | 2010-08-31 | Paper |
Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
Developments in Language Theory | 2010-08-31 | Paper |
Conjunctive grammars with restricted disjunction
Theoretical Computer Science | 2010-06-07 | Paper |
Decision problems for language equations
Journal of Computer and System Sciences | 2010-05-25 | Paper |
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
Theory of Computing Systems | 2010-03-05 | Paper |
On stateless multihead automata: hierarchies and the emptiness problem
Theoretical Computer Science | 2010-02-05 | Paper |
Notes on dual concatenation
International Journal of Foundations of Computer Science | 2010-01-29 | Paper |
| scientific article; zbMATH DE number 5605108 (Why is no real title available?) | 2009-09-19 | Paper |
| scientific article; zbMATH DE number 5604079 (Why is no real title available?) | 2009-09-15 | Paper |
One-Nonterminal Conjunctive Grammars over a Unary Alphabet
Computer Science - Theory and Applications | 2009-08-18 | Paper |
| Homomorphisms preserving linear conjunctive languages | 2009-08-10 | Paper |
On Equations over Sets of Numbers and Their Limitations
Developments in Language Theory | 2009-07-07 | Paper |
State complexity of power
Theoretical Computer Science | 2009-06-04 | Paper |
Language Equations with Complementation
Developments in Language Theory | 2009-03-26 | Paper |
The hardest linear conjunctive language
Information Processing Letters | 2009-03-23 | Paper |
A Simple P-Complete Problem and Its Representations by Language Equations
Lecture Notes in Computer Science | 2009-03-05 | Paper |
Conjunctive Grammars with Restricted Disjunction
Lecture Notes in Computer Science | 2009-02-03 | Paper |
On the State Complexity of Operations on Two-Way Finite Automata
Developments in Language Theory | 2008-10-30 | Paper |
Unambiguous Boolean grammars
Information and Computation | 2008-10-08 | Paper |
On the Computational Completeness of Equations over Sets of Natural Numbers
Automata, Languages and Programming | 2008-08-19 | Paper |
| scientific article; zbMATH DE number 5309909 (Why is no real title available?) | 2008-08-12 | Paper |
State complexity of cyclic shift
RAIRO - Theoretical Informatics and Applications | 2008-07-29 | Paper |
State complexity of cyclic shift
RAIRO - Theoretical Informatics and Applications | 2008-07-29 | Paper |
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
Computer Science – Theory and Applications | 2008-06-03 | Paper |
On Stateless Multihead Automata: Hierarchies and the Emptiness Problem
Lecture Notes in Computer Science | 2008-04-15 | Paper |
Expressive Power of LL(k) Boolean Grammars
Fundamentals of Computation Theory | 2008-02-26 | Paper |
Communication of Two Stacks and Rewriting
Automata, Languages and Programming | 2007-09-11 | Paper |
Recursive descent parsing for Boolean grammars
Acta Informatica | 2007-08-17 | Paper |
Language equations with complementation: decision problems
Theoretical Computer Science | 2007-05-11 | Paper |
Language Equations with Symmetric Difference
Computer Science – Theory and Applications | 2007-05-02 | Paper |
| Computational universality in one-variable language equations | 2007-01-19 | Paper |
Mathematical Foundations of Computer Science 2005
Lecture Notes in Computer Science | 2006-10-20 | Paper |
GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
International Journal of Foundations of Computer Science | 2006-08-14 | Paper |
Developments in Language Theory
Lecture Notes in Computer Science | 2006-06-23 | Paper |
Computing by commuting.
Theoretical Computer Science | 2006-05-18 | Paper |
Unresolved systems of language equations: expressive power and decision problems
Theoretical Computer Science | 2006-03-20 | Paper |
Machines, Computations, and Universality
Lecture Notes in Computer Science | 2005-12-08 | Paper |
The dual of concatenation
Theoretical Computer Science | 2005-12-06 | Paper |
A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS
International Journal of Foundations of Computer Science | 2005-11-14 | Paper |
EFFICIENT AUTOMATON-BASED RECOGNITION FOR LINEAR CONJUNCTIVE LANGUAGES
International Journal of Foundations of Computer Science | 2005-10-19 | Paper |
| scientific article; zbMATH DE number 2201371 (Why is no real title available?) | 2005-09-01 | Paper |
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science | 2005-08-22 | Paper |
| scientific article; zbMATH DE number 2182441 (Why is no real title available?) | 2005-06-23 | Paper |
| scientific article; zbMATH DE number 2155200 (Why is no real title available?) | 2005-04-11 | Paper |
Boolean grammars
Information and Computation | 2004-11-12 | Paper |
On the equivalence of linear conjunctive grammars and trellis automata
RAIRO - Theoretical Informatics and Applications | 2004-10-28 | Paper |
On the equivalence of linear conjunctive grammars and trellis automata
RAIRO - Theoretical Informatics and Applications | 2004-10-28 | Paper |
On the equivalence of linear conjunctive grammars and trellis automata
RAIRO - Theoretical Informatics and Applications | 2004-10-28 | Paper |
On the complexity of the string generation problem
Discrete Mathematics and Applications | 2004-08-30 | Paper |
On the number of nonterminals in linear conjunctive grammars
Theoretical Computer Science | 2004-08-10 | Paper |
Representing recursively enumerable languages by iterated deletion
Theoretical Computer Science | 2004-08-06 | Paper |
| scientific article; zbMATH DE number 2040923 (Why is no real title available?) | 2004-02-11 | Paper |
| scientific article; zbMATH DE number 2038714 (Why is no real title available?) | 2004-02-08 | Paper |
Conjunctive grammars and systems of language equations
Programming and Computer Software | 2003-09-01 | Paper |
A recognition and parsing algorithm for arbitrary conjunctive grammars.
Theoretical Computer Science | 2003-08-17 | Paper |
| scientific article; zbMATH DE number 1962782 (Why is no real title available?) | 2003-08-11 | Paper |
| scientific article; zbMATH DE number 1962778 (Why is no real title available?) | 2003-08-11 | Paper |
| scientific article; zbMATH DE number 1948516 (Why is no real title available?) | 2003-07-13 | Paper |
On the closure properties of linear conjunctive languages.
Theoretical Computer Science | 2003-05-25 | Paper |
| scientific article; zbMATH DE number 1886076 (Why is no real title available?) | 2003-04-23 | Paper |
LR parsing for conjunctive grammars
Grammars | 2002-12-15 | Paper |
| scientific article; zbMATH DE number 1747449 (Why is no real title available?) | 2002-12-01 | Paper |
Top-down parsing of conjunctive languages
Grammars | 2002-07-09 | Paper |
