The nondeterministic state complexity of the site-directed deletion language operation. (English) Zbl 07715624
MSC:
68Qxx
Found 80 Documents (Results 1–80)
Nondeterministic state complexity of site-directed deletion. (English) Zbl 07572322
Caron, Pascal (ed.) et al., Implementation and application of automata. 26th international conference, CIAA 2022, Rouen, France, June 28 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13266, 189-199 (2022).
MSC:
68Q45
A general architecture of oritatami systems for simulating arbitrary finite automata. (English) Zbl 1504.68066
Nondeterministic finite automata based on quantum logic: language equivalence relation and robustness. (English) Zbl 1509.68142
Position automata for semi-extended expressions. (English) Zbl 1397.68114
MSC:
68Q45
The loops of the basis finite automaton and the connected questions. (Russian. English summary) Zbl 1373.68281
Looking for pairs that hard to separate: a quantum approach. (English) Zbl 1379.68214
Han, Yo-Sub (ed.) et al., Implementation and application of automata. 21st international conference, CIAA 2016, Seoul, South Korea, July 19–22, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-40945-0/pbk; 978-3-319-40946-7/ebook). Lecture Notes in Computer Science 9705, 213-223 (2016).
Counting regular expressions in degenerated sequences through lazy Markov chain embedding. (English) Zbl 1332.92007
Chen, Ke (ed.) et al., Forging connections between computational mathematics and computational geometry. Papers from the 3rd international conference on computational mathematics and computational geometry, CMCGS 2014, Singapore, February 3–4, 2014. Cham: Springer (ISBN 978-3-319-16138-9/hbk; 978-3-319-16139-6/ebook). Springer Proceedings in Mathematics & Statistics 124, 235-246 (2016).
Equivalence of SDVFA of order \((s,t)\) with DFA, VDFA, NFA and \(\epsilon \)-NFA. (English) Zbl 1340.68044
MSC:
68Q45
Construction of finite universal automata. II: Examples of functioning of the algorithms. (Russian. English summary) Zbl 1452.68104
MSC:
68Q45
Construction of universal finite automata. I: From theorem to the practical algorithms. (Russian. English summary) Zbl 1475.68150
MSC:
68Q45
A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads. (English) Zbl 1451.68156
Glück, Robert (ed.) et al., Reversible computation. 4th international workshop, RC 2012, Copenhagen, Denmark, July 2–3, 2012. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 7581, 29-43 (2013).
Some more on the basis finite automaton. (English) Zbl 1372.68160
MSC:
68Q45
Theory of computation. (English) Zbl 1283.68005
Oxford: Oxford University Press (ISBN 978-0-19-808458-7/pbk). xiv, 529 p. (2013).
Reviewer: Andreas Maletti (Stuttgart)
Some properties of the basis automaton. (Russian. English summary) Zbl 1475.68164
MSC:
68Q45
Nondeterministic fuzzy automata. (English) Zbl 1248.68287
MSC:
68Q45
Deciding regularity of hairpin completions of regular languages in polynomial time. (English) Zbl 1279.68093
Once more on the edge-minimization of nondeterministic finite automata and the connected problems. (English) Zbl 1214.68203
MSC:
68Q45
Extended nondeterministic finite automata. (English) Zbl 1214.68202
MSC:
68Q45
Finite transducers and nondeterministic state complexity of regular languages. (English. Russian original) Zbl 1207.68199
Russ. Math. 54, No. 6, 19-25 (2010); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2010, No. 6, 23-31 (2010).
MSC:
68Q45
On spiking neural P systems. (English) Zbl 1344.68077
Nonconflict check by using sequential automaton abstractions based on weak observation equivalence. (English) Zbl 1192.93078
Some algorithms for equivalent transformation of nondeterministic finite automata. (English. Russian original) Zbl 1298.68150
Russ. Math. 53, No. 4, 54-57 (2009); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2009, No. 4, 67-71 (2009).
MSC:
68Q45
Quasi-deterministic finite automaton (QDFA). (English) Zbl 1205.68204
MSC:
68Q45
Towards molecular computers that operate in a biological environment. (English) Zbl 1140.68396
MSC:
68Q05
68Q10
Doubler and linearizer: An approach toward a unified theory for molecular computing based on DNA complementarity. (English) Zbl 1146.68373
MSC:
68Q10
Efficient enumeration of regular languages. (English) Zbl 1139.68351
Holub, Jan (ed.) et al., Implementation and application of automata. 12th international conference, CIAA 2007, Prague, Czech Republic, July 16–18, 2007. Revised selected papers. Berlin: Springer (ISBN 978-3-540-76335-2/pbk). Lecture Notes in Computer Science 4783, 226-242 (2007).
MSC:
68Q45
On bounded symport/antiport P systems. (English) Zbl 1234.68112
Carbone, Alessandra (ed.) et al., DNA computing. 11th international workshops on DNA computing, DNA11, London, ON, Canada, June 6–9, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-34161-7/pbk). Lecture Notes in Computer Science 3892, 129-143 (2006).
On determinism versus nondeterminism in P systems. (English) Zbl 1079.68036
MSC:
68Q10
68Q05
On membrane hierarchy in P systems. (English) Zbl 1080.68035
MSC:
68Q10
68Q05
Random generation models for NFA’s. (English) Zbl 1098.68065
MSC:
68Q45
Minimized Thompson NFA. (English) Zbl 1082.68061
MSC:
68Q45
A family of NFAs which need 2\(^{n}-\alpha\) deterministic states. (English) Zbl 1022.68067
MSC:
68Q45
Residual finite state automata. (English) Zbl 1011.68048
MSC:
68Q45
The descriptive complexity approach to LOGCFL. (English) Zbl 0983.68108
MSC:
68Q45
Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata. (English) Zbl 1014.68093
MSC:
68Q45
Computing \(\varepsilon\)-free NFA from regular expressions in \(O(n\log^2 (n))\) time. (English) Zbl 0971.68091
Characterization of Glushkov automata. (English) Zbl 0952.68084
MSC:
68Q45
68Q05
The descriptive complexity approach to LOGCFL. (English) Zbl 0924.03069
Meinel, Christoph (ed.) et al., STACS 99. 16th annual symposium on Theoretical aspects of computer science, Trier, Germany, March 4–6, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1563, 444-454 (1999).
On finite automata with limited nondeterminism. (English) Zbl 0923.68090
MSC:
68Q45
On hybrid connectionist-symbolic models. (English) Zbl 0913.68075
Reviewer: Wolfgang Merkle (Heidelberg)
The passing of a rational expression to a nondeterministic finite automaton. (Passage d’une expression rationnelle à un automate fini non-déterministe.) (French) Zbl 0915.68123
Exponential upper and lower bounds for the order of a regular language. (English) Zbl 0823.68049
MSC:
68Q45
On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages. (English) Zbl 0804.68078
Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata. (English) Zbl 0795.68142
On fault tolerance of syntax. (English) Zbl 0783.68068
On the relation between ambiguity and nondeterminism in finite automata. (English) Zbl 0752.68056
MSC:
68Q65
Using partial orders to improve automatic verification methods. (English) Zbl 0786.68061
Computer-aided verification ’90, Proc. 2nd DIMACS Workshop, New Brunswick/NJ (USA) 1990, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 3, 321-340 (1991).
Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language. (English) Zbl 0766.68077
Automata, languages and programming, Proc. 18th Int. Colloq., Madrid/Spain 1991, Lect. Notes Comput. Sci. 510, 641-648 (1991).
MSC:
68Q45
Minimal NFA problems are hard. (English) Zbl 0766.68063
Automata, languages and programming, Proc. 18th Int. Colloq., Madrid/Spain 1991, Lect. Notes Comput. Sci. 510, 629-640 (1991).
Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata. (English) Zbl 0764.68099
Mathematical foundations of computer science, Proc. 16th Int. Symp., Kazimierz Dolny/Pol. 1991, Lect. Notes Comput. Sci. 520, 221-230 (1991).
Relating the type of ambiguity of finite automata to the succinctness of their representation. (English) Zbl 0692.68049
MSC:
68Q45
The nondeterministic finite automaton whose GTB-family is recognizable. (Chinese. English summary) Zbl 0719.68043
MSC:
68Q45
Relating the degree of ambiguity of finite automata to the succinctness of their representation. (English) Zbl 0643.68121
Foundations of software technology and theoretical computer science, Proc. 7th Conf., Pune/India 1987, Lect. Notes Comput. Sci. 287, 26-43 (1987).
On the degree of ambiguity of finite automata. (English) Zbl 0617.68055
Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 620-629 (1986).
MSC:
68Q45
On the structure of finite automata of which M’ is a (weak) inverse with delay \(\tau\). (English) Zbl 0605.68043
MSC:
68Q70
On equality of multiplicity sets of regular languages. (English) Zbl 0611.68049
Reviewer: A.Stolboushkin
MSC:
68Q45
On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. (English) Zbl 0577.68074
Reviewer: Renji Tao
On some decision questions concerning pushdown machines. (English) Zbl 0525.68028
MSC:
68Q05
68Q45
The compilation of regular expressions into integrated circuits. (English) Zbl 0485.68047
MSC:
68Q45
94C10
Three write heads are as good as k. (English) Zbl 0437.68029
MSC:
68Q45
68Q05
Characterizations of the LL(k) property (Extended abstract). (English) Zbl 0443.68073
Automata, languages and programming, 7th Colloq., Noordwijkerhout/ Netherlands 1980, Lect. Notes Comput. Sci. 85, 596-608 (1980).
Amounts of nondeterminism in finite automata. (English) Zbl 0423.68016
MSC:
68Q45
A finite automaton as a plant. (English. Russian original) Zbl 0418.93012
Autom. Remote Control 39, 1365-1374 (1979); translation from Avtom. Telemekh. 1978, No. 9, 126-135 (1978).
Estimates of the number of completely indecomposable and cohesive matrices and corollaries for automata theory. (Russian) Zbl 0411.68051
Algorithms and Automata, Collect. Sci. Works, Kazan 1978, 3-6 (1978).
Filter Results by …
Document Type
- Journal Articles (64)
- Collection Articles (15)
- Books (1)
all
top 5
Author
- Ibarra, Oscar H. (9)
- Melnikov, Boris F. (9)
- Dolgov, V. N. (3)
- Jiang, Tao (3)
- Lyon, Oliver A. S. (3)
- Ravikumar, Bala (3)
- Salomaa, Kai T. (3)
- Ziadi, Djelloul (3)
- Champarnaud, Jean-Marc (2)
- Lautemann, Clemens (2)
- Leung, Hing-Man (2)
- McKenzie, Pierre (2)
- Melnikova, A. A. (2)
- Mitrana, Victor (2)
- Schwentick, Thomas (2)
- Ullman, Jeffrey David (2)
- Vollmer, Heribert (2)
- Wang, Hui (2)
- Weber, Andreas (2)
- Wotschke, Detlef (2)
- Yokomori, Takashi (2)
- Ackerman, Margareta (1)
- Adar, Rivka (1)
- Al’pin, Yurii A. (1)
- Andrés Montoya, Juan (1)
- Baeza-Yates, Ricardo A. (1)
- Belovs, Aleksandrs (1)
- Brandenburg, Franz-Josef (1)
- Broda, Sabine (1)
- Bruschi, Danilo (1)
- Cai, Xing Shi (1)
- Cao, Yongzhi (1)
- Caron, Pascal (1)
- Chen, Shihua (1)
- Chmiel, Krzysztof (1)
- Delos, V. (1)
- Denis, François (1)
- Devroye, Luc P. J. A. (1)
- Diekert, Volker (1)
- Dolgov, Vasily (1)
- Dwork, Cynthia (1)
- Erdős, Péter L. (1)
- Ezawa, Yoshinori (1)
- Floyd, Robert W. (1)
- Gil, Binyamin (1)
- Godefroid, Patrice (1)
- Goldstine, Jonathan (1)
- Hagenah, Christian (1)
- Han, Yo-Sub (1)
- Hansel, Georges (1)
- Hashiguchi, Kosaburo (1)
- Hofkamp, Albert T. (1)
- Hromkovič, Juraj (1)
- Hunt, Harry Bowen III (1)
- Huynh, Dung T. (1)
- Iwama, Kazuo (1)
- Jain, Arihant (1)
- Kahan, Maya (1)
- Karlin, Anna R. (1)
- Kim, Hwee (1)
- Kintala, Chandra (1)
- Kopecki, Steffen (1)
- Kulkarni, Vivek B. (1)
- Kuznetsov, Sergei E. (1)
- Lemay, Aurélien (1)
- Li, Ping (1)
- Li, Yongming (1)
- Machiavelo, António (1)
- Martín-Vide, Carlos (1)
- Masuda, Yusei (1)
- Mateescu, Alexandru (1)
- Matsuura, Akihiro (1)
- Melnikova, Aleksandra (1)
- Mereghetti, Carlo (1)
- Moreira, Nelma (1)
- Morita, Kenichi (1)
- Muscholl, Anca (1)
- Navarro, Gonzalo (1)
- Nishimura, Harumichi (1)
- Nuel, Gregory (1)
- Onodera, Kaoru (1)
- Palano, Beatrice (1)
- Paranthoën, Thomas (1)
- Paterson, Mike S. (1)
- Pérez-Jiménez, Mario J. (1)
- Pighizzini, Giovanni (1)
- Ponty, Jean-Luc (1)
- Povarov, G. A. (1)
- Regan, Kenneth W. (1)
- Reis, Rogério (1)
- Rooda, Jacobus E. (1)
- Rudnev, V. V. (1)
- Ruohonen, Keijo (1)
- Sabadini, Nicoletta (1)
- Saifullina, M. R. (1)
- Seibert, Sebastian (1)
- Seidl, Helmut (1)
- Seki, Shinnosuke (1)
- Shallit, Jeffrey Outlaw (1)
- Shapiro, Ehud Y. (1)
- and 20 more Authors
all
top 5
Serial
- Theor. Comput. Sci. (11)
- SIAM J. Comput. (4)
- Vestn. Voronezh. Gos. Univ., Ser. Fiz. Mat. (4)
- J. Comput. Syst. Sci. (3)
- Inf. Comput. (3)
- J. Autom. Lang. Comb. (3)
- Fundam. Inform. (3)
- Acta Inf. (2)
- Algorithmica (2)
- Int. J. Approx. Reasoning (2)
- Russ. Math. (2)
- Theor. Inform. Appl. (2)
- Nat. Comput. (2)
- Acta Univ. Sapientiae, Inform. (2)
- Acta Cybern. (1)
- Ars Comb. (1)
- Automatica (1)
- Inf. Sci. (1)
- J. Assoc. Comput. Mach. (1)
- Math. Syst. Theory (1)
- Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. (1)
- Physica D (1)
- Order (1)
- J. Syst. Sci. Math. Sci. (1)
- J. Comput. Sci. Technol. (1)
- Random Struct. Algorithms (1)
- Int. J. Found. Comput. Sci. (1)
- Autom. Remote Control (1)
- Int. J. Comput. Math. (1)
- Bull. Belg. Math. Soc. - Simon Stevin (1)
- J. Appl. Math. Comput. (1)
- J. Comput. Math. Optim. (1)
- Pr. Inst. Podstaw Inf. Pol. Akad. Nauk. (1)
all
top 5
Year of Publication
- 2023 (1)
- 2022 (2)
- 2021 (2)
- 2018 (1)
- 2017 (1)
- 2016 (3)
- 2014 (3)
- 2013 (5)
- 2012 (3)
- 2010 (5)
- 2009 (3)
- 2008 (3)
- 2007 (2)
- 2006 (1)
- 2005 (2)
- 2004 (2)
- 2003 (1)
- 2002 (3)
- 2001 (2)
- 2000 (2)
- 1999 (2)
- 1998 (1)
- 1997 (2)
- 1996 (1)
- 1994 (3)
- 1993 (1)
- 1992 (2)
- 1991 (4)
- 1990 (1)
- 1989 (1)
- 1988 (1)
- 1987 (2)
- 1986 (2)
- 1985 (2)
- 1983 (2)
- 1982 (1)
- 1981 (1)
- 1980 (2)
- 1978 (2)
