On the equivalence of linear conjunctive grammars and trellis automata
RAIRO-Theor. Inf. Appl., 38 1 (2004) 69-88
Published online: 2004-03-15
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Inductive definitions in logic versus programs of real-time cellular automata
Étienne Grandjean, Théo Grente and Véronique TerrierTheoretical Computer Science 987 114355 (2024)
https://doi.org/10.1016/j.tcs.2023.114355
GF(2)-operations on basic families of formal languages
Alexander Okhotin, Maria Radionova and Elizaveta SazhnevaTheoretical Computer Science 995 114489 (2024)
https://doi.org/10.1016/j.tcs.2024.114489
On hardest languages for one-dimensional cellular automata
Mikhail Mrykhin and Alexander OkhotinInformation and Computation 295 104891 (2023)
https://doi.org/10.1016/j.ic.2022.104891
Formal languages over GF(2)
Ekaterina Bakinova, Artem Basharin, Igor Batmanov, et al.Information and Computation 283 104672 (2022)
https://doi.org/10.1016/j.ic.2020.104672
Language and Automata Theory and Applications
Mikhail Mrykhin and Alexander OkhotinLecture Notes in Computer Science, Language and Automata Theory and Applications 12638 118 (2021)
https://doi.org/10.1007/978-3-030-68195-1_10
1 (2019)
https://doi.org/10.1109/LICS.2019.8785666
11376 310 (2019)
https://doi.org/10.1007/978-3-030-10801-4_25
Edit distance neighbourhoods of input-driven pushdown automata
Alexander Okhotin and Kai SalomaaTheoretical Computer Science 777 417 (2019)
https://doi.org/10.1016/j.tcs.2019.03.005
Hardest languages for conjunctive and Boolean grammars
Alexander OkhotinInformation and Computation 266 1 (2019)
https://doi.org/10.1016/j.ic.2018.11.001
Language and Automata Theory and Applications
Alexander OkhotinLecture Notes in Computer Science, Language and Automata Theory and Applications 10792 36 (2018)
https://doi.org/10.1007/978-3-319-77313-1_3
Developments in Language Theory
Alexander OkhotinLecture Notes in Computer Science, Developments in Language Theory 11088 36 (2018)
https://doi.org/10.1007/978-3-319-98654-8_4
Unambiguous conjunctive grammars over a one-symbol alphabet
Artur Jeż and Alexander OkhotinTheoretical Computer Science 665 13 (2017)
https://doi.org/10.1016/j.tcs.2016.12.009
344 (2017)
https://doi.org/10.1145/3009837.3009848
Cellular Automata and Discrete Complex Systems
Véronique TerrierLecture Notes in Computer Science, Cellular Automata and Discrete Complex Systems 10248 176 (2017)
https://doi.org/10.1007/978-3-319-58631-1_14
Recognition of poly-slender context-free languages by trellis automata
Véronique TerrierTheoretical Computer Science 692 1 (2017)
https://doi.org/10.1016/j.tcs.2017.05.041
Context-sensitive data-dependence analysis via linear conjunctive language reachability
Qirun Zhang and Zhendong SuACM SIGPLAN Notices 52 (1) 344 (2017)
https://doi.org/10.1145/3093333.3009848
Least and greatest solutions of equations over sets of integers
Artur Jeż and Alexander OkhotinTheoretical Computer Science 619 68 (2016)
https://doi.org/10.1016/j.tcs.2016.01.013
Input-driven languages are linear conjunctive
Alexander OkhotinTheoretical Computer Science 618 52 (2016)
https://doi.org/10.1016/j.tcs.2016.01.007
Equations over sets of integers with addition only
Artur Jeż and Alexander OkhotinJournal of Computer and System Sciences 82 (6) 1007 (2016)
https://doi.org/10.1016/j.jcss.2016.02.003
Cellular Automata and Discrete Complex Systems
Véronique TerrierLecture Notes in Computer Science, Cellular Automata and Discrete Complex Systems 9099 251 (2015)
https://doi.org/10.1007/978-3-662-47221-7_19
Computational completeness of equations over sets of natural numbers
Artur Jeż and Alexander OkhotinInformation and Computation 237 56 (2014)
https://doi.org/10.1016/j.ic.2014.05.001
LATIN 2014: Theoretical Informatics
Mikhail Barash and Alexander OkhotinLecture Notes in Computer Science, LATIN 2014: Theoretical Informatics 8392 190 (2014)
https://doi.org/10.1007/978-3-642-54423-1_17
Conjunctive and Boolean grammars: The true general case of the context-free grammars
Alexander OkhotinComputer Science Review 9 27 (2013)
https://doi.org/10.1016/j.cosrev.2013.06.001
HOMOMORPHISMS PRESERVING DETERMINISTIC CONTEXT-FREE LANGUAGES
TOMMI LEHTINEN and ALEXANDER OKHOTINInternational Journal of Foundations of Computer Science 24 (07) 1049 (2013)
https://doi.org/10.1142/S0129054113400303
Developments in Language Theory
Artur Jeż and Alexander OkhotinLecture Notes in Computer Science, Developments in Language Theory 7907 277 (2013)
https://doi.org/10.1007/978-3-642-38771-5_25
Conjunctive grammars and alternating pushdown automata
Tamar Aizikowitz and Michael KaminskiActa Informatica 50 (3) 175 (2013)
https://doi.org/10.1007/s00236-013-0177-3
Developments in Language Theory
Tommi Lehtinen and Alexander OkhotinLecture Notes in Computer Science, Developments in Language Theory 7410 154 (2012)
https://doi.org/10.1007/978-3-642-31653-1_15
Descriptional Complexity of Formal Systems
Artur Jeż and Alexander OkhotinLecture Notes in Computer Science, Descriptional Complexity of Formal Systems 7386 183 (2012)
https://doi.org/10.1007/978-3-642-31623-4_14
Language equations with complementation: Expressive power
Alexander Okhotin and Oksana YakimovaTheoretical Computer Science 416 71 (2012)
https://doi.org/10.1016/j.tcs.2011.10.003
A simple P-complete problem and its language-theoretic representations
Alexander OkhotinTheoretical Computer Science 412 (1-2) 68 (2011)
https://doi.org/10.1016/j.tcs.2010.09.015
SOFSEM 2011: Theory and Practice of Computer Science
Alexander OkhotinLecture Notes in Computer Science, SOFSEM 2011: Theory and Practice of Computer Science 6543 431 (2011)
https://doi.org/10.1007/978-3-642-18381-2_36
Formal Grammar
Tamar Aizikowitz and Michael KaminskiLecture Notes in Computer Science, Formal Grammar 5591 1 (2011)
https://doi.org/10.1007/978-3-642-20169-1_1
Expressive power of LL(k) Boolean grammars
Alexander OkhotinTheoretical Computer Science 412 (39) 5132 (2011)
https://doi.org/10.1016/j.tcs.2011.05.013
Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
Artur Jeż and Alexander OkhotinTheory of Computing Systems 46 (1) 27 (2010)
https://doi.org/10.1007/s00224-008-9139-5
BOOLEAN GRAMMARS AND GSM MAPPINGS
TOMMI LEHTINEN and ALEXANDER OKHOTINInternational Journal of Foundations of Computer Science 21 (05) 799 (2010)
https://doi.org/10.1142/S0129054110007568
Mathematical Foundations of Computer Science 2010
Artur Jeż and Alexander OkhotinLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2010 6281 441 (2010)
https://doi.org/10.1007/978-3-642-15155-2_39
Automata, Languages and Programming
Artur Jeż and Alexander OkhotinLecture Notes in Computer Science, Automata, Languages and Programming 5126 63 (2008)
https://doi.org/10.1007/978-3-540-70583-3_6
5110 44 (2008)
https://doi.org/10.1007/978-3-540-69937-8_6
Unambiguous Boolean grammars
Alexander OkhotinInformation and Computation 206 (9-10) 1234 (2008)
https://doi.org/10.1016/j.ic.2008.03.023
Fundamentals of Computation Theory
Alexander OkhotinLecture Notes in Computer Science, Fundamentals of Computation Theory 4639 446 (2007)
https://doi.org/10.1007/978-3-540-74240-1_39
Computer Science – Theory and Applications
Artur Jeż and Alexander OkhotinLecture Notes in Computer Science, Computer Science – Theory and Applications 4649 168 (2007)
https://doi.org/10.1007/978-3-540-74510-5_19
Developments in Language Theory
Michal KuncLecture Notes in Computer Science, Developments in Language Theory 4588 23 (2007)
https://doi.org/10.1007/978-3-540-73208-2_3
NOTES ON DUAL CONCATENATION
ALEXANDER OKHOTINInternational Journal of Foundations of Computer Science 18 (06) 1361 (2007)
https://doi.org/10.1142/S0129054107005406
Computing by commuting
Juhani Karhumäki, Michal Kunc and Alexander OkhotinTheoretical Computer Science 356 (1-2) 200 (2006)
https://doi.org/10.1016/j.tcs.2006.01.051
Machines, Computations, and Universality
Alexander OkhotinLecture Notes in Computer Science, Machines, Computations, and Universality 3354 292 (2005)
https://doi.org/10.1007/978-3-540-31834-7_24
Unresolved systems of language equations: Expressive power and decision problems
Alexander OkhotinTheoretical Computer Science 349 (3) 283 (2005)
https://doi.org/10.1016/j.tcs.2005.07.038
The dual of concatenation
Alexander OkhotinTheoretical Computer Science 345 (2-3) 425 (2005)
https://doi.org/10.1016/j.tcs.2005.07.019
A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS
ALEXANDER OKHOTINInternational Journal of Foundations of Computer Science 16 (05) 985 (2005)
https://doi.org/10.1142/S012905410500342X
Boolean grammars
Alexander OkhotinInformation and Computation 194 (1) 19 (2004)
https://doi.org/10.1016/j.ic.2004.03.006
Mathematical Foundations of Computer Science 2004
Alexander OkhotinLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2004 3153 698 (2004)
https://doi.org/10.1007/978-3-540-28629-5_54
Deletion along trajectories
Michael DomaratzkiTheoretical Computer Science 320 (2-3) 293 (2004)
https://doi.org/10.1016/j.tcs.2004.02.031
On the number of nonterminals in linear conjunctive grammars
Alexander OkhotinTheoretical Computer Science 320 (2-3) 419 (2004)
https://doi.org/10.1016/j.tcs.2004.03.002