java -Xss1g -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e3_294_e1_956.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-22 16:01:14,340 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-22 16:01:14,342 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-22 16:01:14,354 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-22 16:01:14,354 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-22 16:01:14,355 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-22 16:01:14,356 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-22 16:01:14,358 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-22 16:01:14,360 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-22 16:01:14,361 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-22 16:01:14,361 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-22 16:01:14,365 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-22 16:01:14,366 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-22 16:01:14,367 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-22 16:01:14,370 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-22 16:01:14,371 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-22 16:01:14,372 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-22 16:01:14,374 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-22 16:01:14,385 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-22 16:01:14,386 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-22 16:01:14,387 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-22 16:01:14,390 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-22 16:01:14,390 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-22 16:01:14,390 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-22 16:01:14,391 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-22 16:01:14,397 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-22 16:01:14,398 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-22 16:01:14,399 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-22 16:01:14,400 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-22 16:01:14,400 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-22 16:01:14,401 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-22 16:01:14,401 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-22 16:01:14,402 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-22 16:01:14,402 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-22 16:01:14,409 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-22 16:01:14,410 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_No_Goto.epf [2018-06-22 16:01:14,423 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-22 16:01:14,423 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-22 16:01:14,424 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-22 16:01:14,424 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-22 16:01:14,425 INFO L131 SettingsManager]: Preferences of ChcToBoogie differ from their defaults: [2018-06-22 16:01:14,425 INFO L133 SettingsManager]: * Use one large procedure with gotos to replace tail recursive calls=false [2018-06-22 16:01:14,425 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-22 16:01:14,425 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-22 16:01:14,425 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-22 16:01:14,426 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-22 16:01:14,426 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 16:01:14,426 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-22 16:01:14,426 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-22 16:01:14,426 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-22 16:01:14,427 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-22 16:01:14,427 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-22 16:01:14,427 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-22 16:01:14,427 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-22 16:01:14,427 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-22 16:01:14,429 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-22 16:01:14,429 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-22 16:01:14,468 INFO ]: Repository-Root is: /tmp [2018-06-22 16:01:14,486 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-22 16:01:14,490 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-22 16:01:14,492 INFO ]: Initializing SmtParser... [2018-06-22 16:01:14,492 INFO ]: SmtParser initialized [2018-06-22 16:01:14,493 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e3_294_e1_956.smt2 [2018-06-22 16:01:14,494 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-22 16:01:14,592 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e3_294_e1_956.smt2 unknown [2018-06-22 16:01:14,970 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/lustre/car_6_e3_294_e1_956.smt2 [2018-06-22 16:01:14,978 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-22 16:01:14,984 INFO ]: Walking toolchain with 4 elements. [2018-06-22 16:01:14,984 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-22 16:01:14,984 INFO ]: Initializing ChcToBoogie... [2018-06-22 16:01:14,985 INFO ]: ChcToBoogie initialized [2018-06-22 16:01:14,988 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:01:14" (1/1) ... [2018-06-22 16:01:15,039 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15 Unit [2018-06-22 16:01:15,039 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-22 16:01:15,040 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-22 16:01:15,040 INFO ]: Initializing Boogie Preprocessor... [2018-06-22 16:01:15,040 INFO ]: Boogie Preprocessor initialized [2018-06-22 16:01:15,059 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,060 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,070 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,070 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,087 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,088 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,089 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... [2018-06-22 16:01:15,092 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-22 16:01:15,092 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-22 16:01:15,092 INFO ]: Initializing RCFGBuilder... [2018-06-22 16:01:15,092 INFO ]: RCFGBuilder initialized [2018-06-22 16:01:15,093 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-22 16:01:15,113 INFO ]: Specification and implementation of procedure False given in one single declaration [2018-06-22 16:01:15,113 INFO ]: Found specification of procedure False [2018-06-22 16:01:15,113 INFO ]: Found implementation of procedure False [2018-06-22 16:01:15,113 INFO ]: Specification and implementation of procedure state given in one single declaration [2018-06-22 16:01:15,113 INFO ]: Found specification of procedure state [2018-06-22 16:01:15,113 INFO ]: Found implementation of procedure state [2018-06-22 16:01:15,113 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-22 16:01:15,113 INFO ]: Found specification of procedure Ultimate.START [2018-06-22 16:01:15,113 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-22 16:01:15,446 INFO ]: Using library mode [2018-06-22 16:01:15,450 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:01:15 BoogieIcfgContainer [2018-06-22 16:01:15,450 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-22 16:01:15,452 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-22 16:01:15,452 INFO ]: Initializing TraceAbstraction... [2018-06-22 16:01:15,460 INFO ]: TraceAbstraction initialized [2018-06-22 16:01:15,460 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 22.06 04:01:14" (1/3) ... [2018-06-22 16:01:15,461 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a3823ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 22.06 04:01:15, skipping insertion in model container [2018-06-22 16:01:15,461 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 22.06 04:01:15" (2/3) ... [2018-06-22 16:01:15,462 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6a3823ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 22.06 04:01:15, skipping insertion in model container [2018-06-22 16:01:15,462 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 22.06 04:01:15" (3/3) ... [2018-06-22 16:01:15,464 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-22 16:01:15,474 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-22 16:01:15,484 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-22 16:01:15,533 INFO ]: Using default assertion order modulation [2018-06-22 16:01:15,534 INFO ]: Interprodecural is true [2018-06-22 16:01:15,534 INFO ]: Hoare is false [2018-06-22 16:01:15,534 INFO ]: Compute interpolants for FPandBP [2018-06-22 16:01:15,534 INFO ]: Backedges is TWOTRACK [2018-06-22 16:01:15,534 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-22 16:01:15,534 INFO ]: Difference is false [2018-06-22 16:01:15,534 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-22 16:01:15,534 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-22 16:01:15,551 INFO ]: Start isEmpty. Operand 13 states. [2018-06-22 16:01:15,565 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-22 16:01:15,565 INFO ]: Found error trace [2018-06-22 16:01:15,566 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:15,566 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:15,570 INFO ]: Analyzing trace with hash -683425083, now seen corresponding path program 1 times [2018-06-22 16:01:15,571 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:15,572 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:15,605 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:15,605 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:01:15,605 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:15,687 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:15,842 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-22 16:01:15,844 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-22 16:01:15,844 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-22 16:01:15,845 INFO ]: Interpolant automaton has 4 states [2018-06-22 16:01:15,856 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-22 16:01:15,856 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 16:01:15,858 INFO ]: Start difference. First operand 13 states. Second operand 4 states. [2018-06-22 16:01:15,973 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:01:15,973 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-22 16:01:15,974 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-22 16:01:15,975 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-22 16:01:15,976 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:01:15,986 INFO ]: With dead ends: 13 [2018-06-22 16:01:15,987 INFO ]: Without dead ends: 13 [2018-06-22 16:01:15,990 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-22 16:01:16,005 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-22 16:01:16,024 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-22 16:01:16,025 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-22 16:01:16,026 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-22 16:01:16,026 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 9 [2018-06-22 16:01:16,026 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:01:16,027 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-22 16:01:16,027 INFO ]: Interpolant automaton has 4 states. [2018-06-22 16:01:16,027 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-22 16:01:16,028 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-22 16:01:16,028 INFO ]: Found error trace [2018-06-22 16:01:16,028 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:16,028 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:16,028 INFO ]: Analyzing trace with hash 204343015, now seen corresponding path program 1 times [2018-06-22 16:01:16,028 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:16,028 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:16,029 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:16,029 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:01:16,029 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:16,080 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:16,299 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 16:01:16,299 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:01:16,299 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-22 16:01:16,315 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:01:16,397 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:16,407 INFO ]: Computing forward predicates... [2018-06-22 16:01:16,823 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-22 16:01:16,843 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:01:16,843 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2018-06-22 16:01:16,844 INFO ]: Interpolant automaton has 9 states [2018-06-22 16:01:16,844 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-22 16:01:16,844 INFO ]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-06-22 16:01:16,844 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 9 states. [2018-06-22 16:01:17,039 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-22 16:01:17,352 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:01:17,352 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-22 16:01:17,353 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-22 16:01:17,353 INFO ]: Start accepts. Automaton has 9 states. Word has length 13 [2018-06-22 16:01:17,353 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:01:17,354 INFO ]: With dead ends: 15 [2018-06-22 16:01:17,354 INFO ]: Without dead ends: 15 [2018-06-22 16:01:17,355 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2018-06-22 16:01:17,355 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-22 16:01:17,357 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-22 16:01:17,357 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-22 16:01:17,358 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-22 16:01:17,358 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-22 16:01:17,358 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:01:17,358 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-22 16:01:17,358 INFO ]: Interpolant automaton has 9 states. [2018-06-22 16:01:17,358 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-22 16:01:17,359 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-22 16:01:17,359 INFO ]: Found error trace [2018-06-22 16:01:17,359 INFO ]: trace histogram [3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:17,359 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:17,359 INFO ]: Analyzing trace with hash -1649658231, now seen corresponding path program 2 times [2018-06-22 16:01:17,359 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:17,359 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:17,360 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:17,360 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-22 16:01:17,360 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:17,440 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:17,852 WARN ]: Spent 243.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 12 [2018-06-22 16:01:17,990 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 16:01:18,043 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:01:18,043 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:01:18,050 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-22 16:01:18,137 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-22 16:01:18,137 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:18,143 INFO ]: Computing forward predicates... [2018-06-22 16:01:18,611 WARN ]: Spent 206.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-22 16:01:19,209 INFO ]: Checked inductivity of 10 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-22 16:01:19,229 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:01:19,229 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 13 [2018-06-22 16:01:19,229 INFO ]: Interpolant automaton has 13 states [2018-06-22 16:01:19,229 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-22 16:01:19,230 INFO ]: CoverageRelationStatistics Valid=25, Invalid=131, Unknown=0, NotChecked=0, Total=156 [2018-06-22 16:01:19,230 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 13 states. [2018-06-22 16:01:19,589 WARN ]: Spent 134.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 36 [2018-06-22 16:01:19,717 WARN ]: Spent 101.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 32 [2018-06-22 16:01:19,852 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:01:19,852 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-22 16:01:19,852 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-22 16:01:19,852 INFO ]: Start accepts. Automaton has 13 states. Word has length 17 [2018-06-22 16:01:19,853 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:01:19,853 INFO ]: With dead ends: 19 [2018-06-22 16:01:19,853 INFO ]: Without dead ends: 19 [2018-06-22 16:01:19,854 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=71, Invalid=235, Unknown=0, NotChecked=0, Total=306 [2018-06-22 16:01:19,854 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-22 16:01:19,857 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-22 16:01:19,857 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-22 16:01:19,858 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-22 16:01:19,858 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-22 16:01:19,858 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:01:19,858 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-22 16:01:19,858 INFO ]: Interpolant automaton has 13 states. [2018-06-22 16:01:19,858 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-22 16:01:19,858 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-22 16:01:19,858 INFO ]: Found error trace [2018-06-22 16:01:19,858 INFO ]: trace histogram [5, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:19,859 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:19,859 INFO ]: Analyzing trace with hash 1762711629, now seen corresponding path program 3 times [2018-06-22 16:01:19,859 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:19,859 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:19,860 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:19,860 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:01:19,860 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:19,997 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:20,609 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 16:01:20,609 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:01:20,609 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:01:20,632 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-22 16:01:20,810 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-22 16:01:20,810 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:20,815 INFO ]: Computing forward predicates... [2018-06-22 16:01:21,198 INFO ]: Checked inductivity of 36 backedges. 0 proven. 26 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-22 16:01:21,220 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:01:21,220 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 21 [2018-06-22 16:01:21,221 INFO ]: Interpolant automaton has 21 states [2018-06-22 16:01:21,221 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-22 16:01:21,221 INFO ]: CoverageRelationStatistics Valid=47, Invalid=373, Unknown=0, NotChecked=0, Total=420 [2018-06-22 16:01:21,221 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 21 states. [2018-06-22 16:01:21,589 WARN ]: Spent 276.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 106 [2018-06-22 16:01:21,952 WARN ]: Spent 294.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 95 [2018-06-22 16:01:22,198 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 99 [2018-06-22 16:01:22,412 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 102 DAG size of output: 93 [2018-06-22 16:01:22,684 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 101 [2018-06-22 16:01:22,722 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:01:22,722 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-22 16:01:22,722 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-22 16:01:22,722 INFO ]: Start accepts. Automaton has 21 states. Word has length 25 [2018-06-22 16:01:22,723 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:01:22,723 INFO ]: With dead ends: 21 [2018-06-22 16:01:22,723 INFO ]: Without dead ends: 21 [2018-06-22 16:01:22,724 INFO ]: 0 DeclaredPredicates, 42 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=132, Invalid=570, Unknown=0, NotChecked=0, Total=702 [2018-06-22 16:01:22,724 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-22 16:01:22,727 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-22 16:01:22,727 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-22 16:01:22,728 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-22 16:01:22,728 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 25 [2018-06-22 16:01:22,728 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:01:22,728 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-22 16:01:22,728 INFO ]: Interpolant automaton has 21 states. [2018-06-22 16:01:22,728 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-22 16:01:22,729 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-22 16:01:22,729 INFO ]: Found error trace [2018-06-22 16:01:22,729 INFO ]: trace histogram [6, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:22,729 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:22,729 INFO ]: Analyzing trace with hash 853117551, now seen corresponding path program 4 times [2018-06-22 16:01:22,729 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:22,729 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:22,730 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:22,730 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:01:22,730 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:22,814 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:23,503 WARN ]: Spent 225.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 29 [2018-06-22 16:01:23,719 WARN ]: Spent 204.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 43 [2018-06-22 16:01:24,163 WARN ]: Spent 299.00 ms on a formula simplification that was a NOOP. DAG size: 30 [2018-06-22 16:01:24,392 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 33 DAG size of output: 18 [2018-06-22 16:01:24,454 INFO ]: Checked inductivity of 55 backedges. 0 proven. 40 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 16:01:24,454 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:01:24,454 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:01:24,461 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-22 16:01:24,577 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-22 16:01:24,577 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:24,586 INFO ]: Computing forward predicates... [2018-06-22 16:01:25,339 INFO ]: Checked inductivity of 55 backedges. 1 proven. 39 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-22 16:01:25,358 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:01:25,358 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 25 [2018-06-22 16:01:25,358 INFO ]: Interpolant automaton has 25 states [2018-06-22 16:01:25,358 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-22 16:01:25,358 INFO ]: CoverageRelationStatistics Valid=60, Invalid=540, Unknown=0, NotChecked=0, Total=600 [2018-06-22 16:01:25,358 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 25 states. [2018-06-22 16:01:25,671 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 105 [2018-06-22 16:01:26,284 WARN ]: Spent 501.00 ms on a formula simplification. DAG size of input: 114 DAG size of output: 94 [2018-06-22 16:01:27,275 WARN ]: Spent 930.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 94 [2018-06-22 16:01:27,686 WARN ]: Spent 372.00 ms on a formula simplification. DAG size of input: 123 DAG size of output: 93 [2018-06-22 16:01:27,966 WARN ]: Spent 241.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 93 [2018-06-22 16:01:28,211 WARN ]: Spent 201.00 ms on a formula simplification. DAG size of input: 101 DAG size of output: 90 [2018-06-22 16:01:28,668 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 96 [2018-06-22 16:01:28,845 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:01:28,845 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-22 16:01:28,846 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-22 16:01:28,846 INFO ]: Start accepts. Automaton has 25 states. Word has length 29 [2018-06-22 16:01:28,846 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:01:28,846 INFO ]: With dead ends: 25 [2018-06-22 16:01:28,846 INFO ]: Without dead ends: 25 [2018-06-22 16:01:28,847 INFO ]: 0 DeclaredPredicates, 50 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=208, Invalid=848, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 16:01:28,847 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-22 16:01:28,850 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-22 16:01:28,850 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-22 16:01:28,851 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-22 16:01:28,851 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 29 [2018-06-22 16:01:28,851 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:01:28,851 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-22 16:01:28,851 INFO ]: Interpolant automaton has 25 states. [2018-06-22 16:01:28,852 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-22 16:01:28,853 INFO ]: Finished isEmpty. Found accepting run of length 38 [2018-06-22 16:01:28,853 INFO ]: Found error trace [2018-06-22 16:01:28,853 INFO ]: trace histogram [8, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:28,853 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:28,853 INFO ]: Analyzing trace with hash -1494134477, now seen corresponding path program 5 times [2018-06-22 16:01:28,853 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:28,853 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:28,854 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:28,854 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:01:28,854 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:29,019 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:29,837 WARN ]: Spent 269.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 16:01:30,671 WARN ]: Spent 750.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 24 [2018-06-22 16:01:30,814 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 21 [2018-06-22 16:01:31,044 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 73 DAG size of output: 48 [2018-06-22 16:01:31,197 WARN ]: Spent 132.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 68 [2018-06-22 16:01:31,547 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 117 DAG size of output: 65 [2018-06-22 16:01:32,238 WARN ]: Spent 129.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 44 [2018-06-22 16:01:32,508 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 12 [2018-06-22 16:01:32,621 INFO ]: Checked inductivity of 105 backedges. 0 proven. 77 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 16:01:32,621 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:01:32,621 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:01:32,629 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-22 16:01:32,791 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2018-06-22 16:01:32,791 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:32,800 INFO ]: Computing forward predicates... [2018-06-22 16:01:33,248 WARN ]: Spent 184.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 25 [2018-06-22 16:01:33,479 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 22 [2018-06-22 16:01:33,728 WARN ]: expecting exponential blowup for input size 6 [2018-06-22 16:01:34,834 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 26 DAG size of output: 20 [2018-06-22 16:01:36,099 WARN ]: Spent 139.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 3 [2018-06-22 16:01:36,689 INFO ]: Checked inductivity of 105 backedges. 3 proven. 74 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-22 16:01:36,722 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:01:36,722 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 33 [2018-06-22 16:01:36,723 INFO ]: Interpolant automaton has 33 states [2018-06-22 16:01:36,723 INFO ]: Constructing interpolant automaton starting with 33 interpolants. [2018-06-22 16:01:36,723 INFO ]: CoverageRelationStatistics Valid=92, Invalid=964, Unknown=0, NotChecked=0, Total=1056 [2018-06-22 16:01:36,723 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 33 states. [2018-06-22 16:01:37,491 WARN ]: Spent 472.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 128 [2018-06-22 16:01:38,022 WARN ]: Spent 440.00 ms on a formula simplification. DAG size of input: 190 DAG size of output: 100 [2018-06-22 16:01:38,670 WARN ]: Spent 598.00 ms on a formula simplification. DAG size of input: 194 DAG size of output: 130 [2018-06-22 16:01:39,694 WARN ]: Spent 976.00 ms on a formula simplification. DAG size of input: 193 DAG size of output: 125 [2018-06-22 16:01:40,162 WARN ]: Spent 413.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 114 [2018-06-22 16:01:40,727 WARN ]: Spent 417.00 ms on a formula simplification. DAG size of input: 174 DAG size of output: 117 [2018-06-22 16:01:41,185 WARN ]: Spent 390.00 ms on a formula simplification. DAG size of input: 167 DAG size of output: 110 [2018-06-22 16:01:41,698 WARN ]: Spent 411.00 ms on a formula simplification. DAG size of input: 165 DAG size of output: 117 [2018-06-22 16:01:42,213 WARN ]: Spent 441.00 ms on a formula simplification. DAG size of input: 175 DAG size of output: 118 [2018-06-22 16:01:42,280 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:01:42,281 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-22 16:01:42,281 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-22 16:01:42,281 INFO ]: Start accepts. Automaton has 33 states. Word has length 37 [2018-06-22 16:01:42,281 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:01:42,282 INFO ]: With dead ends: 29 [2018-06-22 16:01:42,282 INFO ]: Without dead ends: 29 [2018-06-22 16:01:42,283 INFO ]: 0 DeclaredPredicates, 64 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 151 ImplicationChecksByTransitivity, 11.0s TimeCoverageRelationStatistics Valid=343, Invalid=1463, Unknown=0, NotChecked=0, Total=1806 [2018-06-22 16:01:42,283 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-22 16:01:42,287 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-22 16:01:42,288 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-22 16:01:42,289 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-22 16:01:42,289 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 37 [2018-06-22 16:01:42,289 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:01:42,289 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-22 16:01:42,289 INFO ]: Interpolant automaton has 33 states. [2018-06-22 16:01:42,289 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-22 16:01:42,290 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-22 16:01:42,290 INFO ]: Found error trace [2018-06-22 16:01:42,290 INFO ]: trace histogram [10, 9, 9, 9, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:01:42,291 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:01:42,291 INFO ]: Analyzing trace with hash 996918775, now seen corresponding path program 6 times [2018-06-22 16:01:42,291 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:01:42,291 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:01:42,291 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:42,291 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:01:42,291 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:01:42,715 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:43,756 WARN ]: Spent 297.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-22 16:01:44,473 WARN ]: Spent 634.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 30 [2018-06-22 16:01:45,717 WARN ]: Spent 226.00 ms on a formula simplification. DAG size of input: 72 DAG size of output: 50 [2018-06-22 16:01:45,952 WARN ]: Spent 204.00 ms on a formula simplification. DAG size of input: 129 DAG size of output: 24 [2018-06-22 16:01:46,573 WARN ]: Spent 454.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 30 [2018-06-22 16:01:46,959 WARN ]: Spent 312.00 ms on a formula simplification. DAG size of input: 183 DAG size of output: 52 [2018-06-22 16:01:48,023 WARN ]: Spent 823.00 ms on a formula simplification. DAG size of input: 176 DAG size of output: 57 [2018-06-22 16:01:48,681 WARN ]: Spent 546.00 ms on a formula simplification. DAG size of input: 159 DAG size of output: 53 [2018-06-22 16:01:48,912 WARN ]: Spent 178.00 ms on a formula simplification. DAG size of input: 120 DAG size of output: 42 [2018-06-22 16:01:49,097 WARN ]: Spent 112.00 ms on a formula simplification. DAG size of input: 111 DAG size of output: 34 [2018-06-22 16:01:49,370 WARN ]: Spent 194.00 ms on a formula simplification. DAG size of input: 149 DAG size of output: 33 [2018-06-22 16:01:49,803 WARN ]: Spent 338.00 ms on a formula simplification. DAG size of input: 199 DAG size of output: 34 [2018-06-22 16:01:50,336 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 226 DAG size of output: 36 [2018-06-22 16:01:50,748 WARN ]: Spent 293.00 ms on a formula simplification. DAG size of input: 172 DAG size of output: 18 [2018-06-22 16:01:51,004 WARN ]: Spent 189.00 ms on a formula simplification. DAG size of input: 109 DAG size of output: 6 [2018-06-22 16:01:51,271 WARN ]: Spent 181.00 ms on a formula simplification. DAG size of input: 127 DAG size of output: 23 [2018-06-22 16:01:51,377 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 16:01:51,377 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-22 16:01:51,377 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-22 16:01:51,383 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-22 16:01:51,579 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 10 check-sat command(s) [2018-06-22 16:01:51,580 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:01:51,603 INFO ]: Computing forward predicates... [2018-06-22 16:01:52,843 WARN ]: Spent 461.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-22 16:01:54,566 INFO ]: Checked inductivity of 171 backedges. 0 proven. 126 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-22 16:01:54,586 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-22 16:01:54,587 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 41 [2018-06-22 16:01:54,587 INFO ]: Interpolant automaton has 41 states [2018-06-22 16:01:54,587 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-22 16:01:54,588 INFO ]: CoverageRelationStatistics Valid=120, Invalid=1520, Unknown=0, NotChecked=0, Total=1640 [2018-06-22 16:01:54,588 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 41 states. [2018-06-22 16:01:55,431 WARN ]: Spent 665.00 ms on a formula simplification. DAG size of input: 226 DAG size of output: 137 [2018-06-22 16:01:56,297 WARN ]: Spent 729.00 ms on a formula simplification. DAG size of input: 258 DAG size of output: 119 [2018-06-22 16:01:57,051 WARN ]: Spent 667.00 ms on a formula simplification. DAG size of input: 247 DAG size of output: 122 [2018-06-22 16:01:57,814 WARN ]: Spent 665.00 ms on a formula simplification. DAG size of input: 238 DAG size of output: 121 [2018-06-22 16:01:58,781 WARN ]: Spent 903.00 ms on a formula simplification. DAG size of input: 238 DAG size of output: 128 [2018-06-22 16:01:59,318 WARN ]: Spent 441.00 ms on a formula simplification. DAG size of input: 224 DAG size of output: 121 [2018-06-22 16:01:59,831 WARN ]: Spent 436.00 ms on a formula simplification. DAG size of input: 232 DAG size of output: 121 [2018-06-22 16:02:00,361 WARN ]: Spent 443.00 ms on a formula simplification. DAG size of input: 230 DAG size of output: 122 [2018-06-22 16:02:00,910 WARN ]: Spent 416.00 ms on a formula simplification. DAG size of input: 216 DAG size of output: 116 [2018-06-22 16:02:01,584 WARN ]: Spent 534.00 ms on a formula simplification. DAG size of input: 226 DAG size of output: 127 [2018-06-22 16:02:01,655 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-22 16:02:01,655 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-22 16:02:01,656 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-22 16:02:01,656 INFO ]: Start accepts. Automaton has 41 states. Word has length 45 [2018-06-22 16:02:01,656 INFO ]: Finished accepts. some prefix is accepted. [2018-06-22 16:02:01,657 INFO ]: With dead ends: 31 [2018-06-22 16:02:01,657 INFO ]: Without dead ends: 31 [2018-06-22 16:02:01,658 INFO ]: 0 DeclaredPredicates, 77 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 124 ImplicationChecksByTransitivity, 15.8s TimeCoverageRelationStatistics Valid=460, Invalid=2192, Unknown=0, NotChecked=0, Total=2652 [2018-06-22 16:02:01,658 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-22 16:02:01,662 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-22 16:02:01,662 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-22 16:02:01,665 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-22 16:02:01,665 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 45 [2018-06-22 16:02:01,665 INFO ]: Finished accepts. word is rejected. [2018-06-22 16:02:01,665 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-22 16:02:01,665 INFO ]: Interpolant automaton has 41 states. [2018-06-22 16:02:01,665 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-22 16:02:01,666 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-22 16:02:01,666 INFO ]: Found error trace [2018-06-22 16:02:01,667 INFO ]: trace histogram [11, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-22 16:02:01,667 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-22 16:02:01,667 INFO ]: Analyzing trace with hash -570306151, now seen corresponding path program 7 times [2018-06-22 16:02:01,667 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-22 16:02:01,667 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-22 16:02:01,667 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:02:01,667 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-22 16:02:01,667 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-22 16:02:02,034 INFO ]: Conjunction of SSA is unsat [2018-06-22 16:02:03,503 WARN ]: Spent 152.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-22 16:02:05,216 WARN ]: Spent 1.60 s on a formula simplification. DAG size of input: 214 DAG size of output: 21 [2018-06-22 16:02:05,681 WARN ]: Spent 427.00 ms on a formula simplification. DAG size of input: 236 DAG size of output: 26 [2018-06-22 16:02:08,772 WARN ]: Spent 426.00 ms on a formula simplification. DAG size of input: 226 DAG size of output: 25 [2018-06-22 16:02:09,507 WARN ]: Spent 659.00 ms on a formula simplification. DAG size of input: 287 DAG size of output: 24 [2018-06-22 16:02:10,171 WARN ]: Spent 596.00 ms on a formula simplification. DAG size of input: 217 DAG size of output: 22 [2018-06-22 16:02:11,628 WARN ]: Spent 1.32 s on a formula simplification. DAG size of input: 447 DAG size of output: 27 [2018-06-22 16:02:13,447 WARN ]: Spent 1.64 s on a formula simplification. DAG size of input: 403 DAG size of output: 28 [2018-06-22 16:02:14,812 WARN ]: Spent 1.16 s on a formula simplification. DAG size of input: 385 DAG size of output: 19 [2018-06-22 16:02:15,212 WARN ]: Spent 304.00 ms on a formula simplification. DAG size of input: 209 DAG size of output: 22 [2018-06-22 16:02:15,635 WARN ]: Spent 323.00 ms on a formula simplification. DAG size of input: 204 DAG size of output: 15 [2018-06-22 16:02:17,126 WARN ]: Spent 1.34 s on a formula simplification. DAG size of input: 379 DAG size of output: 13 Received shutdown request... [2018-06-22 16:02:18,288 WARN ]: Removed 2 from assertion stack [2018-06-22 16:02:18,288 WARN ]: Verification canceled [2018-06-22 16:02:18,292 WARN ]: Timeout [2018-06-22 16:02:18,292 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 22.06 04:02:18 BoogieIcfgContainer [2018-06-22 16:02:18,292 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-22 16:02:18,293 INFO ]: Toolchain (without parser) took 63314.47 ms. Allocated memory was 302.5 MB in the beginning and 1.3 GB in the end (delta: 948.4 MB). Free memory was 250.9 MB in the beginning and 1.0 GB in the end (delta: -751.9 MB). Peak memory consumption was 943.7 MB. Max. memory is 3.6 GB. [2018-06-22 16:02:18,293 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 302.5 MB. Free memory is still 268.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-22 16:02:18,294 INFO ]: ChcToBoogie took 54.88 ms. Allocated memory is still 302.5 MB. Free memory was 250.9 MB in the beginning and 248.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:02:18,294 INFO ]: Boogie Preprocessor took 51.97 ms. Allocated memory is still 302.5 MB. Free memory was 248.9 MB in the beginning and 246.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-22 16:02:18,294 INFO ]: RCFGBuilder took 358.40 ms. Allocated memory is still 302.5 MB. Free memory was 246.9 MB in the beginning and 230.8 MB in the end (delta: 16.1 MB). Peak memory consumption was 16.1 MB. Max. memory is 3.6 GB. [2018-06-22 16:02:18,295 INFO ]: TraceAbstraction took 62840.14 ms. Allocated memory was 302.5 MB in the beginning and 1.3 GB in the end (delta: 948.4 MB). Free memory was 230.8 MB in the beginning and 1.0 GB in the end (delta: -772.0 MB). Peak memory consumption was 923.7 MB. Max. memory is 3.6 GB. [2018-06-22 16:02:18,297 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 302.5 MB. Free memory is still 268.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 54.88 ms. Allocated memory is still 302.5 MB. Free memory was 250.9 MB in the beginning and 248.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 51.97 ms. Allocated memory is still 302.5 MB. Free memory was 248.9 MB in the beginning and 246.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 358.40 ms. Allocated memory is still 302.5 MB. Free memory was 246.9 MB in the beginning and 230.8 MB in the end (delta: 16.1 MB). Peak memory consumption was 16.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62840.14 ms. Allocated memory was 302.5 MB in the beginning and 1.3 GB in the end (delta: 948.4 MB). Free memory was 230.8 MB in the beginning and 1.0 GB in the end (delta: -772.0 MB). Peak memory consumption was 923.7 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 50 with TraceHistMax 11, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 501. - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 13 locations, 1 error locations. TIMEOUT Result, 62.7s OverallTime, 8 OverallIterations, 11 TraceHistogramMax, 18.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 79 SDtfs, 428 SDslu, 676 SDs, 0 SdLazy, 529 SolverSat, 516 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 287 GetRequests, 112 SyntacticMatches, 0 SemanticMatches, 175 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 411 ImplicationChecksByTransitivity, 36.1s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=31occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.6s SatisfiabilityAnalysisTime, 24.8s InterpolantComputationTime, 341 NumberOfCodeBlocks, 341 NumberOfCodeBlocksAsserted, 34 NumberOfCheckSat, 328 ConstructedInterpolants, 0 QuantifiedInterpolants, 143920 SizeOfPredicates, 249 NumberOfNonLiveVariables, 4258 ConjunctsInSsa, 342 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 208/760 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/car_6_e3_294_e1_956.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-22_16-02-18-312.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/car_6_e3_294_e1_956.smt2_AutomizerCHC_No_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-22_16-02-18-312.csv Completed graceful shutdown